Papex

Open problem · Computer science · Open

BQP versus NP

Can quantum computers solve NP-complete problems efficiently, and can they efficiently solve problems outside NP?

Summary

BQP is the class of problems a quantum computer solves in polynomial time with bounded error. It contains integer factorisation, through Shor’s algorithm, but whether it contains NP, or lies inside it, is unknown.

Why it is open

BQP (bounded-error quantum polynomial time) is the class of decision problems that a quantum computer can solve in polynomial time with an error probability of at most 1/3 on every input [3, 11]. Ethan Bernstein and Umesh Vazirani defined it in 1993 and showed that it contains BPP, the problems that classical randomised algorithms solve in polynomial time, and lies inside PSPACE, the problems solvable with polynomial memory [3, 7]. NP is the class of problems whose "yes" answers have certificates that can be checked in polynomial time [7] (see the Papex page P versus NP).

The question has two halves, whether NP is contained in BQP and whether BQP is contained in NP, and neither has been settled [5, 7, 15]. A proof that NP is not contained in BQP would also prove P ≠ NP, and Scott Aaronson wrote in 2016 that there is "little hope" of one at present; no one even knows how to prove a conditional statement such as "if NP ⊆ BQP then PH collapses", where PH, the polynomial hierarchy, is a tower of classes built on NP [5, 7]. Separating BQP from classical classes is also hard: because BQP lies inside PSPACE, Charles Bennett, Bernstein, Gilles Brassard and Vazirani noted in 1997 that BQP ≠ BPP cannot be proved without settling whether P = PSPACE [3].

Many results are proved relative to an oracle, a black box that an algorithm can query at unit cost; they show that certain approaches cannot work but do not settle the question without the oracle [3, 5].

A resolution would be a proof of either inclusion or of its failure; no prize is attached, and this page's status follows the Wikipedia list of unsolved problems in computer science, which asks "What is the relationship between BQP and NP?" [15].

What is known

Quantum algorithms for problems in NP (1994–2016). Peter Shor presented polynomial-time quantum algorithms for factoring integers and computing discrete logarithms in 1994 [2]. Both lie in NP ∩ co-NP, as do "almost all the problems for which we have quantum algorithms", Aaronson noted in 2010 [5]; such problems have "significant algebraic structure and are not believed to be NP-complete", Takashi Yamakawa and Mark Zhandry write [12] (see Complexity of integer factorisation). Lov Grover's algorithm finds a marked item among N unsorted items in O(√N) steps [1]. For most NP-complete problems the fastest known quantum algorithm runs Grover's search on top of the best classical algorithm, a quadratic speed-up at most; "as far as anyone knows today", Aaronson wrote, even a quantum computer would need exponential time to solve 3SAT [7].

Limits of black-box search (1997). Bennett and colleagues proved that, relative to a random oracle and with probability 1, a quantum computer cannot solve NP in time o(2^(n/2)) for inputs of length n; Grover's algorithm shows that this bound is tight [3]. They stressed that the result does "not rule out the possibility that NP ⊆ BQP"; it shows that there is "no black-box approach" to NP-complete problems through quantum effects alone [3].

Quantum computation beyond NP, relative to oracles (1993–2026). Bernstein and Vazirani's recursive Fourier sampling problem already gives oracles relative to which BQP is not contained in NP [5]. In 2010 Aaronson called the wider question, whether BQP lies anywhere in PH, one of the "grand challenges" of the field, and proposed Fourier Checking, later known as Forrelation, as a candidate [5, 9]. Ran Raz and Avishay Tal resolved the oracle version in 2019: they gave a distribution that one quantum query distinguishes from uniform, while constant-depth classical circuits of quasi-polynomial size gain only a vanishing advantage; this yields an oracle relative to which BQP is not contained in PH, and so not in NP [5, 9]. In 2022 Yamakawa and Zhandry showed that relative to a random oracle, which has no special structure, some NP search problems can be solved by quantum but not by classical randomised polynomial-time algorithms [12]. In a September 2026 preprint, not peer reviewed, Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit and Tal construct an oracle relative to which BQP is not contained in IP, the class of problems with interactive proofs [14]. The authors state that the "proof idea underlying an initial version of the main theorem" was "generated using ChatGPT 6 Astra", and that they verified, simplified and developed the argument [14].

