Peter Shor's discovery of polynomial-time quantum algorithms for integer factorization and discrete logarithms demonstrated an exponential quantum speedup on problems of cryptographic importance, and his 1997 SIAM Journal on Computing paper closed by asking how far the phenomenon extends. The physical-feasibility strand of Shor's discussion was resolved in principle by the quantum fault-tolerance threshold theorem of 1996-1998; the surviving open core is the algorithmic question Shor posed in two concrete instances: whether quantum computers can solve NP-complete problems in polynomial time (is NP contained in BQP, the class of problems solvable by quantum computers in polynomial time with bounded error), and whether the shortest vector problem on lattices (or its approximation version) admits a polynomial-time, or even asymptotically faster, quantum algorithm. Both strands remain open: the strongest adjacent results are an oracle separation showing black-box techniques cannot give exponential quantum speedups for NP, subexponential-time quantum algorithms for the dihedral hidden subgroup problem related to lattices, quantum worst-case reductions that underpin post-quantum lattice cryptography on the assumed absence of such algorithms, and a prominent 2024 preprint claiming a polynomial-time quantum algorithm for learning-with-errors-related lattice problems whose headline claim the author retracted after a bug was found. A resolution in either direction would directly determine whether quantum computers are general-purpose computational devices and whether lattice-based post-quantum cryptography stands.

Background

A quantum computer processes information stored in qubits, whose states may be superpositions of classical bit strings and evolve by reversible, unitary (wave-like) transformations; interference between the amplitudes of a superposition is the resource that can make quantum algorithms faster than classical ones. In 1994 Peter Shor showed that a quantum computer can factor integers and compute discrete logarithms in time polynomial in the number of digits of the input, whereas the best known classical algorithms for these problems are subexponential. Both algorithms reduce the number-theoretic task to a period-finding problem and solve it with the quantum Fourier transform, a quantum analogue of the discrete Fourier transform that can be computed efficiently on superpositions; both are instances of the abelian hidden subgroup problem, in which one must find a hidden subgroup of a group given a function that is constant on its cosets, and which quantum Fourier sampling solves efficiently whenever the group is abelian (commutative). Because factoring and discrete logarithms underpin widely deployed public-key cryptosystems, this was the first unconditional exponential quantum speedup on a natural problem of independent importance.

The complexity-theoretic yardsticks for asking how far this reaches are as follows. BQP is the class of decision problems solvable by a quantum computer in polynomial time with bounded error probability, the quantum analogue of the classical randomized class BPP; NP is the class of problems whose proposed solutions can be verified in polynomial time, and NP-complete problems, such as satisfiability of Boolean formulas, are the hardest problems in NP, widely believed to admit no polynomial-time classical algorithm at all (the P versus NP question). Grover's search algorithm gives a quantum square-root speedup for searching an unstructured database and is provably optimal for that black-box task, so generic search yields only a quadratic, not exponential, gain. Bennett, Bernstein, Brassard, and Vazirani proved around the same time as Shor's paper that relative to a uniformly random oracle, with probability one, NP cannot be solved by a quantum computer in time subexponential in the input size; such oracle (black-box) results constrain whole classes of algorithms but do not settle the unrelativized question.

