What a Speedup Means
Computer scientists measure an algorithm by how its running time grows with the size of the problem. If the time doubles when the input gains one bit, the growth is exponential, and problems become impossible after a few hundred bits. If the time grows like a fixed power of the input size, the growth is polynomial, and larger problems stay reachable. The best known classical factoring method sits between the two, and it is the reason a 2,048-bit RSA key is safe today: nobody has the centuries of computing it would take.
Shor’s algorithm factors in polynomial time. That is the dramatic case. Grover’s algorithm turns a search of N items into about √N steps, which is a real but far smaller gain: a problem that took a million steps takes a thousand. Most other proposed speedups fall in between or remain unproven.
| Problem | Best classical | Quantum | What it affects |
|---|---|---|---|
| Factoring and discrete logarithms | Sub-exponential: impractical beyond about 1,000 bits | Polynomial (Shor) | RSA, Diffie-Hellman, elliptic curves such as P-256 and X25519 |
| Unstructured search, such as trying every key | N steps | About √N steps (Grover) | Symmetric ciphers and hash functions, by a square root only |
| Simulating quantum systems | Exponential in the number of particles | Polynomial | Chemistry, catalysts, batteries, materials |
| Solving linear systems | Polynomial | Exponentially faster in special cases | Depends on loading the data into a quantum state, which is often the bottleneck |
| Optimization and machine learning | Varies | Unproven in general | Mostly heuristic claims; small or no advantage shown so far |
Shor’s Algorithm: Factoring by Finding a Rhythm
Peter Shor’s 1994 algorithm does not factor a number directly. It converts factoring into a different problem that a quantum computer happens to be good at: finding the period of a repeating pattern. Pick a random number a smaller than the number N you want to factor and look at the sequence of remainders of a, a², a³ and so on, each divided by N. The sequence repeats with some period r. Classically, finding r takes as long as factoring. Once r is known, a few lines of ordinary arithmetic almost always produce a factor of N.
The quantum part finds r. The computer prepares a register of qubits in a superposition of every exponent, computes the remainders for all of them in one pass, and the register becomes entangled with those results. A quantum Fourier transform then makes the amplitudes from every exponent interfere. Contributions add up only at multiples of the period and cancel everywhere else, so a measurement returns a value from which r can be read off. The whole thing is interference at the scale of thousands of qubits.
The same period-finding core solves the discrete logarithm problem, which is what elliptic-curve cryptography rests on. That matters for OWL, whose classical key agreement uses P-256 and X25519. A 2017 Microsoft Research estimate put a 256-bit curve at about 2,300 logical qubits, fewer than the roughly 4,100 that the same generation of estimates needed for RSA-2048. Elliptic curves are not a safer bet against Shor than RSA; they are a slightly easier target.
What It Costs
Logical qubits are the ones an algorithm counts. Physical qubits are the ones a machine has, and each logical qubit has to be built from many physical ones through error correction, because Shor’s algorithm runs for billions of gate operations and no physical qubit survives that long. The conversion rate depends on the physical error rate, and it has been the subject of a decade of estimates.
| Estimate | Physical qubits | Running time | Assumptions |
|---|---|---|---|
| Gidney and Ekerå, 2019 | About 20 million | About 8 hours | 0.1% gate error, surface-code error correction, microsecond cycle times |
| Gidney, 2025 | Under 1 million | Under a week | The same 0.1% error rate, with better arithmetic, denser storage of idle qubits and cheaper production of the special states the algorithm consumes |
| Largest machines, 2025 | About 100 to 1,100 | Not applicable | Error rates between 0.1% and 1%; a handful of logical qubits demonstrated |
Two things stand out. The required machine shrank twenty-fold in six years through better algorithms, with no change in the assumed hardware quality, and it may shrink again. And it is still about a thousand times larger than anything built. Nobody can say when the two lines cross. The planning assumption used by NIST and by OWL is that they will, and that data encrypted today will still matter when they do.
Grover’s Algorithm: A Square-Root Shortcut
Lov Grover’s 1996 algorithm searches an unstructured list. Given a test that recognizes the right answer, it finds that answer among N candidates with about √N uses of the test, where a classical search needs N/2 on average. It works by amplitude amplification: start with equal amplitudes on every candidate, let the test flip the sign of the right one, then reflect every amplitude about their average. Each round moves a little more amplitude onto the answer, and after about √N rounds a measurement returns it with high probability.
For a cipher, the test is “does this key decrypt the sample correctly?” and the candidates are all 2¹²⁸ keys of AES-128. Grover reduces the count to about 2⁶⁴ rounds, which is why the effective strength of a k-bit key is often quoted as k/2 bits against a quantum attacker. In practice the rounds have to run one after another, each one executing the whole cipher on a fault-tolerant machine, and 2⁶⁴ sequential rounds would take centuries even at a billion rounds per second. NIST’s assessment is that Grover offers far less practical advantage than the square root suggests. AES-256 keeps an effective 128-bit margin even on paper, which is why OWL continues to use it for content and for its key envelopes.
What about hash functions?
The same square root applies to finding an input that produces a given hash, so SHA-256 keeps a theoretical 128-bit margin. Finding two inputs with the same hash can in principle be cut further, to about 2⁸⁵ steps for SHA-256, but only with impractical amounts of quantum memory. Hashing and Key Derivation explains what hashes do in OWL; none of it needs to change.
Simulation and the Rest
The oldest argument for quantum computers is Richard Feynman’s from 1982: nature is quantum, so simulating it exactly needs a quantum machine. A molecule with a few dozen electrons already has more quantum states than any classical computer can track, which is why chemists rely on approximations. A fault-tolerant quantum computer could compute reaction energies for catalysts, battery materials and enzymes directly. Resource estimates for useful chemistry are smaller than for breaking RSA, which makes this the likeliest first practical application.
Beyond simulation, caution is warranted. The “quantum advantage” experiments of 2019 and 2025 ran sampling and physics-measurement tasks chosen because they are hard to simulate, not because anyone needed the answer, and classical methods have repeatedly narrowed the gap afterwards. Optimization and machine learning speedups are mostly heuristic and often depend on loading data into a quantum state, which can cost as much as the problem it was meant to accelerate. A measured reading of the field is Preskill’s 2018 paper on the “NISQ” era: noisy machines of intermediate scale that are scientifically interesting and not yet a general tool.
What This Means for Encryption Today
Shor’s algorithm is the reason every public-key method in use needs replacing, and the reason the replacements must be in place before the machine exists. Anyone who records encrypted traffic or copies a database of wrapped keys today can decrypt it when a large enough machine arrives. NIST’s draft transition plan proposes deprecating RSA and elliptic-curve algorithms after 2030 and disallowing them after 2035.
OWL has already moved the part that matters. The keys delivered to recipients are wrapped with ML-KEM-768 combined with P-256, so that confidentiality holds as long as either component holds, and the public ndevr.org endpoint supports hybrid post-quantum key agreement for HTTPS. The content itself stays under AES-256, which Grover does not meaningfully threaten. Post-Quantum Encryption lists exactly which layers are covered, and what it does not solve: signatures and password login remain classical for now, and a compromised device reads the plaintext whatever the algorithm.
Sources & Further Reading
- P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26, 1484 (1997); first presented in 1994.
- L. K. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings of STOC 1996.
- C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits”, arXiv:2505.15917 (2025); C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, Quantum 5, 433 (2021).
- M. Roetteler, M. Naehrig, K. M. Svore and K. Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms”, ASIACRYPT 2017; T. Häner, M. Roetteler and K. M. Svore, “Factoring using 2n+2 qubits with Toffoli based modular multiplication” (2017).
- NIST, Post-Quantum Cryptography FAQ, on Grover’s algorithm and symmetric key sizes; IR 8547 (initial public draft) on the transition timeline.
- J. Preskill, “Quantum Computing in the NISQ era and beyond”, Quantum 2, 79 (2018).
- F. Arute et al., “Quantum supremacy using a programmable superconducting processor”, Nature 574, 505 (2019); Google Quantum AI, “A verifiable quantum advantage” (October 2025).
- R. P. Feynman, “Simulating Physics with Computers”, International Journal of Theoretical Physics 21, 467 (1982).