Can Quantum Computers Beat Classical Ones?

In a basement lab in Santa Barbara, a chip smaller than a fingernail sits at a temperature colder than deep space, colder than the space between galaxies, colder than almost anywhere else in the known universe. Superconducting loops etched into its surface hold fragile quantum states — bits that are not quite 0, not quite 1, but something the mathematics insists is genuinely both. Researchers ask this chip to perform a task with no practical use whatsoever: sampling from the output of a random quantum circuit. A classical supercomputer, they claim, would need thousands of years to simulate what the chip does in minutes. This claim — first made loudly in 2019 by a Google team, contested ever since, refined and re-contested — sits at the center of one of the strangest unresolved questions in all of science.

The strangeness is this: we do not know, in any rigorous mathematical sense, whether quantum computers can do anything that classical computers fundamentally cannot. We have spectacular candidate evidence — algorithms, experiments, complexity-theoretic arguments — that all point the same direction. We do not have proof. And the missing proof is not some minor technical lemma waiting to be tidied up. It is arguably the deepest open question in theoretical computer science after p-versus-np itself, and the two questions are cousins, born of the same unresolved anxiety about what computation truly is.

Every popular article about quantum computing promises revolution: unbreakable codes broken, drug discovery accelerated, financial markets transformed. Almost none of them mention that the entire edifice rests on an unproven mathematical conjecture. This essay is about that conjecture — what it says, why it has resisted proof for forty years, and what it would take to finally settle it.

State it precisely, and the precision itself is revealing. In complexity theory, P/BPP/BQP name classes of decision problems sorted by the resources needed to solve them. P is the class solvable by an ordinary deterministic computer in a number of steps that grows only polynomially with input size — the realm of the tractable. BPP allows the classical machine to flip coins, tolerating a small chance of error, and is generally believed (though this too is not proven) to equal P for all practical purposes, since randomness seems to buy little extra power. BQP — bounded-error quantum polynomial time — is the class of problems a quantum computer built from qubits and quantum gates can solve efficiently, again tolerating bounded error.

The open question, in its sharpest form, is whether

that is, whether there exists some problem quantum computers solve efficiently that classical computers, even randomized ones, provably cannot. We strongly suspect the answer is yes. We have not proven it. We cannot currently rule out the possibility that BPP = BQP — that every quantum algorithm, however clever, can be shadowed by some classical algorithm running in comparable time, using a trick nobody has yet discovered.

Why would this be hard to prove? Because proving BPP ≠ BQP requires proving a lower bound: a mathematical guarantee that no classical algorithm, however ingenious, however unexpected, can solve some specific problem quickly. Complexity theory is extraordinarily good at proving upper bounds — here is an algorithm, it runs fast, done. It is notoriously bad at proving lower bounds, because a lower bound requires reasoning about the space of all possible algorithms, including ones nobody has thought of yet, and ruling every single one of them out. This is exactly the same wall that has stopped P vs NP from being resolved for over fifty years. BPP vs BQP is a structurally similar wall, one level up, involving the extra ingredient of quantum mechanics itself.

An answer, if it ever comes, would look like one of two things. Either a proof that some explicit problem — ideally one already suspected, like factoring or a variant of the recursive Fourier sampling problems used in early separations — cannot be solved by any classical algorithm running in polynomial time, even with randomness, even with any conceivable clever restructuring. Or, far more surprisingly, a proof (or overwhelming practical demonstration) that every quantum algorithm can be classically simulated efficiently, collapsing the hierarchy and rendering "quantum speedup" a mirage for polynomial-time computation, though quantum computers might still be faster by huge constant factors or polynomial degree — useful, but not the qualitative leap the field advertises.

This is why the question is properly a question about the limits of knowledge, not merely a technical gap. It sits inside a nest of unresolved problems about computation's ultimate boundaries — P vs NP, the nature of uncomputable functions, even questions about whether general intelligence is itself a computational phenomenon — and it may be no easier to resolve than any of them.