Heuristics for hard optimisation (2001–2025). In 2001 Edward Farhi and colleagues gave numerical evidence that the quantum adiabatic algorithm, which slowly changes a Hamiltonian into one whose lowest-energy state encodes the answer, solves random instances of the NP-complete Exact Cover problem in polynomial time; their simulations had at most 20 variables [4]. Later work built 3SAT instances on which it takes exponential time when the change is linear [4]. In 2010 Boris Altshuler, Hari Krovi and Jérémie Roland argued that, through a phenomenon similar to Anderson localisation, exponentially small energy gaps appear near the end of the algorithm on large random instances, so that it gets "trapped in one of the numerous local minima" [6]. In a 2025 paper, Stephen Jordan and colleagues introduced decoded quantum interferometry (DQI), which uses the quantum Fourier transform to turn optimisation problems into decoding problems [13]. For approximating optimal polynomial fits over finite fields it "achieves a superpolynomial speed-up over known classical algorithms"; on a constructed max-XORSAT instance it beat simulated annealing, but "a tailored classical solver can outperform DQI" there [13].

Quantum advantage experiments (2019–2023). In October 2019 Frank Arute and colleagues reported that the 53-qubit Sycamore processor sampled one instance of a random quantum circuit a million times in about 200 seconds, a task they estimated would take a state-of-the-art classical supercomputer about 10,000 years [8, 11]. In 2022 Feng Pan, Keyang Chen and Pan Zhang classically generated one million samples for Google's 53-qubit, 20-cycle Sycamore circuit, at a fidelity of about 0.0037, in about 15 hours on 512 GPUs, and estimated "a few dozens of seconds" on an exascale supercomputer [10]. Dominik Hangleiter and Jens Eisert describe such random sampling as a test of the extended Church–Turing thesis, which holds that any physical computer can be simulated efficiently by a classical one; the tasks are "presumably not computations that solve a relevant computational problem" [11]. These experiments test quantum against classical computers on sampling tasks; they do not involve NP-complete problems [8, 11].

What researchers believe. "Most quantum computing researchers conjecture" that NP is not contained in BQP, Aaronson wrote in 2016 [7]. In 2010 he called it "extremely unlikely" that quantum computers solve NP-complete problems in polynomial time, while noting that no one regards the oracle evidence "as decisive"; for the other half, the "default" conjecture is that BQP lies outside PH [5].

Main approaches

Black-box lower bounds. Prove limits on quantum or classical algorithms that access the input only through an oracle [3, 9]. Strongest evidence: the tight bound for search [1, 3], the separation of BQP from PH [9] and, in a 2026 preprint, from IP [14]. Main difficulty: oracle results do not rule out NP ⊆ BQP [3]; without an oracle, a proof that NP ⊄ BQP would imply P ≠ NP [7], and BQP ≠ BPP cannot be proved without settling P versus PSPACE [3].

Using structure in optimisation. Look for quantum algorithms that exploit the structure of hard instances instead of brute-force search [4, 13]. Strongest evidence: the superpolynomial speed-up of DQI over known classical algorithms for polynomial fitting [13]. Main difficulty: that speed-up rests on algebraic structure, a tailored classical solver beat DQI on its test without algebraic structure [13], and the adiabatic algorithm fails on large random instances [6].

Verifiable advantage for NP search. Find problems whose solutions a classical computer can check but only a quantum computer can find quickly [12]. Strongest evidence: the random-oracle separation of Yamakawa and Zhandry, which needs no algebraic structure [12]. Main difficulty: outside the oracle model, replacing the random oracle with a hash function such as SHA-2 gives a construction that the authors call "quite plausibly secure", not a proof [12].

