Quantum algorithms are procedures designed to run on quantum computers, and they work in a way that has almost nothing in common with the popular description of them. They do not evaluate every possible answer in parallel and select the best. They arrange for wrong answers to cancel each other out, so that when you finally look, a useful answer is what remains.
That distinction is not pedantry. It explains why only a few dozen useful quantum algorithms exist after forty years of effort, why some celebrated speedups have since been withdrawn, and why the machines needed to run the most famous one do not yet exist. This guide covers what quantum algorithms are, the main ones by name, how large their advantages actually are, and what it would take to run them.
Quantum algorithms do not test every answer at once. They use interference to cancel the amplitude on wrong answers so that measurement is likely to return a right one. Without that cancellation you get a random result.
Speedups come in four honest categories. Exponential, quadratic, small polynomial, and none once a better classical algorithm is found. Sorting a claim into the right category is the fastest way to judge it.
Shor’s algorithm is the one that changes the world, and it is the furthest away. The May 2025 estimate for breaking RSA-2048 is under a million noisy qubits, down twentyfold from 2019, but no machine remotely that size exists.
Grover is provably optimal and still hard to use. A quadratic saving struggles to pay for error-correction overhead, and loading unstructured data into a quantum machine remains unsolved.
Some quantum speedups turned out not to exist. Ewin Tang’s 2018 dequantization of quantum recommendation systems removed a claimed exponential advantage and prompted several more corrections.
Simulating quantum systems is the strongest case. It avoids the data loading and readout problems that undermine most other proposed applications, which is why it is the likeliest first source of real commercial value.
- What a quantum algorithm actually is
- Interference is the whole trick
- How they differ from classical algorithms
- The oracle model
- The four kinds of speedup
- What quantum computers cannot do
- The early algorithms
- Shor’s algorithm
- Grover’s algorithm
- Quantum phase estimation
- HHL and linear systems
- VQE and chemistry
- QAOA and optimisation
- Quantum simulation
- Walks, estimation and QSVT
- When the speedup disappears
- Quantum machine learning
- The data loading problem
- What it takes to run these
- The algorithms compared
- What it looks like in code
- How to start writing them
- Frequently asked questions
What a quantum algorithm actually is
A quantum algorithm is a procedure written for a machine whose basic unit of memory can hold a combination of zero and one rather than one or the other. That machine is not a faster classical computer. It is a different kind of device, and most classical procedures gain nothing at all from running on it.
The definition matters because the popular version is wrong. Quantum computers are routinely described as trying every possible answer simultaneously and returning the best one. A machine with 300 qubits does hold a combination of more states than there are atoms in the observable universe, so the image is seductive. The problem is the ending, because you cannot read those states.
Measurement returns exactly one outcome, chosen at random according to the weights the machine has built up. Prepare an even combination of a trillion possibilities and measure it, and you get one uniformly random answer out of a trillion. You have built an extremely expensive random number generator. Everything interesting in this field is about what happens between preparation and measurement.
Interference is the whole trick
The weights attached to each possible outcome are called amplitudes, and unlike probabilities they can be negative or complex. Two routes to the same answer can therefore cancel each other out. That single property is what separates a quantum algorithm from a randomised classical one.
A working quantum algorithm is a piece of choreography. It arranges the computation so that the paths leading to wrong answers arrive with opposing signs and destroy each other, while the paths leading to the right answer arrive in step and reinforce. By the time you measure, the amplitude has been herded onto the answers you want. Get the choreography wrong and you measure noise.
This is why designing quantum algorithms is hard, and why so few of them exist. Forty years of work by a global research community has produced a few dozen genuinely useful primitives. Compare that with the classical algorithm literature, which runs to tens of thousands of results.
How they differ from classical algorithms
Three constraints shape how quantum algorithms are built. The first is reversibility, since quantum evolution runs forwards and backwards, so every operation except measurement must be undoable. Classical circuits throw information away constantly, and an AND gate cannot be reversed because two different inputs give the same output. Quantum circuits cannot do that, which forces a different style of construction.
The second is the no-cloning theorem, which says an unknown quantum state cannot be copied. There is no equivalent of saving a variable for later, no debugger that prints intermediate values, and no way to make a backup before a risky operation. Any attempt to look at the state collapses it.
The third is decoherence. Qubits interact with their environment and lose their quantum character in microseconds to seconds depending on the platform. Every algorithm is racing a clock, which is why circuit depth, meaning the number of sequential operations, matters as much as qubit count.
The oracle model and why it dominates the literature
A great many quantum results are stated in terms of queries to a black box, called an oracle. You are given a function you cannot see inside, you may ask it questions, and the cost is the number of questions. Deutsch-Jozsa, Bernstein-Vazirani, Simon and Grover are all query results.
This framing is powerful because it allows provable separations. You can show that any classical algorithm needs a certain number of queries and that a quantum one needs fewer, with no unproven assumptions anywhere. It is also the source of persistent overstatement, since a proof about queries is not a proof about real problems. The oracle has to be built out of actual gates, and that construction can cost more than the speedup saves.
Reading quantum algorithm claims well means asking one question first. Is this a statement about queries to a black box, or about a concrete computational problem? The two get conflated constantly, including in material from vendors who should know better.
The four kinds of speedup
Not every quantum algorithms claim is worth the same. Sorting them into honest categories is the single most useful skill for reading this field, and it is where most marketing falls apart.
Exponential speedups are the prize. Classical cost grows exponentially with problem size while quantum cost grows polynomially, so the gap widens without limit. Factoring and quantum simulation live here, and the list is short.
Quadratic speedups turn a cost of N into a cost of the square root of N. Grover is the example, the result is provably optimal, and it still disappoints in practice. Error correction means each quantum step costs thousands of physical operations, so the crossover point where a quantum machine actually wins sits at problem sizes that are often impractical to load in the first place.
Small polynomial speedups are common in proposals and rarely survive contact with engineering. The fourth category is the interesting one, covered further down, where the advantage evaporates once someone writes a better classical algorithm.
What quantum computers cannot do
The class of problems a quantum computer solves efficiently is called BQP, for bounded-error quantum polynomial time. Understanding what is and is not believed to sit inside it removes a great deal of confusion, and it punctures the most common myth in the field.
That myth is that quantum computers will crack NP-complete problems, the famously hard family that includes the travelling salesman problem, boolean satisfiability and thousands of scheduling and routing tasks. Almost no complexity theorist expects this. NP-complete problems are not believed to lie inside BQP, and the best general quantum approach to them is Grover, which delivers only a quadratic saving rather than the exponential one that would be needed.
The problems where quantum computers do win tend to have hidden algebraic structure. Factoring is not NP-complete, and it is not believed to be NP-hard either. It sits in an unusual middle zone, hard for classical machines yet carrying a periodic structure that a quantum Fourier transform can exploit. That pattern repeats across the field, since quantum advantage comes from matching a specific mathematical structure rather than from raw parallelism.
It is also worth stating what quantum computers offer for everyday computing, which is nothing. They will not speed up databases, web servers, video encoding, spreadsheets or the overwhelming majority of software. They are special-purpose accelerators for a narrow class of mathematical problems, and the realistic future is a quantum processor attached to a classical machine much as a GPU is today.
The early algorithms that proved it was possible
David Deutsch defined the universal quantum computer in 1985 and gave a toy problem where a quantum machine beat a classical one. In 1992 Deutsch and Richard Jozsa sharpened it into the first clean exponential separation in the query model. Given a function promised to be either constant or balanced, their algorithm decides which with a single query where a deterministic classical algorithm may need exponentially many.
Nobody cares about the problem itself, which is contrived and useless. It mattered because it proved the category was not empty. Ethan Bernstein and Umesh Vazirani followed in 1993 with a problem of recovering a hidden bit string, and Daniel Simon in 1994 with a hidden period problem that gives an exponential separation even against randomised classical algorithms.
Simon’s algorithm is the important one historically. Peter Shor read it and recognised the structure, which is how the most consequential quantum algorithm ever written came to exist within months.
Shor’s algorithm and the end of RSA
Shor published in 1994, and it remains the result that funds the field. It factors large integers in polynomial time, where the best known classical method takes time growing roughly exponentially in the cube root of the number of digits. RSA encryption rests entirely on factoring being hard.
The structure surprises people who expect a magic factoring box. Most of Shor’s algorithm is classical number theory, which reduces factoring to finding the period of a modular exponential function. Only the period-finding step is quantum, handled by the quantum Fourier transform, and a final classical step converts the period back into a factor.
The engineering question is what it would take to run. In 2019 Craig Gidney and Martin Ekera estimated that breaking RSA-2048 would need roughly 20 million noisy physical qubits running for about eight hours. In May 2025 Gidney published a revised analysis putting it under one million noisy qubits and under a week, roughly a twentyfold reduction, achieved through approximate residue arithmetic, yoked surface codes and cheaper magic state preparation.
No such machine exists. The largest devices today run from a few hundred to a few thousand physical qubits, and they are not error-corrected in the way this requires. The direction of travel is the point, since the algorithmic requirement has fallen faster than the hardware has climbed. That asymmetry is the whole argument for post-quantum cryptography migration on a fixed timetable, and why the UK’s National Cyber Security Centre expects full migration by 2035.
Grover’s algorithm and the limits of searching
Lov Grover published his search algorithm in 1996. Given an unstructured collection of N items and a way to recognise the one you want, it finds it in about the square root of N steps rather than N. For a trillion items that is a million steps instead of a trillion.
The mechanism is amplitude amplification. The state starts as an even combination of every item, then each iteration performs two reflections that rotate it slightly toward the marked item. Run the right number of iterations and the amplitude concentrates where you want it. Run too many and it rotates past, which is a genuine failure mode.
Grover is provably optimal. Bennett, Bernstein, Brassard and Vazirani showed in 1997 that no quantum algorithm can do better than square root for unstructured search, so this is the ceiling rather than a first attempt. That is a satisfying theoretical result and a discouraging practical one.
Two things spoil the party. Error correction makes each Grover step vastly more expensive than a classical memory read, so the crossover point is far out. Worse, the algorithm assumes the data is available in quantum superposition, and loading a large unstructured classical dataset into a quantum machine is an unsolved problem that can cost as much as the search itself. Grover shines on problems where the data is generated by a rule rather than stored, such as cryptographic key search. A closer look at Grover is worth the time if you want the mechanics.
Quantum phase estimation, the quiet workhorse
Phase estimation is the most reused primitive among fault-tolerant quantum algorithms. Given a unitary operation and one of its eigenvectors, it extracts the associated eigenvalue to a chosen precision. Stated that way it sounds like housekeeping, and it is anything but.
Eigenvalues are what you want in an enormous range of problems. The ground-state energy of a molecule is an eigenvalue. Shor’s period finding is phase estimation wearing a different hat. Many linear-algebra routines call it as a subroutine. It is also expensive, needing deep coherent circuits and therefore full error correction, which puts it firmly in the post-NISQ era.
HHL, linear systems and the fine print
The 2009 algorithm by Aram Harrow, Avinatan Hassidim and Seth Lloyd solves linear systems of equations, and it is the most misrepresented result in the field. The headline is an exponential speedup for solving Ax = b, which sounds like it would transform engineering, finance and machine learning at a stroke.
The conditions are severe. The matrix must be sparse and well conditioned, the vector b must already be loaded as a quantum state, and the output is a quantum state encoding the solution rather than the solution itself. Reading out all the components destroys the speedup entirely, so you only win if you want a single summary statistic of the answer.
HHL remains theoretically important and it seeded a decade of work on quantum linear algebra. Treat any claim built on it as requiring proof that all four conditions hold, because in most proposed applications at least one fails.
VQE and the chemistry case
The variational quantum eigensolver, introduced by Alberto Peruzzo and colleagues in 2014, was designed for machines that cannot run deep circuits. It splits the work between a quantum processor and a classical optimiser. The quantum device prepares a trial state and measures its energy, and the classical optimiser adjusts the parameters and tries again.
The appeal is short circuits, which suits current hardware. The difficulty is everything else. Choosing the trial state form, called the ansatz, is more art than science, the classical optimisation runs into flat regions known as barren plateaus where gradients vanish exponentially with system size, and the number of measurements needed to estimate energies to chemical accuracy grows uncomfortably fast.
VQE has produced real experimental results on small molecules. It has not yet produced a chemistry result that a classical method could not match or beat, and the barren plateau problem is a serious structural obstacle rather than an engineering detail.
QAOA and combinatorial optimisation
The quantum approximate optimisation algorithm, published by Edward Farhi, Jeffrey Goldstone and Sam Gutmann in 2014, applies a similar hybrid pattern to combinatorial problems such as graph partitioning and scheduling. Alternating layers of two operations are tuned by a classical optimiser to push the state toward good solutions.
QAOA attracted enormous attention because optimisation is commercially valuable and the circuits are shallow. The evidence for advantage remains thin. At low depth its performance is matched by classical heuristics, at high depth the circuits exceed what current hardware sustains, and the intermediate regime where it might win has not been convincingly demonstrated. Related but distinct is quantum annealing, which uses different hardware and carries its own long-running debate about advantage.
Quantum simulation, the original and best case
The oldest case for quantum algorithms is still the strongest. Richard Feynman’s 1982 argument was that simulating quantum systems on classical machines is intractable because the state space grows exponentially, so you should use a quantum system to simulate a quantum system. Four decades later this remains the most defensible application.
The reason is structural rather than promotional. Quantum simulation does not fight the data loading problem, since the input is a physical description of a Hamiltonian rather than a large dataset. It does not fight the readout problem, since the quantities of interest are usually a handful of numbers such as energies or correlation functions. The exponential difficulty on the classical side is real rather than an artefact of comparing against a weak baseline.
Catalyst design, superconductivity, nitrogen fixation and drug binding all sit here. If a quantum computer delivers commercial value first, most researchers expect it to happen in simulation rather than in optimisation or machine learning.
The modern toolkit, walks, estimation and QSVT
Three families dominate current algorithm research. Quantum walks are the quantum counterpart of random walks, and they give provable speedups for graph problems including element distinctness and triangle finding. Amplitude estimation generalises Grover to count rather than find, delivering a quadratic improvement in how many samples a Monte Carlo calculation needs, which is why it draws attention in derivative pricing and risk.
The unifying development is the quantum singular value transformation, published in 2019 by Andras Gilyen, Yuan Su, Guang Hao Low and Nathan Wiebe. Their unifying framework for quantum algorithms showed that Grover, phase estimation, Hamiltonian simulation and matrix inversion are all special cases of one construction for applying polynomial functions to the singular values of a matrix. It is the closest thing the field has to a grand unification, and it has become the standard language for stating new results.
When the speedup disappears
In 2018 an undergraduate at the University of Texas at Austin named Ewin Tang was given what her supervisor Scott Aaronson expected to be an impossible task, namely proving a lower bound for classical recommendation systems. The quantum algorithm of Iordanis Kerenidis and Anupam Prakash was believed to offer an exponential speedup.
Tang did the opposite of what was asked. She produced a classical algorithm that matched the quantum one up to polynomial factors, which meant the exponential speedup had never existed. The quantum algorithm had been compared against the wrong classical baseline, and the sampling assumptions that made the quantum version fast could be granted to a classical algorithm too.
The result opened a subfield. Similar dequantization arguments went on to remove claimed exponential advantages from principal component analysis, low-rank linear systems and low-rank semidefinite programming. This is what a healthy field looks like, and it is also a permanent warning. Any claimed exponential speedup over classical methods for a machine learning task should be treated as provisional until someone has tried hard to dequantize it.
Quantum machine learning after the correction
The dequantization results did not end quantum machine learning, but they changed its character. The surviving research directions are more careful about what they claim and about which classical baseline they measure against.
The most defensible line concerns quantum data rather than classical data. If the input is itself a quantum state produced by a physical experiment, there is no loading problem and no obvious classical shortcut, and provable learning advantages exist in that setting. The harder commercial question, whether quantum methods help on ordinary classical datasets, remains open and the honest answer is that no convincing demonstration exists.
The data loading problem nobody has solved
A quantum algorithm that processes classical data has to get that data into the machine, and this is the obstacle that quietly kills more proposals than decoherence does. The theoretical device for the job is quantum random access memory, or QRAM, which would return a superposition of stored values when queried with a superposition of addresses.
Nobody has built one at useful scale, and there are reasons to doubt anyone will soon. A QRAM holding N items needs on the order of N components, all of which must stay coherent during the query and all of which need error correction. Loading a dataset of a billion records would require hardware comparable in scale to the machine doing the computation, which undermines the point.
The arithmetic is unforgiving. If loading takes time proportional to N, a Grover search that runs in the square root of N steps has already lost, because the loading dominates. This is why the strongest quantum applications are the ones where data never has to be loaded. Shor takes a single number as input. Quantum simulation takes a physical description rather than a dataset. Cryptographic search generates its candidates from a rule instead of reading them from storage.
Any proposal that begins by assuming a large classical dataset is already available in superposition is describing a machine that does not exist and may not be buildable. That assumption deserves the same scrutiny as the speedup claim it supports.
What it takes to actually run these
Almost all of the quantum algorithms above, VQE and QAOA excepted, need error correction, and the overhead is the central fact of the field. Physical qubits are too noisy, so many of them are combined into one reliable logical qubit using a code such as the surface code.
Current ratios run from hundreds to thousands of physical qubits per logical qubit depending on hardware quality and target error rate. An algorithm needing a few thousand logical qubits therefore needs millions of physical ones. Non-Clifford operations add a further cost, since they are performed by consuming specially prepared magic states, and magic state factories can dominate the footprint of a fault-tolerant machine.
This is why quantum error correction progress matters more than qubit-count records. A machine with a million noisy qubits and no error correction runs none of the algorithms in this article.
The algorithms compared
| Algorithm | Year | Speedup | Needs error correction | Practical status in 2026 |
|---|---|---|---|---|
| Deutsch-Jozsa | 1992 | Exponential, query model | No, tiny circuits | Teaching example, no application |
| Simon | 1994 | Exponential, query model | Yes at scale | Historically vital, led to Shor |
| Shor | 1994 | Exponential | Yes, heavily | Under 1M noisy qubits estimated for RSA-2048, none exist |
| Grover | 1996 | Quadratic, provably optimal | Yes | Real but hard to cash in, data loading unsolved |
| Phase estimation | 1995 | Exponential in context | Yes, deep circuits | Core primitive for fault-tolerant era |
| HHL | 2009 | Exponential with heavy caveats | Yes | Conditions rarely met in practice |
| VQE | 2014 | Unproven | No, built for noisy machines | Runs today, no advantage demonstrated |
| QAOA | 2014 | Unproven | No | Matched by classical heuristics so far |
| Quantum simulation | 1982 onward | Exponential | Yes for useful sizes | Most defensible route to advantage |
| Amplitude estimation | 2000 | Quadratic | Yes | Watched closely in finance |
| QSVT | 2019 | Framework, not one algorithm | Yes | Standard language for new results |
What a quantum algorithm looks like in code
Reading a circuit makes the ideas concrete. The example below builds the two-qubit Grover instance that marks the state 11, using Qiskit conventions current as of Qiskit 1.x and 2.x. It shows the shape every Grover implementation shares, namely an even superposition, an oracle that flips the sign of the marked state, and a diffusion step that reflects about the average.
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
from qiskit import transpile
qc = QuantumCircuit(2, 2)
# 1. equal superposition over all four basis states
qc.h([0, 1])
# 2. oracle: flip the phase of |11>
qc.cz(0, 1)
# 3. diffusion: reflect about the mean
qc.h([0, 1])
qc.x([0, 1])
qc.cz(0, 1)
qc.x([0, 1])
qc.h([0, 1])
qc.measure([0, 1], [0, 1])
sim = AerSimulator()
result = sim.run(transpile(qc, sim), shots=1024).result()
print(result.get_counts())
# {'11': 1024} -- one iteration is exact for N=4
Two details in that output are worth noticing. A single iteration solves the four-item case exactly, which is a coincidence of small numbers rather than the general behaviour. For larger instances you need about the square root of N iterations and the result is probabilistic, so you repeat and verify.
How to start writing them
Writing quantum algorithms starts with linear algebra, specifically vectors, matrices, eigenvalues and tensor products. Physics background helps but is not necessary, and many strong quantum algorithm researchers came from computer science or mathematics.
The standard reference is Nielsen and Chuang, usually shortened to Mike and Ike, which remains the field’s textbook after two decades. For hands-on work, Qiskit and PennyLane both run on simulators locally and on real hardware through cloud services, and simulators are the right place to start since a laptop handles about 30 qubits comfortably.
The most useful habit is reading claims sceptically. When you meet a new algorithm, ask which speedup category it falls into, whether the comparison is against the best classical method or a convenient one, how the data gets in, how the answer gets out, and how many logical qubits it needs. Those five questions dispose of most overstatement.
Frequently asked questions
What are quantum algorithms in simple terms?
They are step-by-step procedures written for quantum computers, which store information in qubits that can hold combinations of zero and one. The procedures work by arranging for the wrong answers to cancel each other out through interference, so that a measurement is likely to return a useful result. They are not simply faster versions of classical procedures, and most classical tasks gain nothing from them.
Do quantum algorithms try all answers at once?
No, and this is the most common misconception. A quantum computer can hold a combination of many states, but measuring it returns only one outcome at random. Without interference to concentrate the amplitude on correct answers, you get a random result, so the useful work happens between preparing the state and measuring it.
Which quantum algorithm is the most important?
Shor’s algorithm for factoring is the most consequential, because it breaks RSA encryption and drives the global migration to post-quantum cryptography. Grover’s search algorithm is the most widely taught. For likely commercial value, many researchers point instead to quantum simulation of physical systems.
How many qubits do you need to run Shor’s algorithm on RSA-2048?
The most recent public estimate, published by Craig Gidney in May 2025, puts it at under one million noisy physical qubits running for under a week. That is roughly a twentyfold reduction on the 2019 estimate of 20 million qubits and eight hours. No machine of that scale exists, and today’s largest devices run from a few hundred to a few thousand physical qubits.
Are quantum algorithms always faster than classical ones?
No. Speedups are known for a specific and fairly small set of problems, and for most tasks a quantum computer offers no advantage at all. Some claimed speedups have also been withdrawn after researchers found classical algorithms that matched them, a process called dequantization.
What is dequantization?
It is the process of finding a classical algorithm that matches a quantum one, showing the claimed quantum advantage was never real. The best known case is Ewin Tang’s 2018 work on recommendation systems, which removed a supposed exponential speedup and prompted similar results for several other quantum machine learning algorithms.
Can I run quantum algorithms today?
Yes, on simulators and on real cloud-accessible hardware through frameworks such as Qiskit and PennyLane. What you cannot do is run them at a scale where they beat a classical computer, because that needs error correction and far more qubits than current machines provide.
What is the difference between VQE and QAOA?
Both are hybrid algorithms that split work between a quantum processor and a classical optimiser, and both were designed for noisy hardware. VQE targets finding the lowest energy state of a quantum system, which makes it a chemistry and materials tool. QAOA targets combinatorial optimisation problems such as scheduling and graph partitioning.
Why do quantum algorithms need error correction?
Qubits lose their quantum state through decoherence within microseconds to seconds, while useful algorithms need far more operations than that allows. Error correction combines many noisy physical qubits into one reliable logical qubit, currently at a cost of hundreds to thousands of physical qubits each.
Is quantum machine learning real?
The research field is real and active, but the commercial claims run ahead of the evidence. Several early exponential speedup claims were dequantized, and no convincing demonstration exists of quantum advantage on ordinary classical datasets. The strongest results concern learning from quantum data produced by physical experiments.
Where this leaves the field
Quantum algorithms are a real branch of computer science with proven results, a growing toolkit and a small number of applications that would change what is computable. They are also surrounded by more overstatement than almost any other area of technology, and the overstatement usually takes one of three forms.
The first is treating a query-model separation as a practical speedup. The second is quoting an exponential advantage while omitting the loading and readout conditions that make it unreachable. The third is comparing against a weak classical baseline, which is precisely what dequantization exposes. Reading past those three patterns is most of what informed scepticism requires here.
What has genuinely changed recently is the seriousness of the engineering. Resource estimates are now detailed enough to argue about, the cost of breaking RSA has fallen twentyfold in six years on the algorithm side alone, and error correction has moved from theory to demonstrated hardware. The gap between what these algorithms need and what machines provide is still large. It is no longer unmeasurable, and that is the real progress.
See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