Despite the unresolved core, an enormous amount is actually known, built over ninety years of quantum mechanics and forty years of quantum computing theory. It's worth walking through the story properly, because the settled science is what makes the open question so tantalizing rather than merely academic.

The tale begins with quantum entanglement, the phenomenon Einstein, Podolsky, and Rosen flagged in 1935 as apparently absurd and which Einstein himself called "spooky action at a distance." Two particles can be prepared so that measuring one instantly determines the correlated outcome of measuring the other, no matter how far apart they are, in a way that cannot be explained by any classical hidden variable theory obeying locality — a fact proven rigorously by John Bell in 1964 and confirmed experimentally again and again, culminating in the loophole-free Bell tests of 2015 and the 2022 Nobel Prize to Aspect, Clauser, and Zeilinger. Entanglement is not merely correlation; it is a resource, and it is the resource quantum computers spend to do things classical bits cannot.

A single qubit, unlike a classical bit, can exist in superposition — a state $\alpha|0\rangle + \beta|1\rangle$ with complex amplitudes satisfying $|\alpha|^2+|\beta|^2=1$. Put $n$ qubits together and entangle them, and the joint state lives in a space of $2^n$ complex amplitudes. This exponential blowup is the entire source of quantum computing's promised power, and also the entire source of the difficulty in simulating it classically — a state of 50 entangled qubits requires, in the crudest classical description, more numbers than there are grains of sand on Earth.

The theoretical foundations were laid by Richard Feynman in 1981, who observed that simulating quantum mechanics with classical computers seemed to require exponential resources, and wondered aloud whether a computer built from quantum components might simulate quantum systems efficiently instead — turning an apparent curse into a tool. David Deutsch formalized the quantum Turing machine in 1985, and the abstract model has since been shown, through the quantum circuit model, to be equivalent and tractable: any quantum algorithm can be built from a small universal set of one- and two-qubit gates, much as classical circuits are built from AND, OR, and NOT.

For a decade quantum computing remained a beautiful curiosity with no killer application. Then, in 1994, Peter Shor found one. Shor's algorithm factors large integers, and finds discrete logarithms, in polynomial time on a quantum computer — a problem for which no classical polynomial-time algorithm is known, and upon whose presumed classical hardness the entire edifice of RSA public-key cryptography depends. Shor's algorithm works by turning factoring into a period-finding problem, then exploiting the quantum Fourier transform to extract that period using interference among exponentially many amplitudes computed "in superposition" — a genuinely quantum trick with no classical analogue. It was Shor's algorithm, more than any experiment, that convinced the world quantum computing might matter.

A second landmark, Grover's algorithm (1996), searches an unsorted database of $N$ items in roughly $\sqrt{N}$ steps rather than the $N$ steps a classical computer needs — a quadratic rather than exponential speedup, but one that is provably optimal: no quantum algorithm can do better, a rare case where both the upper and the matching lower bound are rigorously established. Grover's algorithm is important precisely because its speedup is modest and proven, in contrast to Shor's, whose speedup is dramatic but rests on the unproven classical hardness of factoring.

This distinction is the seed of everything that follows. Some quantum speedups (Grover's) come with airtight proofs, because they are proven relative to a idealized "oracle" model where you only count queries to a black box, and information-theoretic arguments bound how much an oracle can reveal. Other, much more dramatic speedups (Shor's) are conditional: they are faster than every known classical algorithm, but nobody has proven that a fast classical factoring algorithm cannot exist. The gap between "conditionally faster" and "provably faster" is precisely the gap this whole essay is about.

The picture the field believes — dashed lines and all — places BQP strictly between BPP and PSPACE, overlapping NP in complicated, unproven ways (BQP is not believed to contain all of NP, and vice versa; the two classes seem incomparable). Every boundary drawn with confidence in popular accounts is, on close inspection, drawn with a dashed line in the actual mathematics.

Here is where the settled story runs out and the frontier begins. There are, broadly, three separate cracks in the foundation, and it is worth being honest about each.

