Peter Shor showed in 1994 that a quantum computer could factor large numbers and compute discrete logarithms in polynomial time, problems he described as “generally thought to be hard on a classical computer” and as the basis of several proposed cryptosystems. Thirty-two years later, the list of problems with proven or strongly evidenced large quantum speedups is still short. It contains factoring and related algebraic problems, the simulation of quantum systems such as molecules and magnets, and a family of sampling tasks that researchers first applied in 2025, to certify random numbers.
Speedups for other problems are smaller or unproven. For unstructured search, the speedup is quadratic. Charles Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved in 1997 that no quantum algorithm can do better against a black box. Exponential speedups for linear algebra apply only when data can be loaded quickly and the user needs just a few numbers from the answer.
Large quantum speedups are best evidenced for algebraic problems such as factoring and for the simulation of quantum systems, while claimed speedups for optimization and for machine learning on ordinary data are mostly heuristic or have been matched classically. A buyer weighing a quantum application should ask which of these classes it belongs to before asking how many qubits it needs.
Kinds of speedup and kinds of evidence
Computer scientists compare algorithms by how their running time grows with the size of the input. Under an exponential speedup, a task with a classical cost that grows exponentially with input size gets a quantum cost that grows only as a fixed power of that size. A superpolynomial speedup is the broader case, in which the classical cost grows faster than any fixed power of the input size.
Shor’s algorithm gives a superpolynomial speedup for factoring. The best known classical method, the number field sieve, runs in subexponential time, slower than any fixed power of the input size but faster than an exponential.
A polynomial speedup shrinks the running time by a polynomial factor. A quadratic one, for example, turns N steps into about the square root of N, so a search that takes exponential time classically still takes exponential time.
A heuristic is a method that works on the instances someone has tested, with no proof that its advantage persists as problems grow. Dequantization is the design of a classical algorithm that matches a claimed quantum speedup, usually by giving the classical algorithm the same access to data that the quantum algorithm assumes. Ewin Tang set off the current wave of such results in quantum machine learning with a 2018 preprint on recommendation systems.
Few quantum speedups are proved outright. Sergey Bravyi, David Gosset, and Robert König proved, in a paper published in Science in 2018, that quantum circuits with a fixed number of layers of gates solve a specific problem that no classical circuit with a fixed number of layers can. Their bound covers classical circuits “composed of bounded fan-in gates,” in which each gate reads a limited number of inputs. They needed no unproved assumption, but the result is limited to such shallow circuits.
Proofs in the query model, in which an algorithm learns about its input only by asking a black box questions, are also unconditional. Such a proof applies only relative to the black box, so it does not rule out a faster algorithm that exploits the structure of a real problem.
Most other evidence is conditional on an unproved assumption. One kind is a proof that a problem is complete for BQP, the class of problems a quantum computer solves efficiently. A fast classical algorithm for a BQP-complete problem would yield fast classical algorithms for every problem in the class.
Robin Kothari and Rolando Somma of Google called BQP-completeness the “best evidence we can provide” in 2023. No one has yet proved that quantum computers can efficiently solve problems that classical computers cannot, they wrote.
The map, class by class
Each row in the table lists the largest speedup researchers have shown or strongly evidenced for a class of problems, the kind of evidence behind it, and a primary source.
| Problem class | Best known speedup | Kind of evidence | Source |
|---|---|---|---|
| Factoring and discrete logarithms | Superpolynomial over the best known classical methods, such as the number field sieve | Polynomial-time quantum algorithm, with classical hardness unproved | Shor, 1994 |
| Simulating quantum dynamics | Exponential, believed | BQP-complete | Kitaev, Shen and Vyalyi, 2002 |
| Ground-state energies in chemistry | No exponential speedup shown across chemistry | QMA-complete in the worst case, and dependent on a good starting state | Lee and co-authors, 2023 |
| Unstructured search | Quadratic, the proven maximum | Proof in the query model | Bennett and co-authors, 1997 |
| Linear systems of equations | Exponential, with input and output conditions | BQP-complete, with low-rank cases dequantized | Harrow, Hassidim and Lloyd, 2009 |
| Combinatorial optimization | Quadratic for search-based methods, superpolynomial for one structured problem | Proofs for structured cases, simulations and small experiments for heuristics | Jordan and co-authors, 2025 |
| Machine learning | Exponential on data from quantum systems, mostly heuristic on classical data | Proofs and experiments on quantum data, dequantization on classical data | Huang and co-authors, 2022 |
| Sampling | Exponential, conditional | Exact classical sampling would break a central complexity conjecture, and approximate hardness is conjectured | Aaronson and Arkhipov, 2011 |
Algebraic problems
Shor’s algorithm finds the period of a function, the interval after which its values repeat. Factoring an RSA modulus and computing discrete logarithms, the problem behind elliptic-curve cryptography, both reduce to finding such a period. The algorithm uses a quantum Fourier transform, a quantum version of the method that finds the frequencies in a signal, to extract the period from a superposition, a quantum state that combines all possible inputs.
Researchers call the general task the hidden subgroup problem. Sean Hallgren used the same approach to give a polynomial-time quantum algorithm for Pell’s equation, a problem in number theory. No polynomial-time classical algorithm is known for factoring, discrete logarithms, or Pell’s equation.
Oded Regev showed in work first presented in 2002 that an efficient quantum algorithm for the dihedral coset problem, a relative of the hidden subgroup problem over a non-commutative group, would yield quantum algorithms for some lattice problems. In August 2026, Daniel Simon of Amazon Web Services posted an unreviewed draft claiming such an algorithm, as Quantum Observer reported. On August 15, Aparna Gupte, Seyoon Ragavan, and Mark Zhandry posted “The ePrint:2026/1591 Quantum Algorithm Does Not Solve DCP,” a reply to the draft. Two days later, Yuchen Guo and Shuo Yang of Tsinghua University gave rigorous proofs of the draft’s lemmas and wrote that establishing them “does not by itself establish the correctness of the algorithm.” Simon has revised the draft several times, most recently on November 3, and added a note addressing the reply. He has not withdrawn it.
Estimates of the hardware needed to break public-key cryptography have fallen since 2019. Craig Gidney of Google Quantum AI and Martin Ekerå estimated in 2019 that RSA-2048 could be factored in eight hours with 20 million noisy physical qubits, in a paper later published in Quantum. In a May 2025 preprint, Gidney estimated that a 2048-bit RSA integer could be factored in less than a week with fewer than a million noisy physical qubits.
In a February 2026 preprint from Iceberg Quantum, Paul Webster and seven co-authors put the requirement for RSA-2048 at fewer than 100,000 physical qubits. They assumed a 0.1% physical error rate, a 1-microsecond cycle of error checks, and quantum low-density parity-check (qLDPC) codes, in a design where each physical qubit connects to others beyond its nearest neighbors. Researchers have since published lower counts, each for an attack that takes days or longer on hardware that no laboratory has yet shown, as Quantum Observer set out in its comparison of Shor’s algorithm estimates.
A Google-led team estimated in a March 2026 whitepaper that a 256-bit elliptic-curve attack needs fewer than 1,200 logical qubits and fewer than 90 million Toffoli gates. A logical qubit is an error-protected unit of quantum information spread across many physical qubits. Toffoli gates, three-qubit operations, account for much of the cost of an error-corrected computation.
Researchers at Sandia National Laboratories, Quantinuum, and NVIDIA measured how far today’s processors are from such attacks in a September 2026 preprint. They built a benchmark score, the quantum universal operation performance system (QUOPS), from the size of the largest useful circuits a machine can run and the speed at which it runs them. They set QUOPS targets for factoring RSA-2048 and for estimating the energy of FeMoco, the iron-molybdenum cofactor of the nitrogen-fixing enzyme nitrogenase. Against both, “current QUOPS scores are insufficient by roughly five orders of magnitude,” they wrote.
Quantum Observer ranked published estimates by gate count for fault-tolerant machines, which correct their own errors as they run. In that ranking, elliptic-curve attacks came ahead of every molecular ground-state estimate that Google researchers compiled in 2025. In its final transition plan, published October 27, 2026, NIST deprecates RSA and elliptic-curve algorithms after 2030.
Simulation of quantum systems
Richard Feynman proposed in 1982 that quantum systems be simulated on quantum hardware, since a classical description of many interacting particles grows exponentially with their number. Seth Lloyd showed in Science in 1996 that a quantum computer can efficiently simulate any system of locally interacting particles.
Any computation a quantum computer runs efficiently can be rewritten as the time evolution of such a system, using a circuit-to-Hamiltonian construction that turns a circuit into the energy function of a physical system. Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi set out the construction in their 2002 textbook. Simulating that evolution is therefore BQP-complete. A fast classical method for it would give a fast classical algorithm for every problem a quantum computer solves efficiently.
Finding the lowest energy of a quantum system, the ground-state problem behind most chemistry applications, is harder in the worst case. Julia Kempe, Alexei Kitaev, and Oded Regev proved the general problem, for qubits that interact in pairs, complete for QMA, a quantum analogue of NP. NP is the class of problems whose solutions a classical computer can check quickly. Bryan O’Gorman, Sandy Irani, James Whitfield, and Bill Fefferman later proved the same, in PRX Quantum in 2022, for the electronic structure of molecules with a fixed set of orbitals and a fixed number of electrons.
No efficient algorithm, quantum or classical, is expected for the hardest instances. Quantum chemistry algorithms therefore need a starting state that overlaps well with the true ground state.
Eighteen researchers, including John Preskill and Garnet Chan, examined that condition in a 2023 Nature Communications paper. They concluded that “evidence for such an exponential advantage across chemical space has yet to be found.” They wrote that polynomial speedups could still make quantum computers useful for ground-state chemistry.
Hardware teams have reported simulations that they say classical methods cannot match. On October 22, 2025, Google said that in its Quantum Echoes experiment, researchers measured an out-of-time-order correlator, a quantity that tracks how information spreads through a quantum system, on 65 of the 105 physical qubits of its Willow processor. The run took about two hours, and Google estimated that a classical supercomputer would need 13,000 times longer.
Google’s researchers, who published the result in Nature, called it verifiable on the grounds that another quantum computer or a natural quantum system can reproduce the measured value. They also wrote that a follow-up experiment on molecules, posted as a preprint, “is not yet beyond classical.”
In July 2026, IBM presented three preprints on experiments with its Heron processors as demonstrations of quantum advantage. Two were simulations of model quantum systems on up to 74 physical qubits, run with IBM by teams from Qedma, an Israeli maker of error-mitigation software, and Algorithmiq, a quantum software company. Qedma’s team wrote that leading tensor-network simulations, which use a classical technique for compressing quantum states, failed to converge. IBM wrote that classical groups produced “inconsistent predictions” for the quantity Algorithmiq’s team measured.
Quantum Observer compared the three preprints in August. As of November 2026, none of them, Qedma’s, Algorithmiq’s, or IBM and the University of Chicago’s, had been peer reviewed.
Unstructured search
Lov Grover published an algorithm in 1996 that finds a marked item among N unsorted items in about √N steps, where a classical search needs about N. Bennett and his co-authors proved the following year that no quantum algorithm can search a black box faster.
In the same paper, they showed that relative to a black box chosen at random, a quantum computer cannot solve every problem in NP in time much below 2^(n/2). For Boolean satisfiability, the problem of finding true-or-false values that make a logical formula true, Grover search cuts about 2^n steps to about 2^(n/2) with n variables, a count that still grows exponentially.
Ashley Montanaro extended quadratic speedups in 2015 to estimating averages by Monte Carlo sampling and to the backtracking searches inside exact solvers for constraint problems. Ryan Babbush and five Google colleagues wrote in PRX Quantum in 2021 that “quadratic speedups will not enable quantum advantage on early generations of such fault-tolerant devices unless there is a significant improvement in how we would realize quantum error-correction.” Error-corrected gates run so slowly that a quantum computer with only a quadratic speedup would overtake a classical one only on very long computations.
Linear algebra
Aram Harrow, Avinatan Hassidim, and Seth Lloyd published a quantum algorithm in 2009 for solving systems of linear equations, Ax = b, when the matrix A is sparse and well conditioned. A sparse matrix has few nonzero entries. In a well-conditioned system, small changes to b produce only small changes to x. The authors called the algorithm’s running time “an exponential improvement over the best classical algorithm” and showed that matrix inversion is BQP-complete.
Their algorithm prepares the solution as a quantum state, not as a list of numbers. Harrow and his co-authors framed the use case as estimating “the expectation value of some operator associated with x,” a single number computed from the solution.
Scott Aaronson set out the conditions for a real speedup in Nature Physics in 2015: fast loading of the vector b, a sparse or otherwise easy-to-apply matrix that is well conditioned, and a user who needs only a few numbers from the answer. A user who reads out the whole solution vector would spend time proportional to its length and lose the exponential speedup.
Researchers have matched several of these speedups classically by giving classical algorithms the same access to data. In her 2018 preprint, Tang designed a classical recommendation algorithm and showed that a leading quantum algorithm for the task “does not in fact give an exponential speedup over classical algorithms” when both have the same access to data. Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Tang, and Chunhao Wang extended the method in 2019 to a family of quantum algorithms for low-rank matrices, whose rows are all combinations of a few independent rows.
Exponential speedups are still possible where the input has a compact description and the output is a few numbers. Babbush, Dominic Berry, Kothari, Somma, and Nathan Wiebe showed in Physical Review X in 2023 that a quantum computer can simulate N coupled masses and springs using about log N qubits, and they proved that problem BQP-complete. Kothari and Somma wrote that real-world examples of the advantage remain to be found.
Optimization
Many combinatorial optimization problems, such as routing and scheduling, are NP-hard, meaning at least as hard as any problem in NP. The 1997 black-box result from Bennett and his co-authors is one formal reason researchers do not expect quantum computers to solve such problems in polynomial time.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann proposed the quantum approximate optimization algorithm (QAOA) in a 2014 preprint. QAOA is a heuristic that applies alternating layers of gates whose settings are tuned by a classical optimizer. Farhi and his co-authors analyzed its performance without proving a speedup over classical algorithms.
Researchers at JPMorganChase, Argonne National Laboratory, and Quantinuum published scaling evidence for QAOA in Science Advances in 2024. Ruslan Shaydulin and 28 co-authors reported that on the low autocorrelation binary sequences problem from signal design, “the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers.” Branch-and-bound solvers are a family of exact classical methods that prune their search. Combined with a quantum search step, QAOA had “the best empirical scaling of any algorithm” for that problem, they wrote.
The researchers estimated that scaling from noiseless simulations of up to 40 qubits. They also ran small instances on Quantinuum trapped-ion processors with an error-detection scheme built for the algorithm.
Stephen Jordan, Babbush, and seven co-authors at Google and partner institutions published decoded quantum interferometry (DQI) in Nature in October 2025. Their algorithm uses the quantum Fourier transform to convert an optimization task into a decoding problem, the task of correcting errors in a coded message. For approximating optimal polynomial fits over finite fields, they reported “a superpolynomial speedup over known classical algorithms.”
That problem has algebraic structure, the property behind Shor’s algorithm. Max-XORSAT, an optimization problem without that structure, is the task of choosing bit values that satisfy as many parity constraints as possible. On a max-XORSAT instance they constructed, DQI found an approximate optimum “significantly faster than general-purpose classical heuristics, such as simulated annealing,” the authors wrote. They added that “a tailored classical solver can outperform DQI on this instance.”
Machine learning
On data that come from quantum systems, researchers have proved and measured large advantages. Hsin-Yuan Huang and colleagues reported in Science in 2022 that for some tasks, quantum machines can learn about physical systems from exponentially fewer experiments than conventional approaches. They ran the demonstration on 40 physical superconducting qubits. A team led from the Technical University of Denmark reported in Science in September 2025 that it had used entangled light to learn a physical process with 11.8 orders of magnitude fewer samples than classical methods without entanglement need.
Those results belong with simulation and sensing, since the data are quantum from the start. In a second group of results, researchers construct the learning problem.
A quantum kernel method classifies data by measuring how similar data points are. Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme proved in 2021 that such a method classifies a constructed dataset accurately and that no classical learner can do much better than random guessing on it, assuming discrete logarithms are hard to compute classically. The quantum learner’s advantage depends on the algebraic problem that Shor’s algorithm solves.
On classical data, the evidence is mostly heuristic. In variational quantum models, a circuit’s settings are adjusted like a neural network’s weights. The optimization can stall on barren plateaus, regions where the training signal vanishes. M. Cerezo of Los Alamos National Laboratory and 11 co-authors collected evidence, case by case, in Nature Communications in August 2025 that many commonly used models free of barren plateaus “can also admit classical simulation,” provided some classical data are first collected from quantum devices.
Ryan Sweke and six co-authors established in Quantum in February 2025 the conditions under which random Fourier features, a classical sampling technique, efficiently dequantize variational quantum regression models. In a December 2025 benchmark in Scientific Reports, researchers who compared classical models with quantum models simulated in software found that the classical models scored highest on four of five public datasets.
In a review published in Frontiers in High Performance Computing on September 24, 2026, five researchers at two Italian universities examined 53 peer-reviewed quantum bioinformatics experiments. They found that 36 never ran on quantum hardware and that none explicitly demonstrated a quantum advantage. HSBC and IBM reported relative gains of up to about 34% in bond-trade predictions in a September 2025 preprint and suggested that hardware noise contributed. Quantum Observer summarized several of these results in May.
Researchers at Caltech, Google Quantum AI, MIT, and Oratomic compared memory instead of time. In an April 2026 preprint, Haimeng Zhao, Huang, and five co-authors proved an exponential advantage in machine size for some classification tasks on classical data. They wrote that loading the data dominates the running time, and they gave no fault-tolerant cost estimate.
Sampling
In a sampling task, a quantum computer outputs random bit strings from the probability distribution its circuit defines. In 2011, Scott Aaronson and Alex Arkhipov, and separately Michael Bremner, Richard Jozsa, and Dan Shepherd, showed that an efficient exact classical simulation of such tasks would imply that the polynomial hierarchy, a tower of complexity classes believed to be infinite, stops at its third level. Complexity theorists consider that outcome very unlikely. The hardness of approximate sampling, the version used in experiments, depends on further conjectures.
Classical researchers have matched several experiments based on these results. Google reported in Nature in 2019 that its Sycamore processor, with 53 working physical qubits, had performed such a task beyond classical reach. Feng Pan, Keyang Chen, and Pan Zhang reported in Physical Review Letters in 2022 that they had solved the same sampling problem with a tensor-network method running on GPUs.
In 2024, Changhun Oh, Bill Fefferman, and colleagues published in Nature Physics a classical algorithm that exploits photon loss in Gaussian boson sampling, in which experimenters send squeezed light through a network of beam splitters and count the photons that emerge. The University of Chicago wrote that the algorithm “performed better than some state-of-the-art GBS experiments in various benchmarks.”
Researchers from JPMorganChase, Quantinuum, and other institutions reported in Nature in March 2025 that they had used random circuit sampling to produce certified random numbers. They used Quantinuum’s H2-1 computer with 56 physical qubits and certified 71,313 bits of entropy against a restricted class of adversaries, under further assumptions. They verified the results classically on supercomputers running at a combined 1.1 × 10^18 floating-point operations per second. Their protocol depends on the classical hardness of earlier random circuit sampling experiments, they wrote.
In the July version of their preprint, IBM and University of Chicago researchers reported a doped Clifford sampling experiment on 97 physical qubits. Their circuits combined Clifford gates, which classical computers simulate easily, with 468 harder T gates. On August 13, Hidetaka Manabe and Feng Pan of the Singapore University of Technology and Design and Hanfeng Gu of NVIDIA reported computing the ideal amplitudes, which set the probability of each output, for all 2,051 of the experiment’s samples in 37.3 minutes on 256 GPUs.
Under two stated assumptions, their estimate of the experiment’s fidelity, a measure of how closely its output matched the ideal, was “numerically compatible with IBM’s fidelity lower bound,” they wrote. The three then joined the IBM and University of Chicago team, which revised its preprint on September 1 and 2. In the revision, the team reported a 64-qubit Clifford circuit, 73 layers deep, with 314 T gates, run on 76 physical qubits.
The case for heuristics
IBM treats quantum advantage as a question to settle by experiment. “We are now firmly in the quantum advantage era,” Jay Gambetta, director of IBM Research, said in IBM’s July 30 announcement. The Quantum Advantage Tracker, a community site that IBM introduced in November 2025, lists candidate experiments for classical researchers to attack. An entry is marked superseded once classical methods match it.
In the strongest version of this view, a heuristic that keeps beating classical solvers as problems grow is as useful as a proven speedup. Experiments published for classical researchers to attack are then the way to find one. Shaydulin’s team made a version of the case, writing that their results “provide evidence for the utility of QAOA as an algorithmic component.” With DQI, Jordan’s team showed that researchers are still finding new quantum algorithms for optimization.
Classical researchers have answered several such claims quickly. They matched the 2019 Sycamore experiment within three years and computed the amplitudes for IBM’s July 2026 samples within about two weeks, a check on IBM’s fidelity claim that stops short of reproducing the sampling task. Shaydulin’s team based its scaling evidence on noiseless simulations of up to 40 qubits. On their own test instance without algebraic structure, DQI’s authors reported that their algorithm beat simulated annealing but lost to a solver tailored to that instance.
A heuristic could still beat classical solvers on some problems. For a heuristic, the test of advantage is a published scaling comparison at growing problem sizes against the best classical solver tuned for the same instances.
Questions for a buyer
- Which of the classes in the table does the application belong to, and what kind of speedup is known for that class?
- Is the claimed speedup proved, conditional on a complexity assumption, or observed only on tested instances?
- How do the data get into the machine, and how many numbers does the user need out of it?
- Which classical method served as the baseline, and was it tuned for the same instances?
- At what problem size, logical-qubit count, and gate count does the quantum method overtake that baseline?
What would change the map
A polynomial-time classical algorithm for factoring would remove the speedup in the algebraic row. A fast classical method for simulating local quantum dynamics would remove the exponential speedup for every problem in BQP, since that simulation is BQP-complete.
In the other direction, an efficient quantum algorithm for the dihedral coset problem would extend the algebraic row to some lattice problems, the family behind ML-KEM (CRYSTALS-Kyber) and ML-DSA (CRYSTALS-Dilithium). Simon’s claim to have found one is unreviewed and disputed.
For optimization and machine learning, the confirming result would be a quantum heuristic that beats tuned classical solvers by a margin that grows with problem size, published with its data. For chemistry, it would be a fault-tolerant ground-state calculation on a molecule beyond classical reach. IBM has scheduled Starling, its first large fault-tolerant machine, for 2029 on its roadmap.
Until one of those results appears, the map has two well-evidenced rows for large and useful speedups, one for algebraic problems and one for quantum simulation. It also has a sampling row, where researchers have used quantum computers to certify random numbers.
