Marin Ivezic
The 10,000-year number, and what happened to it
In October 2019, Google reported in Nature that its 53-qubit Sycamore processor finished a sampling task in 200 seconds, and estimated that the fastest classical supercomputer of the day would need about 10,000 years for the same calculation. IBM published a rebuttal on its research blog within days: used differently, with more disk storage, the same machine could do the job in roughly 2.5 days. Later classical work narrowed the gap again.
Both sides were arguing honestly, and the argument taught the field something more durable than either number. The task Google chose had no commercial use. It was chosen because it was hard for classical hardware and natural for quantum hardware, and that combination is exactly what a quantum application needs. Almost no ordinary workload has it.
For anyone deciding whether to fund a quantum program, then, the useful question is narrower than “is quantum faster.” It is: which problems have the internal structure that quantum algorithms can exploit, and how good is the evidence in each case? We answer that below in four problem families, ordered by the strength of the evidence rather than by the volume of the marketing, and close with a screening test you can apply to your own workloads.
Three properties, one working criterion
A classical bit is either 0 or 1. A qubit, the quantum equivalent, can hold a weighted combination of both at once, called a superposition. Eight classical bits store one of 256 possible values; eight qubits hold a weighted combination of all 256 at the same time, with a number attached to each possibility.
Qubits can also be entangled, meaning their states are correlated in a way that has no classical equivalent. Measure one and you learn something about the other immediately, however far apart they are. Entanglement is what allows a quantum machine to represent relationships across many parts of a problem at once instead of one part at a time.
The third property does the real work, and it’s the one most often left out of executive briefings. Those weights attached to each possibility behave like waves, and waves interfere. Two contributions arriving in step reinforce each other; two arriving out of step cancel. A quantum algorithm is a sequence of operations arranged so that the wrong answers cancel each other out and the right answer is reinforced by the time you measure.
A quantum computer does not try every possibility and hand you the best one. You get a single measurement outcome per run, drawn from a probability distribution. The algorithm’s entire job is to shape that distribution before you look. If the problem has no exploitable pattern for interference to work on, a quantum computer gives you a very expensive random number.
The screening criterion
Computer scientists give the problems a quantum machine can solve efficiently a name: BQP, the class of problems solvable in reasonable time on a quantum computer with a bounded chance of error. BQP contains some problems that are hard classically, factoring among them. Most researchers believe it does not contain the NP-complete problems, the family where checking a candidate answer is easy but finding one seems to require searching an exponential space. Route planning across thousands of stops, general scheduling, and boolean satisfiability all sit there. Nobody has found a quantum algorithm that solves them efficiently, and few expect one.
So the criterion we teach first is this: a problem is a plausible quantum candidate when it has mathematical or physical structure that a known algorithm can turn into interference. Hidden periodicity qualifies. Quantum mechanics itself qualifies, since the hardware obeys the same rules as the thing being modelled. Large linear algebra sometimes qualifies. Brute-force search over an unstructured space qualifies only weakly, for reasons we get to below. Everything else is classical work, and will stay classical work.
Family one: hidden periodic structure
Peter Shor’s 1994 algorithm is still the strongest known result in the field. It factors large integers in polynomial time by converting factoring into a period-finding problem and using interference to extract the period. No classical algorithm comes close, which is why RSA and elliptic-curve cryptography, both built on that hardness, are on a clock.
The resource estimates are the part worth tracking, and they have moved sharply. In 2019, Craig Gidney and Martin Ekerå estimated that breaking a 2048-bit RSA key would take roughly 20 million noisy physical qubits running for about eight hours. In 2025, Gidney published a revised estimate in a preprint titled How to factor 2048 bit RSA integers with less than a million noisy qubits: fewer than one million physical qubits, running for under a week. The hardware didn’t change. The algorithms, the error-correction schemes, and the compilation techniques did.
That is roughly a twentyfold reduction in six years, and it explains why standards bodies stopped waiting. The United States National Institute of Standards and Technology published its first post-quantum standards in August 2024: ML-KEM (Kyber) for key establishment (FIPS 203), ML-DSA (Dilithium) for signatures (FIPS 204), and SLH-DSA (SPHINCS+) as a hash-based signature alternative (FIPS 205), with FN-DSA (Falcon) still in draft. NIST SP 800-57 Part 1 (Rev. 5) puts 112-bit security, which covers RSA-2048, at the end of its acceptable life in 2030; P-256, at 128-bit security, is not deprecated on that date. Agency transition timelines come from OMB guidance and the NSA’s CNSA 2.0 suite rather than from a NIST schedule.
For most organisations, this family is the only one that arrives as an obligation rather than an opportunity. You aren’t going to buy a quantum computer to factor anything. You are going to be asked, by regulators, insurers, and enterprise customers, what your migration plan is and when your cryptographic inventory was last updated. Those questions are already appearing in procurement questionnaires.
Family two: quantum systems simulating quantum systems
Richard Feynman made the argument in 1981, before anyone had built anything: if you want to simulate a quantum system, use a machine that is itself quantum. The reasoning is direct. Describing the electronic state of a molecule classically requires bookkeeping that grows exponentially with the number of electrons, so exact treatment stalls at very small molecules and everything larger relies on approximations. A quantum processor represents that state using qubits and obeys the same physics natively, so the exponential blow-up doesn’t appear in the same form.
This is the family with the clearest theoretical case for eventual advantage, and it’s where we would point a first pilot. The current demonstrations are honest about their size. In 2017, an IBM team led by Abhinav Kandala computed the ground-state energy of beryllium hydride on six qubits. In 2020, Google ran a 12-qubit Hartree-Fock calculation on Sycamore, pairing the chip with classical hardware. Both used the variational quantum eigensolver, or VQE: the quantum processor prepares a trial state and measures its energy, a classical optimiser adjusts the parameters, and the loop repeats until the energy stops falling.
None of those results beat classical chemistry software. They were validations that the pipeline works end to end. Industrial interest follows the same logic. Hyundai’s work with IonQ on lithium compounds for battery cathodes, and similar programs at several automakers, are positioning exercises: build the internal skill on problems that are currently small, so that the team is ready when the hardware can take a molecule that classical methods can only approximate.
One recent result sits on the boundary. In March 2025, a D-Wave team published work in Science claiming beyond-classical performance on the simulation of a specific quantum magnetic material, using an annealing processor. Within weeks, other groups posted classical simulations reproducing parts of the same result. That pattern, a quantum claim followed by a classical counterattack, has repeated often enough since 2019 that we treat it as the normal shape of progress rather than as embarrassment. The frontier moves on both sides, and the useful signal is where it settles after a year, not what the press release said.
Family three: unstructured search, and why quadratic isn’t enough
Lov Grover’s 1996 algorithm searches an unsorted collection of N items in about √N steps, where a classical search needs on the order of N. For a billion items, that’s roughly 32,000 steps instead of a billion. The speedup has been proved optimal: no quantum algorithm can do unstructured search faster.
Grover’s algorithm is also the most over-sold result in the field, and the arithmetic explains why. A quadratic speedup takes an exponential problem and leaves it exponential. A problem needing 2^n classical steps needs about 2^(n/2) quantum steps, which grows just as uncontrollably, only more slowly. Grover does not break NP-complete problems.
There’s a harder constraint underneath. In 2021, Ryan Babbush and colleagues at Google examined what quadratic speedups actually cost on error-corrected hardware. Error correction adds a substantial constant-factor slowdown to every operation, and Grover’s algorithm cannot be parallelised across machines the way classical brute-force search can. Their conclusion was that quadratic speedups are unlikely to produce practical advantage on realistic hardware, and that serious effort should go toward problems offering better-than-quadratic gains.
Their argument is a good filter to apply to any vendor claim. If the pitch rests on Grover, ask what the constant factors look like once error correction is included, and whether the classical baseline is a single machine or a cluster. We spend time on Grover in our teaching because it shows how interference works more clearly than any other algorithm, not because we expect it to earn its keep in production.
Family four: optimization, where the evidence is thinnest and the noise is loudest
Optimization is the pitch most executives hear first: routing, scheduling, portfolio construction, factory layout. It’s also the family where the gap between the marketing and the published results is widest.
Two approaches compete. Quantum annealing, commercialised by D-Wave, encodes a problem as an energy surface in which the lowest point corresponds to the best solution, then lets a physical system settle toward low energy while quantum effects help it move through barriers rather than only over them. On gate-based machines, the leading candidate is the Quantum Approximate Optimization Algorithm, or QAOA: a parameterised quantum circuit proposes candidate solutions and a classical optimiser tunes the parameters over repeated runs, in the same loop shape as VQE.
The demonstrations are real and small. At WebSummit in Lisbon in November 2019, Volkswagen ran a live routing system on a D-Wave machine that recalculated paths for nine buses in near real time. Financial institutions have run portfolio-selection trials at similar scale. What has not appeared, after roughly a decade of trying, is a case where a quantum optimiser consistently beats a good classical solver on a problem of commercial size. Where quantum results have looked strong, classical algorithms have usually caught up, sometimes because attention from the quantum community prompted someone to write a better classical solver.
Our blunt reading of the market: optimization is where quantum vendor claims outrun the published evidence by the widest margin, and buyers should treat any promised percentage improvement as a hypothesis to be tested against their own incumbent solver, on their own data, before it appears in a business case. That test is cheap. Run it.
Machine learning and the data-loading tax
Quantum machine learning attracts attention because quantum computers manipulate large vectors natively, and much of machine learning is linear algebra. Several algorithms offer impressive theoretical speedups for linear-algebraic subroutines, and amplitude estimation gives a quadratic improvement to Monte Carlo sampling, which sits under a great deal of pricing and risk work.
Two problems have limited the payoff. The first is input and output. Getting classical data into a quantum state, a step called amplitude encoding, can consume more time than the subsequent quantum computation saves, and reading a full answer vector out requires many repeated runs. Quantum computers suit small data with enormous computation, which is close to the opposite of where most enterprise machine learning value currently sits.
The second problem is that several headline quantum machine learning results have been dequantized: someone found a classical algorithm with comparable scaling, removing the advantage. Ewin Tang, then an undergraduate, did this to the quantum recommendation-systems algorithm in 2018 and to several related results afterwards. That work didn’t disprove quantum machine learning, and it did establish that a proved quantum speedup over the best known classical method is a weaker claim than it sounds.
Our position, which we state plainly to learners: expect simulation and cryptography to produce useful quantum advantage before general machine learning does, and treat quantum machine learning as a research area to monitor rather than a capability to plan around.
What classical computing still owns
Today’s machines are what the field calls NISQ devices, for Noisy Intermediate-Scale Quantum: enough qubits to be interesting, too many errors for long computations. Two-qubit operations fail at a rate of roughly one in a thousand in the best systems, which sounds tolerable until you notice that useful algorithms need millions of operations in sequence. Classical hardware is so much more reliable that its error rate rarely enters an engineering conversation at all.
The fix is quantum error correction, which spreads one protected unit of information across many imperfect ones. A physical qubit is a piece of hardware. A logical qubit is an error-corrected unit built from many physical qubits, and current surface-code schemes need on the order of a thousand physical qubits per logical qubit at useful error rates. That ratio is why resource estimates for breaking RSA run into the hundreds of thousands or millions of physical qubits.
Progress on that front is genuine. Google’s Willow processor, announced in December 2024 with 105 qubits, showed error rates falling as the code grew larger, the behaviour error correction has to have if it’s going to scale. IBM’s Condor chip passed 1,000 physical qubits in December 2023, and the roadmaps of every major vendor now emphasise logical qubits rather than raw counts.
Meanwhile the practical reality check: genuine end-to-end runs of Shor’s algorithm on hardware remain at the level of factoring 15 and 21. Larger published “quantum factorizations” generally use circuits compiled with knowledge of the answer, which proves nothing about scaling. Classical computers factor numbers with hundreds of digits routinely. Claims that encryption breaks next year are not supported by the current resource-estimate literature.
Hybrid is the delivery model, and that’s the part to plan for
There is a useful precedent for how this technology will actually arrive, and it’s the graphics processor. GPUs did not replace CPUs. They became accelerators for a specific shape of computation, sat behind libraries and APIs, and eventually reshaped an entire industry from that position without anyone throwing away a general-purpose computer. Most application developers using GPU acceleration today never write a line of GPU code.
Quantum processors are following the same path, and the hybrid algorithms already in use assume it. VQE and QAOA both run a classical optimiser in the outer loop and call the quantum device for the inner step. Access comes through the cloud, because the hardware needs cryogenic cooling, vibration isolation, and constant recalibration, and nobody wants that in a corporate data centre. A developer writes in Qiskit, Cirq, or a similar framework, and the heavy step executes on a machine somewhere else.
Three consequences follow for planning. Quantum capability will be procured as a service, not as capital equipment. The valuable internal skill is knowing which slice of a computation to hand off, which is an architecture question more than a physics question. And the people who can make that judgement need to understand both sides, which is why the training gap in most organisations is wider than the hardware gap.
A screening test for your own workloads
When a team brings us a candidate problem, we work through the same questions. They filter out most proposals in under an hour.
Does the problem contain quantum mechanics? Molecules, materials, catalysts, reaction pathways, magnetic systems. If yes, it belongs to the strongest family and deserves a pilot. If no, expectations should drop immediately.
Is the bottleneck combinatorial search with no structure? If the only method is trying candidates, you’re in Grover territory, and the Babbush argument applies. Ask for constant factors before you ask for a percentage improvement.
How good is your current classical solver, and who benchmarked it? A quantum result that beats a naive classical baseline tells you nothing. Insist that any comparison run against a well-tuned commercial solver on your data.
How much data has to move into the machine? If the answer is terabytes, the loading cost will overwhelm any computational gain with current architectures.
Is this a deadline or an opportunity? Cryptographic migration is a compliance obligation with dates attached. Everything else is optional and can wait for better hardware. Confusing the two is the most expensive mistake we see, in both directions: teams that treat migration as research, and teams that treat optimization pilots as urgent.
What is the pilot actually buying? Usually the honest answer is capability rather than results, and that’s a legitimate reason to spend money. It should be stated that way in the business case, so that nobody is disappointed by a correct outcome.
Where to build the judgement
Everything above is judgement rather than calculation. Deciding whether a workload has exploitable structure, whether a benchmark is fair, and whether a vendor claim holds up once its own constant factors are included takes a working understanding of how these algorithms produce their advantage. That understanding doesn’t require a physics degree, and it doesn’t come from a vendor webinar either.
Quantum Academy’s programs are built for exactly this: enough algorithmic depth that you can read a resource estimate and know what it assumes, taught for people who will be making procurement and architecture decisions rather than writing papers. Our algorithms and applications material covers the four families above in detail, with the worked resource estimates behind each one. Browse the current programs at quantumacademy.com/.
For migration methodology specifically, including cryptographic inventory and transition sequencing, the open framework at pqcframework.org is the companion reference, and deeper technical analysis of individual results lives at PostQuantum.com.