The first crack: no unconditional separation from classical computing is known for any problem believed practically important. Shor's algorithm is fast. But "fast" is measured against the known classical algorithms — the best is the general number field sieve, running in sub-exponential but super-polynomial time. Nobody has proven that a polynomial-time classical factoring algorithm cannot exist; it is merely that generations of very smart number theorists have failed to find one, which is suggestive but is not a theorem. If someone tomorrow found a classical polynomial-time factoring algorithm — not impossible, merely believed extremely unlikely — Shor's algorithm would still work exactly as advertised, but the case for quantum computers offering a fundamental, provable advantage over classical ones would lose one of its two central pillars.

The second crack: the unconditional separations we do have are for problems nobody cares about. This is the domain of "quantum supremacy" or "quantum advantage" experiments, and it deserves unpacking, because it is both the strongest rigorous evidence for a real separation and, simultaneously, evidence for essentially nothing of practical use.

Theorists including Scott Aaronson, Alex Arkhipov, and others constructed specific sampling problems — Boson Sampling (2011), Random Circuit Sampling — for which they could actually prove something rigorous, conditional on complexity-theoretic assumptions somewhat weaker and more specialized than "P ≠ NP." The proof structure is: if a classical computer could efficiently sample from the same probability distribution a certain random quantum circuit produces, then something believed false in complexity theory (roughly, that the polynomial hierarchy collapses to a low level) would have to be true. This is a real theorem, and it is genuinely impressive, but notice what it does not say. It does not directly prove BQP ≠ BPP. It proves a conditional statement about a specific, practically useless sampling task, resting on a different unproven conjecture (the non-collapse of the polynomial hierarchy) that is itself unresolved, though widely believed.

Google's 2019 Sycamore experiment and IBM's competing claims, and China's Jiuzhang photonic experiment (2020) and Zuchongzhi superconducting device, were attempts to demonstrate this gap empirically: run the sampling task on real quantum hardware, argue no classical supercomputer could reproduce the output distribution in any reasonable time, and thereby claim an experimental instance of quantum advantage. Each claim has been followed, sometimes within months, by classical algorithmic improvements narrowing or in some cases nearly closing the gap. IBM researchers and others showed that with cleverer tensor-network simulation methods and enough supercomputer time, Google's original 2019 benchmark could be matched far faster than the "10,000 years" headline suggested — down to days, and later disputed further. This is not fraud or failure; it is the normal, healthy churn of an adversarial scientific contest, and it illustrates something important: "quantum advantage" as currently demonstrated is an empirical, moving-target claim about specific hardware and specific classical algorithms at a specific moment in time, not a mathematical proof of anything permanent.

The third crack, the deepest one, is that we do not even know how to prove BPP ≠ BQP relative to no oracle at all, i.e., "in the real world." Complexity theorists have proven oracle separations — in an idealized world where algorithms are only allowed to query some black-box function, quantum algorithms can be proven to need exponentially fewer queries than classical ones for certain contrived problems, starting with Deutsch-Jozsa (1992), Simon's algorithm (1994, the direct inspiration for Shor), and continuing through modern examples like the Forrelation problem. These are genuine, unconditional mathematical theorems. But oracle separations are a notoriously unreliable guide to "real" complexity class relationships — history is littered with statements provably true relative to one oracle and provably false relative to another (the Baker-Gill-Solovay result of 1975 first demonstrated this pathology for P vs NP), meaning oracle results cannot, even in principle, resolve the unrelativized question. It's a permanent structural limitation of the proof techniques available, sometimes called the "relativization barrier," and quantum complexity theory inherits it fully.

So the honest summary is: we have overwhelming circumstantial evidence, several genuinely rigorous conditional theorems, dramatic and repeatedly-defended experimental demonstrations on contrived tasks, and precisely zero unconditional proof that quantum computers are more powerful than classical ones for any problem anybody outside a complexity theory seminar would call practically important.

Given the standoff, what do researchers actually believe, and what are they betting on? There is broad but not universal consensus, distributed roughly across three camps.

