Grover and Shor, Simulated: Learning the Famous Quantum Algorithms
· 13 min read · ZKSF team
Two algorithms appear in nearly every quantum computing course, because together they delimit what a quantum computer might accomplish that a classical one cannot. Grover's algorithm searches an unstructured space with a quadratic speedup; Shor's algorithm factors integers with an exponential one. The difference between quadratic and exponential is the entire practical story, and it is usually glossed over.
The left side plots Grover’s success probability against iteration count for a 4-qubit search (N=16). The moving marker traces the exact probability, climbing to a peak at the optimal iteration k* near three, then falling again through an overshoot region where adding iterations lowers the chance of measuring the marked item. The loop driving it is two operations repeated k times: an oracle that flips the sign of the target state, followed by a diffusion step that amplifies it. That gives Grover its quadratic speedup, roughly the square root of N steps against N for a classical worst-case search. The right side separates Shor’s algorithm into its quantum core, period-finding via the quantum Fourier transform, and the classical number theory around it (continued fractions and a gcd). The scale bar beneath it is the part most easily missed: factoring 15 or 21 is a trivial teaching exercise on a few qubits, whereas a 2048-bit RSA modulus would require thousands of logical qubits, millions of physical ones, and hours of runtime. That gap is why a cryptographically threatening Shor run remains a future event rather than a present capability. Both algorithms are shown at sizes a laptop holds exactly, which is precisely where their mechanics are learned.
Grover's algorithm
Grover's algorithm finds a marked item among N possibilities in O(sqrt(N)) queries, against the N/2 expected queries a classical search requires. It is provably optimal: no quantum algorithm can do better for an unstructured search, a result due to Bennett, Bernstein, Brassard and Vazirani that predates Grover's algorithm itself.
The mechanism is amplitude amplification. Beginning in a uniform superposition over all N states, each iteration applies two reflections: an oracle that flips the sign of the marked state, and a diffusion operator that reflects all amplitudes about their mean. Geometrically the pair rotates the state vector toward the marked state by a fixed angle of roughly 2/sqrt(N) radians per iteration, so approximately (pi/4) sqrt(N) iterations are required to arrive.
The geometric picture predicts a phenomenon worth seeing directly: continuing past the optimal count rotates the state *past* the target and the success probability falls. Grover's algorithm can be run too long, and the success probability oscillates rather than saturating. This is among the clearest demonstrations available that quantum algorithms are interference phenomena rather than parallel search.
Grover's circuit is general and densely entangling, so a statevector simulator handles it directly at the usual 2^n cost. That cost is entirely manageable for learning: at 10 to 20 qubits the full algorithm runs comfortably, the target amplitude can be plotted iteration by iteration, and the overshoot is directly visible. A worked implementation is in the Grover tutorial.
Why quadratic is less than it appears
The practical caveat on Grover deserves more attention than it usually receives. A quadratic speedup is consumed quickly by constant factors.
Quantum gates operate at kilohertz to megahertz rates on current hardware; classical processors operate at gigahertz rates and parallelise across thousands of cores. Fault-tolerant execution adds a further large overhead, since each logical gate decomposes into many physical operations plus rounds of error correction. Published analyses generally conclude that Grover-type speedups become advantageous only for search spaces large enough that the constant factors are amortised, and that for many realistic problem sizes a classical machine finishes first.
The security consequence is nonetheless real and is the reason symmetric key sizes are being doubled: Grover reduces the effective security of a 128-bit key to roughly 64 bits of quantum search, so AES-256 is specified where AES-128 would otherwise suffice. This is a manageable adjustment rather than a break, which is exactly the difference between quadratic and exponential.
Shor's algorithm
Shor's algorithm factors an integer in time polynomial in the number of digits, an exponential speedup over the best known classical methods. Its consequence is severe: a sufficiently large fault-tolerant quantum computer would break RSA and elliptic-curve cryptography, which secure most internet traffic today.
The structure is worth understanding because most of it is classical. Factoring N reduces to finding the period r of the function f(x) = a^x mod N for a randomly chosen a. Given r, and provided r is even and a^(r/2) is not congruent to -1, the greatest common divisor of a^(r/2) plus or minus 1 with N yields a non-trivial factor. That reduction is elementary number theory and requires no quantum computer.
The quantum part is period finding, and it consists of modular exponentiation into a superposition followed by an inverse quantum Fourier transform, which concentrates amplitude on multiples of 1/r. The QFT is efficient, requiring O(n^2) gates. The expensive component is modular exponentiation, which dominates the circuit and is the reason resource estimates are as large as they are.
What it would actually cost
Task Feasibility
Factor 15 or 21 trivial; standard teaching exercise
Factor a 2048-bit RSA modulus ~1,000s of logical qubits; physical
estimates fell from ~20M (2019) to
<1M (2025) to <100k (2026, LDPC codes)Factoring 15 or 21 is a common exercise and simulates easily, though it is worth noting that most published small-number demonstrations use circuits simplified with prior knowledge of the answer, which makes them illustrations rather than executions of the general algorithm.
Factoring a cryptographically relevant modulus is a different scale, and the resource estimates have moved quickly. Craig Gidney's 2019 analysis required roughly 20 million physical qubits over eight hours. His 2025 revision brought that under 1 million, and a 2026 result built on low-density parity-check codes projects fewer than 100,000 physical qubits, corresponding to on the order of a thousand logical qubits running for hours.
Even the lowest of these figures is far beyond current hardware, which in 2026 spans a few thousand physical qubits and up to 96 demonstrated logical qubits, and far beyond classical simulation of the full circuit. A cryptographically relevant Shor run is not yet possible. The more useful observation is that the resource gap narrowed by more than two orders of magnitude in seven years, driven by algorithmic and error-correction improvements rather than by hardware, and that trend is a stronger argument for migrating cryptography than any single projection.
The migration is already underway; the standardised replacements and the timeline are covered in the post-quantum cryptography primer.
Why simulate them at all
Understanding precedes scale. Simulating these algorithms at small sizes teaches the mechanics that motivate the entire hardware effort and the cryptographic response to it.
There is also a pedagogical advantage simulation has over hardware permanently, not merely for now: a simulator can display the full state at any point in the circuit, which physics forbids on a physical device. Watching Grover's amplitude concentrate over iterations, or the QFT's peaks form at multiples of 1/r, is available only in simulation. Measurement on hardware collapses precisely the object being studied.
Running these exactly, and inspecting the intermediate states real hardware never exposes, builds the intuition required to evaluate large-scale claims critically rather than accept them on authority. That is the practical case for starting here.
Run your own 100-qubit circuit, with an error bar.
