Questions nobody has answered, with what is known, what is not, and what would settle each. Last checked 2 October 2026.
Open means no accepted proof either way. A problem is listed only when we can name the paper it comes from. The date above is the last time a person checked each entry against its source; fields move, and one entry below is about a claim that was withdrawn within days. If something here has been settled, tell us and it goes in the corrections log.
The same page also lists problems that sound open and are not, because the usual mistake is to treat a proven limit as a gap waiting for a clever idea.
Status: open. Shor’s 1994 algorithm factors a number in polynomial time on a quantum computer. No polynomial-time classical algorithm is known, and there is no proof that none exists.
Why it matters. “A quantum computer breaks RSA” is a statement about the quantum side. That factoring is hard for ordinary computers is an assumption the whole of RSA rests on, not a theorem.
What would settle it. A classical algorithm (it would end RSA without any quantum computer), or a proof of a superpolynomial classical lower bound (which would also separate complexity classes nobody has separated).
Source. P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26(5), 1997. On this site. The post-quantum page; Shor’s Clockwork does the classical finish.
Status: open. It is one of the Clay Mathematics Institute’s Millennium Prize problems. Whether every problem whose answer can be checked quickly can also be solved quickly is unknown.
Why it matters here. Whether quantum computers can solve NP-complete problems efficiently is a separate open question (NP versus BQP). Most researchers expect they cannot, but even a proof that P differs from NP would not establish it. A proof that P equals NP would. It is why “a quantum computer will solve optimisation” is a claim to test rather than a result.
What would settle it. A proof of P = NP, or of P ≠ NP (which would still leave NP versus BQP open). Nothing quantum is needed or known to be sufficient.
Source. S. Cook, “The complexity of theorem-proving procedures”, STOC 1971; the Clay Mathematics Institute problem statement by S. Cook, 2000. On this site. The Heuristic Arena and the optimisation course, where the pars are proven only because the instances are small enough to try everything.
Status: open. In 2018 Ewin Tang gave a classical algorithm for recommendation systems that matched the quantum one up to a polynomial factor, which removed the exponential advantage that had been claimed there. Several other quantum machine-learning speedups have been treated the same way since. Whether any exponential speedup survives for a natural task whose data starts out classical is unresolved. Contrived tasks with a proven separation exist (Liu, Arunachalam and Temme, Nature Physics 17, 1013, 2021, assuming the discrete-logarithm problem is hard classically).
What would settle it. A task with a proven separation, or a classical algorithm for every candidate. Until then, a quantum-learning speedup claim comes with the question “compared with the best classical algorithm that reads the data the same way?”.
Source. E. Tang, “A quantum-inspired classical algorithm for recommendation systems”, 2018 (published at STOC 2019). On this site. The AI page.
Status: open. For unstructured search the speedup is quadratic and that is proven to be the most there is (see below). Whether structured optimisation problems allow more, and whether any quantum method beats the best tuned classical heuristic on an instance somebody actually needs solved, has no accepted demonstration.
What would settle it. A named problem, a named instance family, a fixed budget and a fair classical baseline, with both sides tuned by someone who wanted the other to win.
Source. A. Abbas et al., “Challenges and opportunities in quantum optimization”, Nature Reviews Physics 6, 718 (2024). On this site. The Ledger tracks the specific claims and scores them on their own deadlines; Classical Strikes Back lets you be the classical side.
Status: open. No quantum algorithm is known that solves them efficiently, and there is no proof that none exists. The standards built on them (FIPS 203 and 204, finalised in August 2024) rest on that absence.
The 2024 episode. On 10 April 2024 Yilei Chen posted a paper claiming a polynomial-time quantum algorithm for the learning-with-errors problem with polynomial modulus-to-noise ratio, not for LWE in general. Within days Hongxun Wu and, independently, Thomas Vidick found a bug in step 9, and the author’s own note on the paper says he does not know how to fix it. The claim is withdrawn in practice; the question is back where it was. It is a fair picture of how fast a serious claim can fall, and of why we wait for the second pair of eyes.
What would settle it. A correct algorithm, or a reduction showing the problem is as hard as something already trusted for quantum machines. Neither exists.
Source. Y. Chen, “Quantum Algorithms for Lattice Problems”, IACR ePrint 2024/555, with the bug notice on its first page. On this site. The post-quantum page; Lattice Heist.
Status: open. The conjecture says that approximating the ground-state energy of a local Hamiltonian to within a constant fraction is still as hard as the hardest problems quantum computers can check. A necessary consequence, the “no low-energy trivial states” (NLTS) conjecture, was proved in 2022; the full conjecture was not.
Why it matters. It would say something about the limits of how well any machine, quantum or not, can approximate quantum systems, and it is tied to how much entanglement is unavoidable at low energy.
What would settle it. A proof or a disproof; NLTS was a step along the way and not the arrival.
Source. D. Aharonov, I. Arad and T. Vidick, “The quantum PCP conjecture”, SIGACT News 44(2), 2013 (arXiv:1309.7495), states the conjecture. A. Anshu, N. P. Breuckmann and C. Nirkhe, “NLTS Hamiltonians from good quantum codes”, STOC 2023, proved NLTS.
Each of these is a result with a proof. Looking for a gap in them is looking for a clever way around a theorem.
Some things here are open in a smaller way: we have made a call and cannot yet say whether it was right. The desk’s forecasts on the race page and the claims on the Ledger are written down with dates so that they can be scored, and The Standing scores yours the same way. How we check says what each layer of checking catches and misses.