Camp one: quantum advantage is real and provable, we just haven't found the proof yet. This is the mainstream position among quantum information theorists — Scott Aaronson, John Preskill, Umesh Vazirani among the most vocal advocates. Their confidence rests on the sheer structural weirdness of quantum interference: amplitudes can cancel as well as reinforce, in a way that seems to require tracking correlations across exponentially many basis states simultaneously, and no classical trick for compressing this has ever been found despite decades of trying, including strong "no-go" results (like the Gottesman-Knill theorem, which shows that a restricted class of quantum circuits, those built only from Clifford gates, actually can be simulated efficiently classically — meaning the hardness is not "quantumness" in general but specifically the non-Clifford resources, sometimes called "magic," that a circuit contains). This last point is important and often missed in popular writing: we know precisely which quantum resources are classically simulable and which are not, at least for large classes of circuits, via the stabilizer formalism and its extensions. The frontier of hardness is being mapped out gate by gate.

Camp two: quantum advantage might be an illusion of insufficiently clever classical algorithms. This is a minority position, but not a fringe one, and it deserves respect rather than dismissal. Gil Kalai, an Israeli mathematician, has argued for years that noise in real quantum devices might be a fundamental obstruction rather than an engineering nuisance — that as you scale up qubits, error rates might not merely need suppression but might scale in a way that makes fault-tolerant quantum computation impossible in principle, not just difficult in practice. If Kalai is right, and near-term "quantum advantage" experiments are being fooled by their own imperfections (noise smoothing distributions into ones that happen to look "hard" but are secretly easy, or classical simulability hiding behind computational shortcuts nobody has found yet), the entire program could stall not at BQP ≠ BPP but at the much earlier hurdle of whether large-scale fault-tolerant quantum computers can be built at all. This connects the question to engineering and to decoherence as much as to pure complexity theory. Most researchers think Kalai's specific noise-model arguments are not correct as stated — experiments have shown error rates decreasing as predicted under quantum error correction thresholds, notably Google's 2023 and 2024 results demonstrating that logical qubit error rates fall as more physical qubits are added, crossing the long-sought "break-even" point. But the fact that this camp exists, and includes serious mathematicians rather than cranks, is itself evidence of how open the underlying question remains.

Camp three: the truth is somewhere subtler — quantum computers offer real but bounded advantage, not the science-fiction "solve everything exponentially faster" story. This is arguably the most empirically grounded position. We already know, rigorously, that quantum computers do not solve NP-complete problems in polynomial time via brute force the way headlines sometimes imply — Grover's algorithm gives a quadratic, not exponential, speedup for unstructured search, and there is a proven oracle result (Bennett, Bernstein, Brassard, Vazirani, 1997) that quantum computers cannot solve NP-complete problems via black-box search faster than roughly $\sqrt{N}$, ruling out a certain broad class of hoped-for shortcuts. The dramatic exponential speedups we know about — Shor's algorithm chief among them — exploit very specific algebraic structure (the hidden subgroup problem, essentially, exploiting Fourier analysis over abelian groups) rather than brute-force parallelism over an entire solution space, a common misconception. Quantum computers are not magic parallel universes computing all possibilities at once for free — that folk-physics picture, though evocative, misleads about where the actual power comes from. It comes from interference patterns that must be engineered so wrong answers cancel and right answers reinforce, and engineering that cancellation is only known to work for problems with the right hidden structure. Under this view, quantum advantage is real, provable in restricted domains, but likely far narrower in scope than 1990s enthusiasm suggested — a specialized tool, not a universal accelerant, echoing the way the debate over P vs NP increasingly focuses not on "is P=NP" but on the fine structure of exactly which problems resist which techniques.

What would actually resolve this, and on what timescale might we expect movement?

