Apple Finch Pudding

What Can Quantum Computers Actually Do? | Scott Aaronson | AFP 56

The following is based on a conversation with Scott Aaronson, a professor in computer sciences at the University of Texas at Austin.

What is the P vs NP problem, and why does it fundamentally limit our ability to predict quantum speedups?

The P vs NP problem is an unsolved question in computer science that asks whether every problem whose solution can be verified efficiently (in polynomial time, class NP) can also be solved efficiently from scratch (class P).

Quantum computing adds a layer of subtlety to this class structure through the introduction of BQP (bounded-error quantum polynomial time), which represents the set of problems efficiently solvable on a quantum computer. While classical polynomial time (P) is contained within both NP and BQP, computer scientists do not know the exact boundaries separating these complexity classes.

Because theoretical computer scientists have not yet proven the fundamental limits of efficient classical algorithms, it is extraordinarily difficult to prove whether a given quantum algorithm offers a true, permanent speedup over classical methods, or if a classical algorithm can be designed to match its performance.

How does quantum interference allow quantum algorithms like Shor’s to achieve exponential speedups over classical computing?

Quantum computers operate by manipulating complex mathematical values called amplitudes, which are assigned to every possible configuration of a physical system. Unlike classical probabilities, which range strictly from 0 to 1, amplitudes can be positive, negative, or complex numbers.

When a quantum system evolves without being observed, these amplitudes interfere with one another. If an outcome can occur via two paths, one with a positive amplitude and one with a negative amplitude, the paths cancel each other out, dropping the probability of that outcome to zero.

Algorithms like Shor’s algorithm use this principle to solve problems with specific mathematical structure, such as hidden periodicity in number theory. By arranging the algorithm so that incorrect answers undergo destructive interference (canceling out) and correct answers undergo constructive interference (amplifying), the probability shifts almost entirely to the correct answer when measured.uous glucose monitor (CGM) curve patterns, allows for targeted dietary interventions, such as consuming fiber or protein prior to carbohydrates to blunt glycemic spikes.

Why is Grover’s algorithm less likely to offer an immediate real-world win for AI than Shor’s algorithm is for cryptography?

