Grover and Shor, Simulated: Learning the Famous Quantum Algorithms

July 3, 2026 · 6 min read · ZKSF team

Two algorithms appear in nearly every quantum computing course, because together they demonstrate what a quantum computer might accomplish that a classical one cannot. Grover's algorithm searches an unstructured space; Shor's algorithm factors integers. Both are best learned by running them on a simulator, where the state can be observed exactly at every step.

Interactive diagramGrover’s overshoot, and Shor’s resource gulfGrover’s success probability across iterations, next to the scale that separates a teaching-size Shor run from a cryptographic one

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 roughly the square root of N steps, a quadratic speedup over the N steps a classical search requires in the worst case. It proceeds by repeatedly applying two operations: an oracle that flips the sign of the target state, and a diffusion step that amplifies its probability. After approximately the square root of N iterations, measuring the register returns the marked item with high probability.

Grover's circuit is general and densely entangling, so a statevector simulator handles it directly at the usual 2^n memory cost. That cost is manageable for learning purposes: at 10 to 20 qubits the full algorithm runs comfortably, the growth of the target amplitude can be plotted iteration by iteration, and the well-known overshoot effect, where too many iterations lower the success probability, is directly visible. It is among the clearest demonstrations available in quantum computing and fits on a laptop without difficulty.

Shor's algorithm

Shor's algorithm factors an integer in time that grows polynomially with its number of digits, an exponential speedup over the best known classical methods. Its consequence is significant: a sufficiently large quantum computer running Shor's algorithm would break the RSA and elliptic-curve cryptography that secures much of internet traffic today. The quantum component of the algorithm is period finding via the quantum Fourier transform; the remainder is classical number theory.

Simulation meets a firm limit here, worth stating precisely.

Task                                   Simulation feasibility
Factor 15 or 21 with Shor's algorithm   trivial, common teaching exercise
Factor a cryptographically relevant     ~1,000 logical qubits; 2025-2026
2048-bit number                         estimates put the physical cost near
                                         100,000 to 1,000,000 qubits, still
                                         beyond classical simulation and
                                         beyond today's hardware

Factoring a small number such as 15 or 21 is a standard teaching exercise and simulates easily. Factoring a cryptographically relevant 2048-bit number is an entirely different scale, and the resource estimates have moved fast. Craig Gidney's 2019 analysis required roughly 20 million physical qubits; his 2025 revision brought that under 1 million, and a 2026 result built on low-density parity-check codes projects fewer than 100,000, on the order of a thousand logical qubits running for hours. Even the lowest of these figures is beyond both current hardware, which in 2026 spans a few thousand physical qubits and its first few dozen logical qubits, and beyond classical simulation of the full circuit. A cryptographically relevant Shor run is therefore not yet possible, but the resource gap has narrowed by more than two orders of magnitude in a few years, which is a more useful fact than any single projection.

Why simulate these algorithms at all

Understanding precedes scale. Simulating Grover's and Shor's algorithms at small sizes teaches the mechanics that motivate the entire hardware effort and the post-quantum cryptography response to it. Running them exactly, and inspecting intermediate states that real hardware never exposes, builds the intuition required to evaluate large-scale claims critically rather than accept them as received wisdom.

Run your own 100-qubit circuit, with an error bar.

Try ZKSF Get the Android app