In short: Shor's algorithm factors large integers in polynomial time and breaks RSA/ECC, while Grover's algorithm gives a quadratic speedup for unstructured search — together they are the two results that explain why quantum computing threatens cryptography and why so much engineering money is chasing qubits.
Two quantum algorithms are cited far more than any others when people ask "what is a quantum computer actually good for?" Peter Shor's 1994 factoring algorithm and Lov Grover's 1996 search algorithm are both decades old, yet they remain the benchmarks against which every new superconducting or trapped-ion chip is measured. Understanding them is essential for anyone preparing for interviews in hardware security, cryptography, or next-generation VLSI, because the hardware roadmaps at Intel, IBM, and startups fabbing on advanced nodes are explicitly driven by the qubit counts these algorithms demand.
Why classical factoring is hard
The security of RSA rests on a brutally simple asymmetry: multiplying two 1024-bit primes is trivial, but recovering those primes from the 2048-bit product is not. The best known classical method, the General Number Field Sieve, runs in sub-exponential time — roughly exp(1.9 · (ln N)^(1/3) · (ln ln N)^(2/3)). For a 2048-bit modulus that is on the order of 10^34 operations, comfortably beyond any data centre on Earth for the foreseeable classical future.
A 2048-bit RSA key would take a classical supercomputer longer than the age of the universe to factor by brute force. Shor's algorithm reduces that to hours on a sufficiently large fault-tolerant quantum computer.
Shor's algorithm: factoring as period-finding
Shor's key insight was that factoring reduces to period-finding. To factor N, pick a random a coprime to N and look at the function f(x) = a^x mod N. This function is periodic with some period r, and once you know r, elementary number theory recovers a factor of N from gcd(a^(r/2) ± 1, N). The hard part — finding r — is exactly what a quantum computer does exponentially faster, using the Quantum Fourier Transform (QFT) to extract periodicity from a superposition of all function values at once.
Complexity-wise, Shor runs in roughly O((log N)^3) time — polynomial in the number of bits. That is the exponential-to-polynomial collapse that makes it famous. The catch is resource overhead: factoring a 2048-bit key needs on the order of 20 million noisy physical qubits once quantum error correction is layered on top of a few thousand logical qubits. Today's best chips have a few thousand physical qubits, so RSA is safe for now — but "harvest now, decrypt later" attacks mean the clock is already ticking.
Grover's algorithm: amplitude amplification
Grover's algorithm tackles a different problem: searching an unstructured database of N items for the one that satisfies some condition. Classically you expect to check N/2 entries on average; Grover finds it in about √N steps. For N = 1,000,000, that is roughly 1,000 oracle calls instead of 500,000 — a quadratic, not exponential, speedup.
The mechanism is amplitude amplification. You start in an equal superposition, apply an oracle that flips the phase of the target state, then reflect all amplitudes about their mean. Each iteration rotates the state vector a little closer to the answer, so the probability of measuring the correct item climbs with each step until it peaks near (π/4)√N iterations. Overshoot and the probability falls again — the number of iterations must be tuned.
Shor vs Grover at a glance
| Property | Shor | Grover |
|---|---|---|
| Problem | Integer factoring / discrete log | Unstructured search |
| Speedup | Exponential | Quadratic |
| Complexity | O((log N)³) | O(√N) |
| Core engine | Quantum Fourier Transform | Amplitude amplification |
| Main victim | RSA, ECC, Diffie-Hellman | Symmetric keys, hash preimages |
| Mitigation | Post-quantum crypto (lattices) | Double the key length |
Grover only halves the effective bit-strength of a symmetric cipher: AES-256 drops to an AES-128-equivalent security level. That is why doubling key sizes is a sufficient defence against Grover, but not against Shor.
Why this matters for hardware and security engineers
These algorithms are not abstractions for the VLSI community — they are shaping silicon roadmaps. Error-corrected quantum hardware demands enormous control circuitry, cryogenic ASICs, and classical co-processors, all problems being solved with EDA toolchains from Synopsys, Cadence, and Siemens EDA. On the defensive side, NIST has already standardised post-quantum algorithms (ML-KEM / Kyber, ML-DSA / Dilithium) whose lattice arithmetic is now being hardened into secure-element RTL. If you are designing a hardware root-of-trust today, you are already making decisions that assume Shor will one day be real. Teams building this kind of secure silicon — such as the design services group at Avecas — treat post-quantum readiness as a requirement, not a research curiosity.
To see how these algorithms compare against conventional computation, read our deeper explainer on quantum vs classical computing, and if you want the number-theory background, our note on the quantum Fourier transform explained walks through the engine inside Shor step by step.
Want to go from "I've heard of qubits" to writing real circuits? Explore CourseTron's quantum and VLSI tracks on our courses page and build the foundations interviewers actually test.
Frequently asked questions
Does Grover's algorithm break AES?
No. Grover only provides a quadratic speedup, which effectively halves a symmetric cipher's security margin. AES-256 still offers 128-bit effective security against a quantum attacker, which remains infeasible. Simply using a longer key neutralises Grover.
How many qubits does Shor need to break RSA-2048?
A few thousand logical qubits in theory, but with quantum error correction that translates to roughly 20 million noisy physical qubits and many hours of runtime. Current hardware is orders of magnitude short, which is why RSA is not broken today.
Is quantum computing already a threat to today's encrypted data?
Indirectly. "Harvest now, decrypt later" means adversaries can store encrypted traffic today and decrypt it once a capable quantum computer exists. This is why migration to post-quantum cryptography has already begun.
Why is Shor exponentially faster but Grover only quadratically faster?
Factoring has hidden algebraic structure (periodicity) that the Quantum Fourier Transform exploits for an exponential gain. Unstructured search has no such structure to exploit, so amplitude amplification can only deliver a provably optimal quadratic improvement.