On the pure mathematics side, a full unconditional proof that BPP ≠ BQP would very likely require first resolving, or at least making serious progress on, the broader landscape of unproven separations in complexity theory — a landscape that includes P vs NP. Many complexity theorists suspect these problems are linked at a deep level: proving strong-enough classical lower bounds (showing some explicit function requires large classical circuits) is a prerequisite tool for essentially every major unresolved separation, quantum or classical, and such lower bounds have proven ferociously difficult to establish for forty years, hitting formal "barriers" (relativization, natural proofs, algebrization) that show entire classes of proof technique cannot possibly work. A proof of BPP ≠ BQP, in other words, may require an entirely new mathematical technology not yet invented — this is not a problem where we can currently see the shape of the missing argument, the way (for instance) mathematicians could see roughly what a proof of Fermat's Last Theorem might need decades before Andrew Wiles supplied it. There is no comparable roadmap here. Some theorists think we might make partial progress within a decade or two — stronger conditional separations, more restricted unconditional ones, sharper characterizations of exactly which circuit families are classically simulable. Nobody credible predicts a full unconditional resolution on any specific timeline; it may take generations, or it may never come, in the same way P vs NP has now outlasted the careers of the theorists who first posed it.

On the practical, empirical side, the path is more concrete and the timeline nearer. The decisive move would be a genuinely useful computation — not a contrived sampling task, but something like a chemically meaningful molecular simulation, or an optimization result of real economic value — performed on a quantum computer, verified against experiment or trusted theory, where all serious attempts at classical replication using the best available algorithms and the largest available supercomputers fail even after years of subsequent effort to catch up. This is different from "supremacy" experiments precisely because it would matter even to someone who doesn't care about complexity theory. Companies and national labs — Google, IBM, Quantinuum, IonQ, PsiQuantum, and government programs in the US, China, and the EU — are racing toward exactly this milestone, sometimes called "quantum utility" or "commercial advantage," as distinct from the narrower academic "supremacy" claim. IBM's 2023 utility-scale experiments on 127-qubit processors, simulating certain quantum magnetism models beyond brute-force classical reach (though later matched by improved classical tensor-network methods, again illustrating the shifting target), are an early skirmish in this longer war. Most serious estimates place a durable, uncontested, practically meaningful demonstration somewhere in the 2030s, contingent entirely on progress in quantum error correction — the single largest engineering bottleneck, since useful algorithms like Shor's require millions of high-quality physical qubits assembled into far fewer, much more reliable "logical" qubits, and current devices have on the order of hundreds to a few thousand noisy physical qubits.

There is also a third, hybrid form of evidence that matters: continued failure of classical algorithms to catch up despite serious, well-funded effort to do so. Each time a classical team narrows the gap on a supremacy claim and the quantum side responds by scaling further, the pattern of results, even without a proof, shifts the Bayesian credence of working scientists. This is not proof. It is the same kind of accumulating circumstantial confidence that convinced most number theorists the Riemann Hypothesis is true long before (if ever) anyone proves it — a sociological and empirical form of near-certainty that coexists, uncomfortably but honestly, with acknowledged mathematical ignorance.

The stakes reach in three directions.

For technology, the stakes are almost absurdly concrete: the security of the internet. RSA encryption, and much of elliptic-curve cryptography, rests on the presumed classical hardness of factoring and discrete logarithms — precisely the problems Shor's algorithm solves efficiently, given a sufficiently large fault-tolerant quantum computer. Governments and standards bodies are not waiting for the theoretical question to resolve; the U.S. National Institute of Standards and Technology finalized the first post-quantum cryptography standards in 2024, migrating critical infrastructure toward lattice-based schemes believed (though again, not proven) hard for both classical and quantum computers. This is a striking case where practical policy has raced ahead of theoretical certainty, hedging against a mathematical possibility nobody can rule out.

For science, resolving BQP versus BPP would settle something deeper than a technical classification — it would tell us whether the universe, at bottom, computes in a fundamentally richer way than any classical machine could match, or whether quantum mechanics' apparent computational extravagance is, for the purposes of what can actually be computed rather than merely described, ultimately tameable by classical means. This bears directly on the Church-Turing thesis and its physical extensions: the strong Church-Turing thesis conjectures that any physically realizable computation can be simulated efficiently by a probabilistic Turing machine. If BQP strictly exceeds BPP, nature itself violates this — physics computes things classical mathematics, running on classical hardware, structurally cannot keep pace with, however much time you give it (short of exponential time, where classical computers can always simulate quantum ones in principle, since BQP is known unconditionally to sit inside PSPACE). That would be a statement about the ultimate texture of physical law, not merely a fact about engineering.