Hardware demonstrations. Show a quantum device outperforming the best classical methods on a concrete task [8, 11]. Strongest evidence: random-circuit sampling on Sycamore in 2019 [8]. Main difficulty: classical simulation methods improved after the claim [10], and sampling tasks bear on quantum versus classical computation, not on NP-complete problems [7, 11].

Open sub-questions

  1. A conditional consequence. Can any unlikely classical consequence of NP ⊆ BQP, such as a collapse of the polynomial hierarchy, be proved? Aaronson wrote in 2005 and 2016 that none was known [4, 7].
  2. DQI without algebra. For which families of sparse max-XORSAT instances, if any, does DQI with a strong decoder beat the best tailored classical solver [13]?
  3. Adiabatic paths. Do the exponentially small gaps found for large random instances [6] also appear for paths between the initial and final Hamiltonians other than a linear interpolation [4]?
  4. Cost of classical sampling. How does the cost of tensor-network sampling like that of Pan and colleagues grow with qubits and cycles at the fidelities reported in experiments [8, 10]?
  5. Instantiating the oracle. With SHA-2 in place of the random oracle, is the Yamakawa–Zhandry search problem classically hard under a standard assumption, or does a classical algorithm solve it [12]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC '96), 212–219. 10.1145/237814.237866 · Checked 15 Oct 2026
  2. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5), 1484–1509. 10.1137/S0097539795293172 · Checked 15 Oct 2026
  3. Bennett, C. H., Bernstein, E., Brassard, G. & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM Journal on Computing 26(5), 1510–1523. 10.1137/S0097539796300933 · Checked 15 Oct 2026
  4. Aaronson, S. (2005). Guest column: NP-complete problems and physical reality. ACM SIGACT News 36(1), 30–52. 10.1145/1052796.1052804 · Checked 15 Oct 2026
  5. Aaronson, S. (2010). BQP and the polynomial hierarchy. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC '10), 141–150. 10.1145/1806689.1806711 · Checked 15 Oct 2026
  6. Altshuler, B., Krovi, H. & Roland, J. (2010). Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences 107(28), 12446–12450. 10.1073/pnas.1002116107 · Checked 15 Oct 2026
  7. Aaronson, S. (2016). P =? NP. In Open Problems in Mathematics, Springer, 1–122. 10.1007/978-3-319-32162-2_1 · Checked 15 Oct 2026
  8. Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R. et al. (2019). Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510. 10.1038/s41586-019-1666-5 · Checked 15 Oct 2026
  9. Raz, R. & Tal, A. (2022). Oracle separation of BQP and PH. Journal of the ACM 69(4), 1–21. Conference version in STOC 2019 ( 10.1145/3313276.3316315) · Checked 15 Oct 2026
  10. Pan, F., Chen, K. & Zhang, P. (2022). Solving the sampling problem of the Sycamore quantum circuits. Physical Review Letters 129(9), 090502. 10.1103/PhysRevLett.129.090502 · Checked 15 Oct 2026
  11. Hangleiter, D. & Eisert, J. (2023). Computational advantage of quantum random sampling. Reviews of Modern Physics 95(3), 035001. 10.1103/RevModPhys.95.035001 · Checked 15 Oct 2026
  12. Yamakawa, T. & Zhandry, M. (2024). Verifiable quantum advantage without structure. Journal of the ACM 71(3), 1–50. 10.1145/3658665 · Checked 15 Oct 2026
  13. Jordan, S. P., Shutty, N., Wootters, M., Zalcman, A., Schmidhuber, A., King, R. et al. (2025). Optimization by decoded quantum interferometry. Nature 646(8086), 831–836. 10.1038/s41586-025-09527-5 · Checked 15 Oct 2026
  14. Bouland, A., Huang, A., Natarajan, A., Shalit, I. & Tal, A. (2026). BQP ⊆ IP does not relativize. Preprint, arXiv:2609.25680 (version 1, 22 September 2026), not peer reviewed. Source · Checked 15 Oct 2026
  15. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 15 Oct 2026

Page reviewed 15 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Computing