Three Circles of Quantum Algorithms
One of the clearest pictures in quantum computing is a Venn diagram with three circles. It is a way of asking: where are the quantum algorithms that are actually worth building a machine for? The diagram does not answer that — but it tells you exactly where every candidate sits.
The three circles are practical utility (does the algorithm solve a real-world problem — chemistry, logistics, cryptography — that somebody actually needs solved?), few qubits (can it run on a modest number of qubits, the kind we can build today?), and quantum advantage (does it genuinely outperform the best classical computer?). The spot where all three overlap is the goal: a useful, buildable, genuinely faster quantum computation.
Two landmark results show why that center is so hard to reach. Shor's algorithm sits firmly in the overlap of practical utility and quantum advantage: factoring large numbers exponentially faster is enormously useful (it breaks today's encryption) and a true quantum speedup. But it does not reach into the "few qubits" circle — running it on cryptographically relevant numbers needs thousands of reliable logical qubits, which means millions of physical ones once error correction is included. Shor's is in the diagram, but off-center.
Shor's algorithm
Practical utility + quantum advantage — but needs far more qubits than we have.
Quantum supremacy (2019)
Few qubits + quantum advantage — but the task had no practical use.
Google's 2019 quantum supremacy experiment sits in a different overlap: few qubits and quantum advantage. A ~53-qubit processor ran a sampling task no supercomputer could reproduce in reasonable time — a genuine quantum speedup on a modest chip. But it does not reach into the "practical utility" circle: the task, random circuit sampling, was chosen precisely because it is hard for classical machines, not because anyone needs its answer. So the diagram's message is the field's central tension: the most useful algorithms need the most qubits, and today's machines have the fewest. Every line of research — better hardware, error correction, smarter algorithms — is an attempt to drag more results toward that desired center. The center is empty today; that is the point of the diagram.
Go deeper — the math & the rigor
Why do the three circles resist overlapping? Because "few qubits" and "quantum advantage" pull against each other. Advantage on a small device demands deep, intricate circuits; noise destroys deep circuits before they finish. Meanwhile "practical utility" usually means large problem instances — simulating a real molecule, factoring a real key — which need many qubits and long coherence. Formally, each circle is a resource demand: utility demands problem size, advantage demands circuit complexity that classical machines cannot match, and "few qubits" demands the whole thing fit in a NISQ-era device. Satisfying all three at once is the field's open problem.
The 2019 supremacy experiment deserves precise language. Google's Sycamore processor sampled the output of a random quantum circuit — a task whose cost grows like \\(2^{53}\\), the dimension of the 53-qubit state space — in about 200 seconds. Google estimated the best supercomputer would need ~10,000 years; IBM countered that with better classical algorithms and enough disk storage it could take days. The debate is beside the point for the diagram: whatever the exact classical cost, this was a real quantum computation no classical machine could do conveniently — on a real chip — and it landed exactly where the diagram predicts: advantage without utility.
Contrast Shor's. For an \\(n\\)-bit number, the quantum circuit needs only \\(O(n)\\) qubits — polynomial, not exponential — so in principle it is efficient. The trouble is the constant factors: thousands of logical qubits, each protected by error correction requiring hundreds to thousands of physical qubits, plus deep circuits and long coherence. The resource estimate is millions of physical qubits. Shor's is an algorithm waiting for a machine — utility and advantage confirmed, "few qubits" denied.
Read this way, the diagram is also a research map. Error correction moves results toward "few qubits" by making each qubit better; new hardware moves the boundary of what "few" means; and algorithm design hunts for problems that are both useful and NISQ-sized — variational algorithms like VQE and QAOA live in exactly that hunt. Progress is measured in results migrating toward the center. (See also: Shor's algorithm, Grover's algorithm, Quantum computing in 10 questions.)
Key takeaways
- A Venn diagram of practical utility, few qubits, and quantum advantage organizes the search for worthwhile quantum algorithms.
- The center — all three at once — is the goal, and it is empty today.
- Shor's algorithm has utility and advantage but needs far more qubits than NISQ devices offer.
- The 2019 supremacy experiment had advantage on ~53 qubits but solved no practical problem.
- Hardware, error correction, and algorithm design are all attempts to pull results toward the center.
Check your understanding
Q1.In the three-circles diagram, where does Shor's algorithm sit?
Shor's is enormously useful and a true speedup, but needs thousands of logical qubits — far beyond 'few'.
Q2.Why does Google's 2019 supremacy experiment miss the center of the diagram?
Random circuit sampling was chosen for classical hardness, not because anyone needs its answer.
Q3.What would it take for an algorithm to reach the desired center?
The center is the overlap of all three circles: utility, advantage, and few qubits.
References
The books, papers, and articles this lesson drew on — with a note on what each one was used for.
- Arute et al., "Quantum supremacy using a programmable superconducting processor", Nature 574, 505–510 (2019). · source ↗
Used for: the 2019 supremacy experiment — random circuit sampling on ~53 qubits. - IBM, "On 'quantum supremacy'" (2019). · source ↗
Used for: the classical-cost debate around the supremacy experiment.
Tip: press ← / → to turn pages.