Whether NP is contained in BQP — equivalently, whether an NP-complete problem such as SAT admits a polynomial-time bounded-error quantum algorithm — is a central open problem of quantum computational complexity, closely tied to P versus NP because a negative answer would prove P ≠ NP and a positive answer would place all of NP (indeed the whole polynomial hierarchy) within efficient quantum computation. Neither direction is known: no quantum algorithm is known to solve an NP-complete problem in polynomial time, and no lower-bound technique separates NP from BQP; moreover, oracle evidence points in both directions, so relativizing techniques cannot settle the question. A 2023–2024 preprint by Reiner Czerwinski, 'NP-hard problems are not in BQP' (arXiv:2311.05624), claims an unconditional proof that no NP-hard problem lies in BQP, deriving P ≠ NP as a corollary and stating that the paper includes a solution of the P vs NP problem. The claim is not accepted: a detailed comment by Chavrimootoo (arXiv:2406.08495) shows the key step rests on a false undecidability claim — the relevant process is computable in exponential time — and concludes the paper establishes none of its claimed separations. The problem, in its standard unrelativized form, remains open.

Background

A decision problem is in NP if membership has certificates verifiable in polynomial time; SAT, the satisfiability of Boolean formulas, is the canonical NP-complete problem, to which every other NP problem reduces in polynomial time. P, the class of problems solvable in polynomial time, is contained in NP, and whether P = NP is the famous Millennium Problem, open since 1971.

BQP (bounded-error quantum polynomial time) is the accepted formalization of the problems efficiently solvable by a quantum computer: decision problems decidable by a family of quantum circuits whose size grows polynomially with the input length and which is uniform — meaning a polynomial-time classical algorithm generates the circuit for each input — with acceptance probability at least 2/3 on yes-instances and at most 1/3 on no-instances. Classical circuits are a special case, so P ⊆ BQP, and BQP is contained in PSPACE. Shor's algorithm places integer factorization and discrete logarithms in BQP — natural problems not known to be in P — showing genuinely nontrivial quantum computational power. Grover's algorithm searches an unstructured space of 2n2^n candidates in O(2n/2)O(2^{n/2}) quantum steps, and the BBBV theorem of Bennett, Bernstein, Brassard, and Vazirani proves a matching Ω(2n/2)\Omega(2^{n/2}) lower bound in the black-box model, where the search space is accessible only through an oracle; this quadratic speedup is the best quantum computation offers for unstructured search.

The open question is whether NP ⊆ BQP. Because BQP is closed under polynomial-time many-one reductions, this is equivalent to asking whether SAT — or any single NP-complete problem — is in BQP. No quantum algorithm is known for any NP-complete problem beyond Grover-type quadratic speedups, and no lower-bound technique excludes a polynomial-time one. The two possible answers both have dramatic consequences: if NP ⊆ BQP, then the entire polynomial hierarchy PH — the union over kk of the levels ΣkP\Sigma_k^P obtained by adding kk alternating rounds of nondeterministic quantification — is contained in BQP, since a BQP machine with a BQP oracle gains no additional power; if NP ⊄ BQP, then P ≠ NP follows immediately from P ⊆ BQP.

Relativized evidence points in both directions. Bennett, Bernstein, Brassard, and Vazirani constructed an oracle relative to which NP ⊄ BQP, and Raz and Tal, building on the Forrelation problem of Aaronson and Ambainis — an oracle problem asking whether one Boolean function is strongly correlated with the Fourier transform of another — proved there is an oracle relative to which BQP ⊄ PH, hence relative to which BQP ⊄ NP. A relativizing proof technique — one that holds relative to every oracle — therefore cannot resolve the question in either direction. Aaronson's 2005 survey of physical proposals for solving NP-complete problems (soap bubbles, protein folding, quantum computing, and others) frames the quantum case as unresolved, and the question remains a standard entry in lists of open problems in quantum complexity theory.

Problem Statement

Is NP⊆BQPNP \subseteq BQP? That is, does there exist a bounded-error quantum polynomial-time algorithm for SAT — a polynomial-time-uniform family of polynomial-size quantum circuits that decides satisfiability with two-sided error at most 1/31/3 — or equivalently for any (and hence every) NP-complete problem?

A resolution is a proof that NP⊆BQPNP \subseteq BQP or a proof that NP⊈BQPNP \nsubseteq BQP; a proof of non-containment would in particular prove P≠NPP \neq NP.

The question is the standard unrelativized one. Results that do not answer it include: black-box or query lower bounds such as the Bennett–Bernstein–Brassard–Vazirani (BBBV) Ω(2n/2)\Omega(2^{n/2}) bound for unstructured search; oracle separations in either direction; results about restricted circuit families, sub-uniform generation, or non-uniform (advice-based) classes; and average-case results over restricted input distributions. On scope: the phrase 'NP-hard problems in BQP' reduces to this question for all decidable cases, since undecidable NP-hard sets are trivially outside BQP; the meaningful content is precisely whether NP — equivalently SAT — lies in BQP.

References

  1. Reiner Czerwinski, 'NP-hard problems are not in BQP', preprint 2023, revised through v3 October 2024, arXiv:2311.05624, https://arxiv.org/abs/2311.05624
  2. Michael C. Chavrimootoo, 'A Brief Note on a Recent Claim About NP-Hard Problems and BQP', 2024, arXiv:2406.08495, https://arxiv.org/abs/2406.08495 (a comment on Czerwinski's preprint 'NP-hard problems are not in BQP')
  3. Michael C. Chavrimootoo, Tran Duy Anh Le, Michael P. Reidy, Eliot J. Smith, 'On Czerwinski's "P ≠ NP relative to a P-complete oracle"', 2023, arXiv:2312.04395, https://arxiv.org/abs/2312.04395
  4. Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. 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
  5. Lov K. Grover, 'A fast quantum mechanical algorithm for database search', Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC '96), pp. 212-219, 1996, DOI: 10.1145/237814.237866, https://doi.org/10.1145/237814.237866
  6. Ran Raz, Avishay Tal, 'Oracle Separation of BQP and PH', Journal of the ACM 69(4):1-21, 2022, DOI: 10.1145/3530258, https://doi.org/10.1145/3530258 (preliminary version in Proceedings of STOC 2019, pp. 13-23, DOI: 10.1145/3313276.3316315, https://doi.org/10.1145/3313276.3316315)
  7. Scott Aaronson, 'NP-complete Problems and Physical Reality', ACM SIGACT News, March 2005, arXiv:quant-ph/0502072, https://arxiv.org/abs/quant-ph/0502072
  8. 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
  9. Scott Aaronson, Andris Ambainis, 'Forrelation: A Problem that Optimally Separates Quantum from Classical Computing', 2014, arXiv:1411.5729, https://arxiv.org/abs/1411.5729 (published in preliminary form as 'Forrelation' in STOC 2015, pp. 307-316, DOI: 10.1145/2746539.2746547, https://doi.org/10.1145/2746539.2746547)
  10. Jonah Librande, 'BQP is not in NP', 2022, arXiv:2209.10398, https://arxiv.org/abs/2209.10398