Shor closed his paper with a section titled 'Comments and open problems', raising three linked issues: the physical feasibility of long quantum computations in the presence of imprecision and decoherence (the loss of quantum coherence through interaction with the environment), and whether software techniques could overcome hardware noise; whether quantum computers can efficiently solve NP-complete problems, which he called 'a Holy Grail of theoretical computer science'; and whether other important problems not known to be NP-complete, in particular finding a short vector in a lattice, 'seem as if it might potentially be amenable to solution by a quantum computer'. A lattice is the set of all integer linear combinations of a given basis of vectors in n-dimensional Euclidean space; the shortest vector problem (SVP) asks for a nonzero lattice vector of minimum Euclidean length, and its approximation version, the gap shortest vector problem, asks to distinguish lattices whose shortest vector is short from those where it is longer by a given factor. SVP is NP-hard in its exact and close-approximation forms (established shortly after Shor's paper), and the best known algorithms, classical and quantum, run in exponential time in the lattice dimension; approximating SVP within polynomial factors is the hardness assumption on which lattice-based, and hence post-quantum, cryptography is built.

On the physical-feasibility strand, the state of knowledge changed decisively within a few years: the fault-tolerance threshold theorem (Aharonov and Ben-Or; Knill, Laflamme, and Zurek, 1996-1998) proved that if the error rate per quantum gate is below some fixed constant, then arbitrarily long quantum computations can be performed accurately with only polylogarithmic overhead, using quantum error-correcting codes that encode quantum information redundantly so that noise can be detected and corrected without measuring, and hence destroying, the encoded data. This resolved Shor's 'software' question affirmatively in principle. The open questions that survive are the algorithmic ones.

Problem Statement

Determine whether the exponential quantum speedups that Shor established for factoring and discrete logarithms extend to the computational problems he explicitly named in his closing section. This comprises two linked worst-case, asymptotic questions:

(1) Can a quantum computer solve NP-complete problems in polynomial time? In complexity-theoretic terms, is NP contained in BQP, the class of decision problems solvable by a quantum computer in polynomial time with bounded error probability? Shor called this 'a Holy Grail of theoretical computer science' and noted only 'weak indications' (oracle evidence) against it; a resolution requires either a bounded-error polynomial-time quantum algorithm for an NP-complete problem such as Boolean satisfiability, or a proof that no such algorithm exists.

(2) Does the shortest vector problem on lattices admit a polynomial-time quantum algorithm? Given a basis of a lattice in n-dimensional Euclidean space, find a nonzero lattice vector of minimum length (SVP), or decide the gap version for a given approximation factor. Shor's own formulation was weaker: whether this problem admits any asymptotically faster quantum algorithm than the best classical one, i.e., a superpolynomial (including subexponential) quantum speedup. The strand is resolved by a quantum algorithm asymptotically faster than the best classical algorithms—a polynomial-time algorithm being the strongest form—or by a proof that no such faster quantum algorithm exists.

Both instances serve the single overarching objective Shor articulated: to decide whether quantum computers become general-purpose computational devices, capable of asymptotically faster solution of a wide class of important problems, or remain specialized tools for problems that reduce to the abelian hidden subgroup problem. The physical-feasibility portion of Shor's original discussion is excluded from this statement because the fault-tolerance threshold theorem resolved it in principle; experimental realization of large-scale fault-tolerant machines is an engineering program, not part of the algorithmic question.

References

  1. Peter W. Shor, 'Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer', SIAM Journal on Computing 26(5), 1484-1509, 1997. DOI: 10.1137/S0097539795293172, https://doi.org/10.1137/S0097539795293172 (author preprint arXiv:quant-ph/9508027, https://arxiv.org/abs/quant-ph/9508027)
  2. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani, 'Strengths and Weaknesses of Quantum Computing', SIAM Journal on Computing 26(5), 1510-1523, 1997. DOI: 10.1137/S0097539796300933, https://doi.org/10.1137/S0097539796300933 (preprint arXiv:quant-ph/9701001, https://arxiv.org/abs/quant-ph/9701001)
  3. Lov K. Grover, 'A fast quantum mechanical algorithm for database search', Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), 212-219, 1996. DOI: 10.1145/237814.237866, https://doi.org/10.1145/237814.237866
  4. Dorit Aharonov, Michael Ben-Or, 'Fault Tolerant Quantum Computation with Constant Error', arXiv:quant-ph/9611025, https://arxiv.org/abs/quant-ph/9611025 (STOC 1997; journal version 'Fault-Tolerant Quantum Computation with Constant Error Rate', SIAM Journal on Computing 38, 1207-1282, 2008, DOI: 10.1137/S0097539799359385, https://doi.org/10.1137/S0097539799359385)
  5. Emanuel Knill, Raymond Laflamme, Wojciech H. Zurek, 'Resilient Quantum Computation: Error Models and Thresholds', Proceedings of the Royal Society of London A 454, 365-384, 1998. DOI: 10.1098/rspa.1998.0166, https://doi.org/10.1098/rspa.1998.0166 (preprint arXiv:quant-ph/9702058, https://arxiv.org/abs/quant-ph/9702058)
  6. Greg Kuperberg, 'A subexponential-time quantum algorithm for the dihedral hidden subgroup problem', SIAM Journal on Computing 35(1), 170-188, 2005. DOI: 10.1137/S0097539703436345, https://doi.org/10.1137/S0097539703436345 (preprint arXiv:quant-ph/0302112, https://arxiv.org/abs/quant-ph/0302112)
  7. Oded Regev, 'Quantum Computation and Lattice Problems', SIAM Journal on Computing 33(3), 738-760, 2004. DOI: 10.1137/S0097539703440678, https://doi.org/10.1137/S0097539703440678 (preliminary version, 43rd IEEE Symposium on Foundations of Computer Science, 520-529, 2002, DOI: 10.1109/sfcs.2002.1181976, https://doi.org/10.1109/sfcs.2002.1181976)
  8. Oded Regev, 'On lattices, learning with errors, random linear codes, and cryptography', Journal of the ACM 56(6), Article 34, 1-40, 2009. DOI: 10.1145/1568318.1568324, https://doi.org/10.1145/1568318.1568324
  9. Scott Aaronson, 'Guest Column: NP-complete problems and physical reality', ACM SIGACT News 36(1), 30-52, 2005. DOI: 10.1145/1052796.1052804, https://doi.org/10.1145/1052796.1052804 (author's preprint, https://www.scottaaronson.com/papers/npcomplete.pdf)
  10. Chris Peikert, 'A Decade of Lattice Cryptography', Foundations and Trends in Theoretical Computer Science 10(4), 283-424, 2016. DOI: 10.1561/0400000074, https://doi.org/10.1561/0400000074
  11. Google Quantum AI and Collaborators, 'Quantum error correction below the surface code threshold', Nature 638, 920-926, 2025 (published online 9 December 2024). DOI: 10.1038/s41586-024-08449-y, https://doi.org/10.1038/s41586-024-08449-y
  12. Yilei Chen, 'Quantum Algorithms for Lattice Problems', IACR Cryptology ePrint Archive, Paper 2024/555, 2024 (received 10 April 2024, revised 19 April 2024). https://eprint.iacr.org/2024/555 (preprint; the author's revision note states that the claimed polynomial-time quantum algorithm for learning with errors with polynomial modulus-noise ratios does not hold, owing to a bug in Step 9 found by Hongxun Wu and, independently, Thomas Vidick)