In this interview, I speak to one of the world’s foremost experts in Quantum Computing, Scott Aaronson. Scott is Schlumberger Centennial Chair of Computer Science at The University of Texas at Austin, and director of its Quantum Information Center. His research interests centre around the capabilities and limits of quantum computers, and computational complexity theory more generally. From 2022-2024, he worked with OpenAI on the theoretical foundations of AI safety.
Q: How does Quantum Computing work?
[Scott Aaronson]: A quantum computer is very similar to a classical computer, with one key difference: it takes full advantage of the laws of quantum mechanics. These laws, first formulated by pioneers like Heisenberg, Schrodinger, Bohr, Dirac and von Neumann in the 1920s, generalize the rules of probability in surprising ways.
The heart of quantum mechanics is the concept of amplitudes. An amplitude is a new kind of number, related to but distinct from an ordinary probability. Amplitudes can be positive, negative, or even complex numbers. The fundamental rule of quantum mechanics states that to calculate the probability of an event occurring, you must:
- Assign an amplitude to each possible way the event could happen
- Sum the amplitudes for all possible paths
- Square the absolute value of this sum to get the final probability
The surprising consequence is that amplitudes can interfere with each other. If an event can happen in two different ways, one with a positive amplitude and one with a negative amplitude, the contributions can cancel out, leading to zero probability of the event occurring. Decreasing the number of paths can paradoxically increase the likelihood of an outcome.
This is beautifully illustrated by the famous double-slit experiment. When a photon is fired at a screen with two narrow slits, an interference pattern emerges, with dark fringes where the photon never lands. Closing one slit eliminates the interference and allows the photon to reach those dark spots. The amplitudes traveling through the two slits interfered destructively; blocking one path prevents this cancellation.
In quantum mechanics, the state of a system is described by a wave function – a list of amplitudes for each possible configuration. For a single particle, the wave function assigns an amplitude to each possible position, forming a “smear” of probability. This is the basis for phenomena like electron orbitals in chemistry.
With multiple particles, the wave function becomes vastly more complex. The amplitudes can no longer be specified separately for each particle; an amplitude must be assigned to every possible configuration of all particles together. For a system of n qubits (quantum bits that can be in a superposition of 0 and 1), there are 2^n amplitudes. A 1000 qubit system would require 2^1000 amplitudes – more than the number of atoms in the observable universe.
This exponential scaling reveals the immense complexity lurking beneath the surface of reality. Taking full computational advantage of these quantum laws is the essence of quantum computing. By harnessing interference and entanglement, quantum computers can perform certain tasks, like factoring large numbers and simulating molecules, exponentially faster than any classical computer.
Q: What does Quantum Computing reveal about our universe?
[Scott Aaronson]: The strangeness of reality was apparent long before the advent of quantum mechanics. The history of science is a sequence of revelations, each showing that the true nature of things is not what it seems to the casual observer. Quantum mechanics, however, takes this weirdness to a new level.
According to quantum theory, it is impossible to fully specify the state of a system by simply listing the positions of each particle. Instead, one must write down a wave function that describes the system as a whole. This requirement was present from the very beginning of the theory. In his groundbreaking 1926 paper, Erwin Schrödinger discussed the wave function Ψ(x) for a single particle, and then posed the question of how to describe a system of three particles. His answer was that a single wave function Ψ(x, y, z) would be needed for all the particles together.
Schrödinger acknowledged that this might seem like a “preposterous suggestion,” but argued that there were “many considerations in its favour,” chief among them being that he saw no other way to ensure the probabilities would sum to 1, as required. This holistic, exponential nature of quantum states was always lurking in the background of the theory, but was often overlooked as most early applications dealt with very small systems of only a few particles.
Quantum computing can be seen as a monumental effort to fully confront this exponential scaling that lies at the heart of quantum mechanics. By building and testing quantum computers, we are conducting an experiment that should either indisputably confirm this exponential nature, or overturn a century of established quantum theory. Either way, the goal is to uncover the truth about the fundamental workings of reality.
The implications are profound. If quantum mechanics is correct, then the computational power of the universe is far greater than what can be accessed classically. Harnessing this power could lead to breakthroughs in fields from cryptography to drug discovery. On the other hand, if quantum mechanics is found to break down at large scales, it would require a revision of our most basic understanding of nature. Quantum computing is thus not just a technological pursuit, but a deeply philosophical one, aiming to probe the very foundations of our world.
Q: Why do Quantum Computers matter?
[Scott Aaronson]: My initial motivation for studying quantum computing was a desire to understand the fundamental computational limits of the universe. Even in the absence of practical applications, I believed this pursuit was worthwhile as the most rigorous test of quantum mechanics to date. In fact, I often joke that disproving quantum computing sceptics is the primary application of a quantum computer, with everything else being a bonus. However, it turns out there are indeed promising applications on the horizon.
The original vision for quantum computers, as proposed by Richard Feynman, David Deutsch, and others over 40 years ago, was to create a programmable device for simulating quantum mechanics itself. Chemists and physicists have long recognized the exponential scaling of quantum systems as a practical barrier to classical simulation. Much of the history of quantum chemistry has revolved around developing increasingly sophisticated approximation methods to manage this exponential growth.
Feynman, in his seminal 1981 lecture, argued that if simulating quantum mechanics is exponentially difficult for classical computers, perhaps we are not building computers optimally. He suggested constructing computers that operate on qubits rather than bits, leveraging entanglement and amplitude interference to capture the exponential complexity of quantum systems. To this day, simulating quantum mechanics remains the most economically significant application of quantum computing. Designing better batteries, solar cells, and chemical catalysts all involve many-body quantum problems that could potentially be accelerated by a quantum computer. While not as widely relatable as everyday computing tasks, these applications could have substantial downstream economic impact.
The discovery that truly put quantum computing on the map came a decade after Feynman’s proposal. In 1994, Peter Shor demonstrated that a quantum computer could efficiently find the prime factors of large numbers by exploiting quantum interference. This was a breakthrough because factoring is believed to be classically intractable – so much so that much of modern internet security relies on the hardness of factoring and related problems in number theory.
Shor’s algorithm showed that quantum computers could potentially solve certain classical problems exponentially faster than the best known classical algorithms. This generated tremendous excitement and spurred a wave of research into quantum algorithms and complexity theory. While relatively few such exponential speedups have been discovered, the potential for even a handful of key applications has been enough to drive major investments in quantum computing research and development.
As quantum computing technology continues to advance, the field stands at a pivotal juncture. On one hand, building a large-scale quantum computer would provide the most stringent test of quantum mechanics to date, potentially affirming or overturning a century of established theory. On the other hand, if successful, quantum computers could unlock computational capabilities far beyond what is classically possible, with transformative applications in chemistry, optimization, machine learning, and cryptography.
Realizing this potential will require sustained collaboration across physics, computer science, mathematics, and engineering. While significant challenges remain, the progress in recent years has been remarkable. As we continue to push the boundaries of what is computationally possible, we are not just developing a new technology, but fundamentally expanding our understanding of the universe and our place within it.
Q: What are the ethical issues around quantum computing?
[Scott Aaronson]: Any technology with the potential for significant global impact raises important ethical considerations. Having recently spent two years working on AI safety and ethics at OpenAI, I have been deeply engaged in examining the moral and societal implications of artificial intelligence. With AI, we face a profound civilizational question: as AI systems become increasingly capable of performing tasks previously done by humans, what role will humans play in an AI-driven world? Will AI eventually surpass human intelligence to such a degree that our relationship to AI becomes analogous to that between humans and other great apes? And if so, will AI treat humanity with more moral consideration than we have shown our evolutionary cousins? These questions, first posed by Alan Turing in 1951, have taken on new urgency in light of the rapid advances in AI capabilities over the past five years.
While the ethical challenges posed by quantum computing are perhaps less existential in nature, they are nonetheless significant. The potential for quantum computers to break current cryptographic systems that secure internet communications and transactions is a major concern for cybersecurity and even geopolitical stability. However, the situation is somewhat mitigated by the existence of quantum-resistant or post-quantum cryptographic schemes. These cryptosystems are based on mathematical problems, such as lattice problems, that have thus far withstood attacks from both classical and quantum algorithms over several decades of research.
In recent years, there has been a concerted effort to upgrade the security infrastructure of the internet to utilize these quantum-resistant protocols. The U.S. National Institute of Standards and Technology (NIST) has issued recommendations for post-quantum cryptographic standards, and major tech companies like Google have already begun implementing these upgrades. While there is no absolute guarantee that these new cryptosystems will never be broken – indeed, proving the long-term security of any cryptographic protocol remains an open problem in mathematics and computer science – the transition to post-quantum cryptography is well underway.
Some have drawn an analogy between the disruptive potential of quantum computing and that of nuclear weapons. However, I believe this comparison is somewhat overstated. While a quantum computer could certainly cause significant economic and social disruption if used to break encryption, it does not pose the same kind of direct, physical threat to human life as nuclear weapons. Barring an unfortunate accident involving a dilution refrigerator, a quantum computer is unlikely to directly cause loss of life.
As quantum computing and AI continue to advance, it is crucial that we as a society grapple with the ethical implications of these powerful technologies. While the challenges they pose are significant, I remain optimistic that with foresight, collaboration, and a commitment to responsible development, we can harness the potential of these technologies for the benefit of humanity. By proactively addressing issues of safety, security, and social impact, we can work to ensure that the development of quantum computing and AI aligns with our values and contributes to a better future for all.
Q: How will Quantum Computing play a role in AI, for example?
[Scott Aaronson]: In recent years, many quantum computing startups have promoted the idea that quantum computers will revolutionize artificial intelligence (AI). While this narrative has gained significant traction, especially among those seeking investment, the evidence supporting this claim is mixed at best. To understand why, we must examine the fundamental principles of quantum computation and the specific problems for which quantum computers are well-suited.
Quantum computers have been shown to offer substantial advantages over classical computers in two key areas:
- Quantum computers are uniquely suited to simulate the behaviour of complex quantum systems, such as molecules and materials. This capability could accelerate research in fields like drug discovery and materials science.
- Certain quantum algorithms, like Shor’s algorithm, can efficiently factor large numbers, a task that is believed to be intractable for classical computers. This has significant implications for the security of modern cryptographic systems that rely on the difficulty of factoring.
However, the potential of quantum computers to broadly accelerate AI remains uncertain.
A common misconception is that quantum computers can simply try all possible solutions to a problem simultaneously, thanks to the principle of superposition. This idea suggests that a quantum computer could, for example, factor a number by trying every possible divisor in parallel, with the correct answer somehow “shouting above” the rest.
While it is true that a quantum computer can create a superposition of all possible answers, even for problems with exponentially large solution spaces, this alone does not provide a computational advantage. When a superposition is measured, the rules of quantum mechanics dictate that a random answer will be observed. Simply generating a random answer provides no benefit over classical computation.
To achieve a quantum speedup, algorithms must carefully manipulate the amplitudes associated with each possible answer, leveraging the phenomenon of quantum interference. By choreographing the interference pattern, quantum algorithms can suppress the amplitudes of incorrect answers while amplifying the amplitude of the correct answer. This constructive and destructive interference is the key to extracting useful information from a quantum computation.
Designing quantum algorithms that successfully exploit interference to solve practical problems is a significant challenge. While a few such algorithms have been discovered, like Shor’s algorithm for factoring and Grover’s algorithm for unstructured search, they rely on specific problem structures and do not generalize to all of AI.
While quantum computing is a transformative technology with the potential to revolutionize certain domains, its impact on AI more broadly remains an open question. The popular narrative of quantum computers effortlessly solving AI problems through sheer parallelism is a misconception. Quantum advantage arises from the careful orchestration of interference, a feat that has been achieved for only a handful of problems to date.
As research in quantum computing and quantum algorithms progresses, it is crucial to maintain a realistic perspective on the technology’s capabilities and limitations. By focusing on the fundamental principles of quantum computation and the specific problems for which quantum speedups have been rigorously demonstrated, we can cut through the hype and make informed decisions about the future of this exciting field.
Q: What does the future hold for Quantum Computing?
[Scott Aaronson]: At the most fundamental level, all phenomena are governed by the laws of quantum mechanics. However, the relevance of quantum effects varies greatly depending on the scale and complexity of the system under consideration. In this report, we will examine the role of quantum mechanics in biology, the challenges of building practical quantum computers, and the potential for quantum speedup in various computational tasks.
While it is clear that quantum mechanics plays a role in certain biological processes, such as photosynthesis and enzymatic reactions, the overall relevance of quantum effects in biology remains an open question. In everyday life, we typically do not observe quantum phenomena directly, as the systems we interact with are constantly measuring and influencing each other. This interaction can lead to the decoherence of quantum superpositions, effectively “collapsing” them into classical states.
The central challenge in building a practical quantum computer lies in isolating the quantum bits (qubits) from their environment to maintain their delicate superposition states, while still allowing for precise control and interaction between qubits. Any leakage of information from a qubit to its environment can cause decoherence, collapsing the superposition and disrupting the computation.
Significant progress has been made in recent years, with demonstrations of individual qubits approaching the reliability thresholds required for quantum error correction. However, the overhead associated with error correction is substantial, potentially requiring millions of physical qubits to simulate a single reliable logical qubit. This overhead poses a major challenge for realizing the full potential of quantum computers.
To achieve a quantum advantage over classical computation, algorithms must leverage the unique properties of quantum systems, such as superposition and interference. Shor’s algorithm for factoring large numbers and Grover’s algorithm for unstructured search are two prominent examples of quantum algorithms that offer significant speedups over their classical counterparts.
However, the applicability of these algorithms is limited by the specific problem structures they exploit. Many problems of practical interest, such as combinatorial optimization and machine learning tasks, do not naturally fit into these frameworks. While quantum computers can often provide a modest speedup for these problems, the advantage is typically quadratic rather than exponential.
Given the substantial overhead of quantum error correction, a quadratic speedup may only become practically relevant for extremely large problem instances. For example, to see a practical advantage from Grover’s algorithm, the problem size might need to be on the order of trillions, assuming an error correction overhead of a million times.
While quantum computing holds great promise for revolutionizing certain domains, such as quantum simulation and cryptography, its potential impact on general-purpose computation and artificial intelligence remains uncertain. The challenges of building reliable qubits and the limitations of known quantum algorithms suggest that practical quantum advantages in these areas may be further off than initially hoped.
As research in quantum computing and quantum algorithms progresses, it is essential to maintain a realistic perspective on the technology’s capabilities and limitations. By focusing on the fundamental principles of quantum mechanics and the specific problem structures that admit significant quantum speedups, we can guide the development of this transformative technology towards the most promising applications.