Grover’s algorithm provides a general-purpose way to search an unstructured space of N items in (O(N)O(\sqrt{N}) steps, yielding a quadratic speedup over classical brute-force search (O(N)). While quadratic speedups apply to a much broader range of real-world problems, including optimization and AI search tasks, they are mathematically far less powerful than the exponential speedups provided by algorithms like Shor’s algorithm.

An exponential speedup turns a problem that would take longer than the age of the universe into one that takes seconds. A quadratic speedup merely reduces an exponential search from 210002^{1000} operations to 25002^{500} operations, which remains computationally intractable.

Furthermore, running physical quantum hardware incurs massive structural, operational, and error-correction overheads. Because the mathematical gain of a quadratic speedup is modest, those physical overheads mean that Grover’s algorithm will take much longer to outperform optimized classical hardware running advanced heuristics.

Do you want science ideas worth thinking about in your inbox?

Real scientific ideas, from black holes to bacteria, explained the way we’d explain it to a friend who actually wants to understand, straight to your inbox.

Cleaned Transcript

Jeroen Schreel: Welcome to Apple Finch Pudding, your gateway into the world of science. Today’s scientist is Scott Aaronson, a professor in computer science at the University of Texas at Austin. His work focuses on quantum computers. Welcome, Scott.

Scott Aaronson: Thanks. It’s great to be here.

Jeroen Schreel: Scott, you have done numerous interviews, and I think a lot of people have asked you about quantum computing. But what are some of the biggest lies or marketing hypes that companies are currently telling the public about quantum computing?

Scott Aaronson: Oh, it’s hard to know where to start. The single biggest thing—which has been true for decades now, but has become more prominent as quantum computing gets closer to scaling and working like the theory says—is that people want to present quantum computing as a magic solution that speeds up everything. So no matter what problem you have—optimization, machine learning, AI, supply chain, finance—the solution is going to be quantum because quantum is new, spooky, and somehow tries every possible answer in parallel. They tell you not to worry too much about the details.

What’s hard is that people hear that narrative of quantum computing speeding everything up, and some of them just eat it up with mustard. We’ve seen decades of journalists uncritically repeating this, often with investors pumping companies up to multi-billion-dollar valuations on the basis of this belief.

Then other people realize that it isn’t true, and they jump to the opposite extreme. They say the whole idea of quantum computing must be a fraud and doesn’t work at all. The tragedy is that we’ve understood the basic picture since the 1990s. It’s just been really hard to get the message out that quantum computing is an incredible accelerator for a few very specific types of problems that have a particular structure you can exploit using quantum interference.

There are two big categories of problems where we think that helps a lot. One is simulating quantum physics and chemistry themselves, which was the original application Richard Feynman had in mind when he proposed the idea of a quantum computer 45 years ago. I think it’s still the most economically important application we know. It could help in designing better batteries, better solar cells, new materials, and maybe new ways to make fertilizer.

Nature gave us this lemon of being so complicated to simulate because of the exponentiality of wave functions in quantum mechanics. So we’re taking that lemon and making lemonade: building computers that take advantage of the same phenomena.

The second big application was discovered by Peter Shor in 1994, which really put quantum computing on the map for most of the world and launched it as a field. It so happens that a quantum computer can break most forms of encryption that we use to protect the internet.

This isn’t because a quantum computer breaks every code or tries every answer at once. It’s for a more subtle reason: those cryptographic codes happen to be based on certain problems in number theory and group theory that involve finding the period of a periodic function. That hidden periodicity is the exact structure needed to design a quantum interference experiment that concentrates all the amplitude onto the correct solutions.

We were unlucky in a way to base the security architecture of the modern internet on cryptographic codes that had this specific vulnerability to quantum computers. That’s why there is a big push right now to migrate to post-quantum or quantum-resistant encryption—cryptographic codes developed over the last 25 years that give us the same benefits, but would hopefully resist attack even by a quantum computer.

That’s a huge story of cybersecurity, geopolitical, and military importance. But starting about 20 years ago, a narrative took shape that quantum computers were really going to speed up AI, machine learning, finding patterns in data, and optimizing large sets of variables.

That sounded really good to people and synced with the idea of a quantum computer exploring all possible answers in superposition. There were little grains of truth to it: there are some quantum speedups in those domains, and there’s lots of research—including by me and my students—on how to find more. But it’s a complicated, evolving picture. The speedups we know for these workhorse problems of finance, industry, and machine learning tend to be much more modest, much further in the future before you see a win, or much more speculative.

That is the biggest misrepresentation people have. It’s downstream from a deeper misrepresentation about how a quantum computer really works. Explaining how it actually works takes 10 or 15 minutes of explaining what quantum mechanics says about the world. But the scope of applications is something I hope any journalist or investor should be able to understand if someone takes the time to explain it to them.

Jeroen Schreel: Yeah, and you have been doing that very successfully, I might add.

Scott Aaronson: Well, it doesn’t feel that way from where I stand. It feels like I’m pushing a boulder up a hill for eternity like Sisyphus, but I do what I can.

Jeroen Schreel: People also want to be optimistic about what is possible.

Scott Aaronson: Look, I want to be optimistic about technology, and I often am. I was later than some people to realize what was happening with AI, but around 2020 or 2021 when I played around with GPT-3, I realized this was going to change the world. People who say it won’t change the world are just in denial about it.

I had a similar feeling as a teenager when I first saw the web. I wondered why everyone wasn’t doing everything that way, and the answer was to give it a couple of decades and they would be. I’ve spent my whole career in quantum computing because I was fascinated by the way it overturns our previous beliefs about the fundamental limits of computation.

The hard part about quantum computing specifically is that it’s never enough for a quantum algorithm to work; to be useful, it has to beat the best classical solution. There are amazing advancements in quantum computing, but there are also amazing advancements happening in classical computing.

Again and again in quantum computing research, people thought they had a quantum algorithm dramatically faster than any known classical algorithm for a task. Then classical computer scientists caught wind of it, realized there was interest in that problem, and designed a much faster classical algorithm. Poof, the quantum speedup was gone! This is called “dequantization”—replacing quantum algorithms with classical ones.

From the point of view of scientific understanding, this is great. We discovered a fast new algorithm that runs on existing computers, which wouldn’t have happened without quantum computing research as the spur. But from the point of view of what a quantum computer is good for, it’s only good for things where there isn’t a fast classical algorithm to do the same task.

When I tell people this, it blows their minds: they think quantum algorithms research must be hard because it’s unfamiliar to think in quantum terms. But people have been doing this for 30 years or more, and we have a lot of intuition now. Often, coming up with a quantum algorithm or protocol is the easier part. The harder part is convincingly arguing why there won’t be an equally good classical solution. So the hard part of quantum computing research often comes down to our ignorance of the limitations of classical computers.

Jeroen Schreel: To rehash that so it’s clear in my mind: quantum computers will not speed up everything. They will be good at specific things, like helping us with quantum research, which will hopefully result in things like better solar cells.

Scott Aaronson: Hopefully. What a quantum computer does is give you a fully programmable tool for simulating any kind of quantum system with lots of interacting particles without suffering from the exponential explosion faced on a classical computer. That explosion comes from wave functions having a separate parameter for every possible way particles could be configured.

Does that automatically mean a new drug pops out that cures cancer, or a better solar cell or battery pops out? No. First of all, those solutions have to exist. We don’t actually know what is out there in the space of all molecules, proteins, or materials that hasn’t already been discovered by trial and error. The quantum computer doesn’t help all that much with combinatorial search among candidate drugs or materials—it helps only modestly with that part.

Where it really helps is when you have a candidate involving lots of interacting particles where, in the past, people had no choice but to synthesize that molecule or build that material in the lab and measure its properties. Now you have a programmable way to get those answers. With classical computers, people often resort to approximations because of the exponentiality of the wave function, and sometimes those approximations aren’t good enough. The hope is that this will lead to new discoveries. There are no guarantees, but there will be many shots on goal.

Jeroen Schreel: Quantum computing will be better at some stuff than classical computing, but there’s a race going on between them.

Scott Aaronson: A quantum computer is a strict generalization of a classical computer. Anything a classical computer can do in principle, you could also do with a quantum computer. But for most things we do on classical computers—checking email, playing Minecraft, browsing social media—it’s not obvious why you would want a quantum computer. It would be like using the Space Shuttle to taxi people around a parking lot.

For certain specific hard problems involving a combinatorial explosion in potential solutions—like the Traveling Salesman Problem or finding the prime factors of a huge number (which Shor’s algorithm solves)—quantum computers don’t speed up all of them. They speed up specific ones.

People ask if there’s a general rule for which problems have quantum speedups and which don’t. That’s what we’ve been studying for 30 years. We have answers, but the answer doesn’t take the form of a single sentence—it takes the form of a textbook or an undergraduate course. We don’t even fully know the limits of efficient classical algorithms; there is a famous unsolved problem in computer science, the P vs NP problem, which is about which problems can avoid this combinatorial explosion. We don’t even know that for classical algorithms.

Jeroen Schreel: Could you explain what the P vs NP problem really is?

Scott Aaronson: P stands for Polynomial Time. It’s the class of all problems that have an algorithm running on a conventional classical computer taking a number of steps that scales, at most, like the size of the problem raised to some fixed power. By the size of the problem, I mean the number of bits needed to specify the input.

This includes most of what we do on computers daily. If I give you two n-digit numbers and ask you to add them, you can do that in a number of steps that grows linearly with n. If I ask you to multiply two n-digit numbers, grade-school multiplication uses an amount of time that scales quadratically (n2), which is still polynomial time and efficient according to our criterion. In the 1960s and 70s, people came up with much cleverer ways to multiply n-digit numbers that take almost linear time.

There are more interesting examples. If I give you a group of people and a list of who is willing to date whom, and ask if everyone can be paired off with a happy partner, that sounds like it would face a combinatorial explosion. But in the 1960s, an efficient solution was discovered that scales like n3. If I give you an n-digit number and ask if it’s prime, trying every divisor takes exponential time, but there are clever algorithms that run in polynomial time (n3). These are all problems in P.

NP stands for Non-Deterministic Polynomial. Physicists have names like quark, gluon, and black hole; we’re stuck with “non-deterministic polynomial.” We really need to work on branding! NP is the class of all problems where, if someone showed you a valid solution, you could check it in polynomial time. Solutions are efficiently verifiable, even if they aren’t efficiently findable.

A famous example is factoring. I give you a 1,000-digit number and ask for its prime factors. To this day, we don’t know any polynomial algorithm running on a classical computer to solve this. Brute-force trial division for a 1,000-digit number would take longer than the age of the universe. The cleverer methods used by agencies like the NSA still scale exponentially; they can handle 1,024-bit numbers, but likely not 4,096-bit numbers.

However, if someone claims they know the factors, it’s obvious how they can convince you: they just show you the factors. You or your computer can multiply them together to check if they match and are prime. That puts factoring into NP.

The P vs NP problem simply asks: is every problem in NP also in P? If you can efficiently verify a solution, does that mean you can also efficiently find it?

Every P problem is an NP problem by definition. But are the two classes equal? Explaining this to people, you sometimes have to convince them why it’s even a question. Of course recognizing a solution can be easier than finding it! Hundreds of people could check Andrew Wiles’s proof of Fermat’s Last Theorem, but only Andrew Wiles could find it. Millions can enjoy a symphony, but very few can compose one.

If we were physicists, we would have declared P ≠\neq NP to be a law of nature and given ourselves Nobel Prizes for the discovery. If it later turned out P = NP, we would give ourselves more Nobel Prizes for overthrowing the law! But because theoretical computer scientists are a breed of mathematician, we have to call it a conjecture because we don’t have a proof. Problems like primality testing once seemed like they were in NP but not P, until we discovered they were in P after all. The conjecture remains that there are some NP problems that really aren’t in P.

When quantum computing came along, it added a new layer of subtlety. In quantum computing, we talk about a class called BQP, which stands for Bounded-Error Quantum Polynomial Time. Think of it as the quantum generalization of P—the problems efficiently solvable using a quantum computer.

P sits inside BQP, and P sits inside NP. But we don’t know if P = NP, we don’t know if P = BQP, and we don’t know the exact relationship between NP and BQP. It is consistent with everything we know that NP and BQP are incomparable, meaning each contains problems not in the other.

A holy grail of computer science since the 1960s has been finding efficient solutions to all problems in NP. When quantum computing arrived, people asked if NP is contained in BQP—could all NP-complete problems be solved by a quantum algorithm? Most of us think the answer is no. But BQP does contain certain NP problems—most famously factoring—that are of great importance to cryptography and are not suspected to be in P.

Jeroen Schreel: Why do we need quantum computing to solve part of those problems? What is the point?

Scott Aaronson: The original point was to give us a way to simulate quantum mechanics itself. There’s a famous quote from Richard Feynman: “Nature isn’t classical, damn it.” We didn’t get to choose the laws of physics; we discovered a hundred years ago that they are quantum mechanical.

Quantum mechanics is governed by an alien type of probability discovered in the 1920s. In classical physics, we assign probabilities from 0 to 1 to different states. The probability of a country winning the World Cup might be 30%, but never −30%, and certainly not −1\sqrt{-1}%. In quantum mechanics, you assign a number to every possibility called an amplitude. Amplitudes can be positive, negative, or complex numbers with real and imaginary parts.

When you make a measurement, amplitudes get converted to probabilities by the Born Rule, which states that the probability of an outcome equals the square of the absolute value of its amplitude. That yields a valid probability between 0 and 1. But while the system is unobserved, it evolves in terms of this giant list of amplitudes.

If an event like an electron arriving at a spot can happen one way with a positive amplitude and another way with a negative amplitude, those contributions can cancel each other out so the total amplitude is zero and the event never happens. If you block one of those paths, you get only the positive or negative contribution, which squares to a positive probability so the electron can show up. By decreasing the number of paths an electron can take, you can increase the chance that it reaches a spot.

The simplest answer to why we need quantum computers is that nature works this way. If we want to simulate nature properly, we should build computers based on this kind of probability.

Beyond that, quantum computers give us a window into nature at the atomic scale, and they can break public-key cryptography—which you want to know about if you use encryption or own cryptocurrencies.

Personally, my number one reason for wanting a quantum computer is to disprove the people who said quantum computing was impossible! It would be the most dramatic test of quantum mechanics itself that we will ever see.

Since the 1920s, quantum mechanics has passed every experimental test designed for it. Popular articles frequently report experiments uncovering “new weirdness,” but it’s just the same old weirdness over and over. Once you accept quantum mechanics, you can predict the outcomes of these experiments; for a hundred years, the result has always been “quantum mechanics is true.”

Yet many people, including Einstein, believed the theory was provisional and couldn’t be the final answer because it tells you the mathematical formalism to calculate probabilities rather than describing how the world “really” is.

There are a few responses to this century-long debate. Niels Bohr, Werner Heisenberg, and the Copenhagen interpretation essentially said to deal with it—you aren’t entitled to a picture of what’s behind the curtain, only predictions of experiment outcomes.

The Many-Worlds interpretation says to bite the bullet: the giant list of amplitudes is reality. If that means reality keeps branching into innumerable worlds that are all equally real, then that’s what reality is.

A third response is that quantum mechanics must break somewhere between the microscopic scale and everyday life, restoring our intuitive picture where objects have definite properties even when unobserved.

A quantum computer would be a device with millions or billions of particles in a superposition state where quantum behavior is essential to its operation. To understand how Shor’s algorithm factors a number, you can’t talk about individual particles; you have to talk about a wave function involving 21,000,000 parameters. It is the biggest escalation of quantum nature toward the human scale short of creating Schrödinger’s cat or putting human minds in superposition.

David Deutsch, one of the founding fathers of quantum computing alongside Feynman, wanted to force everyone to accept the Many-Worlds interpretation. In the early 1980s, long before Shor’s algorithm, he proposed running a conscious AI on a quantum computer and measuring it in a way that depended on interference between two mental states. That would force everyone to admit that two different mental states of a conscious being existed in superposition.

Jeroen Schreel: What do you think would happen if we put AI on quantum computers?

Scott Aaronson: If you run an AI in a superposition of asking it two different questions and engineer things to see interference between those branches, you will see the interference that quantum mechanics predicts. My bet is on quantum mechanics continuing to be true—that’s been a 100% winning bet for a century.

Building a scalable quantum computer won’t resolve the metaphysical debate between Many-Worlds and Bohmian mechanics, but it will empirically rule out the perspective that quantum mechanics breaks at larger scales.

I say to confident skeptics: I hope you’re right, because participating in the biggest revolution in physics in a hundred years would be awesome! Unfortunately, my guess is we’ll see the boring outcome that quantum computers work like the theory says they will.

That is the scientific case for building them, similar to the case for the Large Hadron Collider or the James Webb Space Telescope. The case that actually secured the funding over the last 20 years was the business case—that quantum computers will solve business problems faster. There is some truth to that, but it was never my main motivation. I get annoyed when that case relies on flagrant misrepresentations of what quantum algorithms can do.

As for whether quantum computers will enhance AI, that’s a harder question. Grover’s algorithm, discovered shortly after Shor’s algorithm, gives a quadratic speedup for unstructured search—reducing N steps to N\sqrt{N}​ steps. That applies to a wide range of tasks in AI and machine learning.

However, unlike Shor’s exponential speedup, Grover’s speedup is only quadratic. It doesn’t turn an exponential problem into a polynomial one; 21000 steps becomes 2500 steps, which is better, but still huge. Because the speedup is modest, it will take much longer for Grover’s algorithm to beat classical solutions once you factor in the hardware overhead of a quantum computer.

Many claims of exponential quantum speedups for AI problems have since been dequantized by advances in classical algorithms. Other exponential speedups exist for extremely specialized tasks, but it’s unclear if those tasks are useful in practice. Whether there are practical quantum speedups for classical AI remains an active research question.

Whatever we do in quantum computing must compete against the staggering progress in classical AI. Simulating protein folding was once considered a prime candidate for a quantum advantage, but AlphaFold 3 gets incredible results using classical AI. The bar for quantum computing is higher now, though I expect we will clear it for simulating quantum mechanics itself.

Jeroen Schreel: Do you have an idea of how far we are from a functioning quantum computer?

Scott Aaronson: For many years my standard answer was that if I could predict timelines, I’d be a rich investor instead of a professor! Since then, many quantum computing startups have gone public, and several of my friends have gotten rich from equity. Given recent advances—devices with over 100 qubits achieving 99.9% two-qubit gate fidelity—we are paper-proven past the point where error correction should become a net win.

If we can scale this up by a few orders of magnitude, we ought to start threatening cryptography. It feels like nuclear fission around 1939 or 1940: we don’t know the exact year, but it is now an engineering problem depending on funding, effort, and mundane obstacles.

Neutral atoms, trapped ions, and superconducting qubits are radically different architectures running neck-and-neck. Billions of dollars are flowing in from companies like Google, IBM, and Amazon, as well as startups and governments in the US, EU, and China. Barring a surprising showstopper, it’s hard to see how we don’t get to fault-tolerant devices within the next 5 to 10 years.

Jeroen Schreel: I should start investing as well!

Scott Aaronson: I don’t know how much of it is already priced in by now—my distaste for those questions is why I resisted investing for so long!

Jeroen Schreel: Well, Scott, I feel like we could keep going, but you should probably go have lunch.

Scott Aaronson: That’s a fair point!

Jeroen Schreel: This was Apple Finch Pudding. I want to thank Scott Aaronson for all the information. Let’s meet again for the next episode.

Relevant Papers