Where is the quantum advantage? The big picture of algorithms

In which problems are quantum computers really fast, and in which not? Learn the kinds of speed-up, today’s experiments and how to tell exaggerated claims apart.

Kinds of speed-up

Not all quantum algorithms are equally fast. Shor’s algorithm gives a huge leap over the best known classical methods for factoring. Grover search gives a “quadratic” speed-up: it cuts a search that takes N steps classically down to about √N steps; a thousand steps instead of a million.

Simulating quantum systems, that is molecules and materials, is also one of the areas where a large advantage is expected; Feynman proposed the idea of a quantum computer in 1981 for exactly this purpose. In contrast, for most ordinary computing, such as sorting a table or playing a video, a quantum computer has no advantage at all.

Today’s experiments

In 2019 Google announced that its 53-qubit Sycamore processor had performed a task called random circuit sampling in 200 seconds and that the most powerful supercomputer would need 10,000 years for it; IBM argued that a better classical method could do the same job in a few days. In 2024 Google’s 105-qubit Willow chip performed a task of the same kind in 5 minutes and showed for the first time error correction that reduces errors as the number of qubits grows.

These tasks are artificial problems chosen to measure the power of a quantum computer; they produce no result useful in everyday life. In 2025 Google announced the first claim of a verifiable advantage on a physical question, but the race for useful quantum advantage goes on.

Noisy devices and error correction

Today’s devices are called NISQ (noisy intermediate-scale quantum) devices: they have hundreds of qubits but every gate makes small errors. Short variational algorithms such as VQE and QAOA were designed for these devices. Long algorithms like Shor’s can only run on error-corrected, “fault-tolerant” computers.

Error correction uses many physical qubits as a single reliable “logical qubit”. That is why breaking real RSA keys needs far more qubits than exist today. How error correction works is the subject of one of the school’s later courses.

Telling hype apart

If you see the sentence “a quantum computer tries all the answers at once” in a news story, be careful: a measurement gives only a single result, and an advantage appears only in problems where interference can boost the probability of the right answer.

Some promised speed-ups were later matched by cleverer classical algorithms. For example, in 2018 Ewin Tang found a classical method that runs almost as fast as an important quantum machine learning algorithm for recommendation systems. A good question to ask is always: was it compared with the best classical method?

Try it yourself

This four-option Grover circuit finds the right answer with 100% certainty in a single step; classically 2.25 tries are needed on average. As the number of options grows the gap widens in proportion to √N: this is the quadratic speed-up.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

Shor gives a huge speed-up for factoring, Grover a quadratic (√N) speed-up for search.
Simulating quantum systems is one of the most promising application areas.
Today’s supremacy experiments are artificial tasks; the race for useful advantage goes on.
Every speed-up claim should be compared with the best classical method.

Test yourself

A search takes N steps classically. About how many steps does Grover search need?

log N
√N
N / 2

Show the answer

√N. Grover gives a quadratic speed-up: about (π/4)·√N steps. For a search over a million items that is around a thousand.

← Quantum walks: the quantum version of a random walk · Communication and cryptography course: teleportation, BB84 and post-quantum encryption →