The Quantum Threat

A sufficiently large, fault-tolerant quantum computer would shatter the public-key cryptography that secures the internet. Understanding exactly what breaks — and what merely needs strengthening — is the foundation of any migration plan.

Two quantum algorithms, two very different impacts

The quantum threat to cryptography comes down to two famous algorithms with wildly different consequences.

Shor's algorithm — the existential threat

Shor's algorithm (1994) solves integer factorization and discrete logarithms in polynomial time on a quantum computer. Those two problems are the entire foundation of classical public-key cryptography. A large fault-tolerant quantum computer running Shor's algorithm would break:

• RSA — factoring large integers becomes tractable.
• Finite-field Diffie-Hellman — the discrete log problem falls.
• Elliptic-curve crypto (ECDH, ECDSA, Curve25519) — the elliptic-curve discrete log falls too.

This is not a marginal weakening; it is a total collapse. Larger key sizes do not help, because Shor's runtime grows only polynomially. The only answer is to switch to algorithms based on different math — that is, post-quantum cryptography.

Grover's algorithm — a manageable nuisance

Grover's algorithm speeds up brute-force search, but only quadratically. Against an n-bit symmetric key, it reduces the effective search from 2^n to roughly 2^(n/2) operations — it halves the security level. This is real but generally manageable: in common engineering estimates, increasing symmetric key length offsets the quadratic speedup from Grover; the actual security margin still depends on the algorithm, implementation, and resource estimates.

What breaks, what survives

The headline: public-key crypto is doomed; symmetric crypto and hashes are fine with adequate sizes.

What is a CRQC?

The term that matters operationally is cryptographically relevant quantum computer (CRQC) — a machine large and reliable enough to run Shor's algorithm against real-world key sizes (e.g., factoring a 2048-bit RSA modulus or breaking a 256-bit elliptic curve). A CRQC is not just any quantum computer; it is one that crosses the threshold of practical cryptanalysis. No CRQC exists today, and credible estimates for when one might appear range from roughly a decade to several decades — with deep uncertainty in both directions.

The current hardware reality

It is essential to separate today's machines from the hypothetical CRQC.

NISQ machines

We live in the NISQ era — Noisy Intermediate-Scale Quantum. Current devices have tens to a few hundred physical qubits, but those qubits are noisy: they decohere quickly and accumulate errors that ruin long computations. NISQ machines cannot run Shor's algorithm at cryptographically relevant scales.

Logical versus physical qubits

Breaking RSA-2048 is estimated to require a few thousand logical qubits — qubits that behave perfectly. But logical qubits are built from many noisy physical qubits using quantum error correction, with overheads commonly cited at hundreds to thousands of physical qubits per logical qubit. The practical requirement is therefore on the order of hundreds of thousands to millions of physical qubits: early estimates put it near 20 million (Gidney–Ekerå, 2019), and a 2025 revision lowered it to under 1 million noisy qubits (Gidney, arXiv:2505.15917) — still far beyond today's hardware.

Error correction is the gating problem

The central engineering challenge is fault tolerance: error-correcting codes (such as surface codes) must suppress errors faster than they accumulate. Recent demonstrations of error correction at small scale are genuine progress, but a fault-tolerant CRQC remains a substantial leap away.

Standards & references

• NIST Post-Quantum Cryptography project — the program coordinating the quantum-safe transition.
• NIST IR 8547 — transition to post-quantum cryptography standards, including deprecation timelines.
• NSA CNSA 2.0 advisory — the Commercial National Security Algorithm Suite and its mandated quantum-safe algorithms.
• Resources — full standards register