NP versus BQP
Determine whether ; equivalently, whether an NP-complete decision problem has a polynomial-time bounded-error quantum algorithm.
Problem statement
Determine whether ; equivalently, whether an NP-complete decision problem has a polynomial-time bounded-error quantum algorithm.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
No NP-complete problem is known to be in BQP, and none is proved to lie outside it. The conjectural answer is that quantum computers cannot efficiently solve every NP problem, but this is an unrelativized containment question, not a theorem about generic search alone.
What is known: Bennett–Bernstein–Brassard–Vazirani establish black-box lower bounds, including the quantum-query cost of searching unstructured possibilities, matching Grover's algorithm. Their oracle results give evidence against the containment. They do not rule out algorithms exploiting the structure of SAT or other NP-complete problems; an oracle-query lower bound is not an ordinary running-time lower bound.
A resolution would distinguish quantum speedups for structured problems from efficient solution of all efficiently checkable search problems. Related: A1, A15.
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
- [1]Bennett, Bernstein, Brassard & Vazirani, 'Strengths and weaknesses of quantum computing', SIAM J. Comput. 26 (1997) link
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.