For self-understanding, the question sits adjacent to some of the strangest frontiers in contemporary science. If quantum mechanics grants nature genuine computational powers beyond classical reach, this reopens old, mostly dormant questions about whether biological information processing — including cognition — might exploit similar resources, questions raised (controversially, and mostly rejected by mainstream neuroscience) by Roger Penrose and Stuart Hameroff regarding microtubules and quantum effects in the brain. Most researchers remain skeptical that warm, wet biological tissue can sustain the coherence needed for quantum computational advantage, and this remains a fringe hypothesis rather than a mainstream research program. But its mere existence shows how the unresolved status of quantum advantage echoes outward into questions about the nature of mind, paralleling debates in the search for genuine machine intelligence about whether computation of any kind, classical or quantum, could ever amount to understanding rather than mere symbol manipulation. Nobody claims quantum computing settles that debate. But the fact that we don't even know the computational boundary of quantum mechanics leaves an open door that speculation, responsibly and irresponsibly both, continues to walk through.

The chase has been carried by a relatively small number of theorists, physicists, and engineers, moving in and out of pure mathematics and hands-on laboratory work.

physicist[Peter Shor|b. 1959|Mathematician at Bell Labs whose 1994 factoring algorithm gave quantum computing its first practically alarming application, and remains the sharpest evidence — though not proof — that BQP escapes classical reach]

physicist[Gil Kalai|b. 1955|Mathematician and prominent skeptic, arguing that noise may fundamentally, not merely practically, obstruct large-scale fault-tolerant quantum computation]

Between and around these names sit dozens of others essential to the story: David Deutsch, who formalized the quantum Turing machine; Umesh Vazirani and Ethan Bernstein, whose 1993 work founded quantum complexity theory rigorously and proved the first quantum-classical oracle separations; Daniel Gottesman and Emanuel Knill, whose theorem carved out exactly which quantum circuits are classically simulable; Dorit Aharonov and Alex Arkhipov, architects of much of the sampling-based hardness program; and the large experimental teams at Google, IBM, USTC in China, and Quantinuum, whose engineers wrestle daily with the decoherence and calibration problems that stand between today's noisy devices and the fault-tolerant machines the theory demands.

Stand back and the shape of the question becomes almost beautiful in its honesty. We have built machines that do something no classical machine, as far as anyone can demonstrate with total rigor, can efficiently replicate — and we cannot prove that this is actually true. We are in the position of a physicist confident in a law of nature without a full derivation from first principles, running experiments that keep confirming the prediction, while knowing that "keeps confirming" is not the same word as "proves."

This is not embarrassing. It is, in fact, exactly the condition of frontier science: enough structure to know precisely what is missing, not enough to supply it. The gap between BQP and BPP sits in excellent company, beside P vs NP and beside the deepest puzzles of computability theory, as one of the load-bearing unknowns of the discipline — a question whose resolution, whenever it comes, will not merely settle an academic dispute but will tell us something about what kind of universe we live in, computationally speaking.

Several threads remain conspicuously, productively unresolved:

• Is there any unconditional proof, free of complexity-theoretic assumptions, that any practically meaningful problem is in BQP but not BPP?
• Does fault-tolerant quantum computation scale as theory predicts, or does noise impose a fundamental — not merely engineering — ceiling, as Kalai and a minority of skeptics contend?
• Can classical algorithms (tensor networks, improved simulation methods) keep permanently pace with each new generation of "supremacy" hardware, or will a durable, uncatchable gap finally open?
• Is the apparent kinship between BQP vs BPP and P vs NP a deep mathematical connection, or a surface analogy that will resolve on entirely different timescales and by entirely different techniques?
• If quantum advantage is eventually proven narrow — confined to problems with specific algebraic structure — what does that imply about the true, more modest shape of quantum computing's promised revolution?

Ask the tutor: If someone discovered tomorrow a fast classical algorithm for factoring integers, what would actually be left of quantum computing's claim to power — and how would you go about checking whether such a discovery, hypothetically announced, was real?