In short

BQP and NP are incomparable as far as anyone knows — no containment is proved in either direction, and both directions are conjectured to fail. Quantum computers do not, in general, solve NP-complete problems in polynomial time. The best known quantum attack on an NP-complete problem like 3-SAT is Grover's algorithm, which gives a quadratic speedup: 2^{n/2} quantum versus 2^n classical for n-variable SAT. That is still exponential. The BBBV theorem proves that in the unstructured oracle model no quantum algorithm can do better than \sqrt{N}, so no polynomial-time quantum SAT solver can arise from that route. In the other direction, BQP is not known to sit inside NP either: a quantum algorithm's output is not obviously classically verifiable. The Raz–Tal (2019) oracle separation shows BQP can even exceed the polynomial hierarchy (which contains NP) relative to an oracle. Factoring — the headline BQP problem — is not NP-complete; it sits in NP \cap coNP, a tight sliver that strongly suggests it is not NP-hard. The takeaway: "quantum computers solve NP" is one of the most durable and most wrong claims in popular science.

Open any mainstream article about quantum computing and you will see the claim, stated or implied, that quantum computers solve NP-hard problems in polynomial time. "Quantum annealers crack the travelling salesman problem." "Grover's algorithm cuts SAT to polynomial time." "Quantum will solve every NP-complete problem and revolutionise optimisation." All three statements are wrong. The last one is not even a misunderstanding — it is a clean confusion of what complexity class quantum computers live in.

This article maps the actual relationship between the classical class NP and the quantum class BQP. The headline: they are two different classes, defined by two entirely different games, and as far as anyone knows they are incomparable. Neither contains the other. The evidence says neither is likely to contain the other. Grover's algorithm offers a real but limited advantage on NP problems, and the BBBV theorem says nothing better is possible in the unstructured case.

By the end, you should never again read a quantum-computing article without mentally flagging the "quantum solves NP" claim as the error it is.

The two classes, in one paragraph each

You have met both classes, but they deserve a side-by-side recap because the confusion between them turns on mixing up their definitions.

NP is a classical verification class. A language L is in NP if there exists a polynomial-time classical algorithm V and a polynomial p such that for every yes-instance x \in L, there exists a witness w with |w| \leq p(|x|) and V(x, w) = 1; for every no-instance x \notin L, no such witness exists. NP is about checking — if someone hands you a proposed solution, can you verify it quickly? 3-SAT is in NP: if someone hands you a satisfying assignment to a Boolean formula, you plug it in and check each clause in polynomial time.

BQP is a quantum decision class. A language L is in BQP if there exists a polynomial-size family of quantum circuits \{C_n\} such that for every x \in L of length n, C_n(x) outputs 1 with probability \geq 2/3, and for every x \notin L, C_n(x) outputs 1 with probability \leq 1/3. BQP is about computing — can a quantum computer in polynomial time produce the right answer most of the time?

These are fundamentally different games. NP asks about the existence of short classical proofs. BQP asks about efficient quantum computation. There is no reason, a priori, that either should contain the other.

NP and BQP as different gamesTwo panel diagram side by side. Left panel: NP game — input x, witness w given by a prover, verifier V checks in polynomial time and returns yes or no. Right panel: BQP game — input x fed to a quantum circuit C_n, measurement returns yes or no with bounded error. Arrows and labels highlight that the games are structurally different.two different games — that is why incomparability is naturalNP — classical verificationinput xwitness w(from prover)Vpoly-time0/1short classical proof exists ⇒ acceptBQP — quantum computationinput xC_npoly-sizequantum circuit0/1probability ≥ 2/3 of correct answer
NP and BQP are defined by structurally different games. NP asks "does there exist a short classical proof that a polynomial-time classical verifier accepts?" BQP asks "can a polynomial-size quantum circuit output the right answer with probability $\geq 2/3$?" Different rules. No reason for one to contain the other.

Is BQP ⊆ NP?

You might hope that every quantum algorithm's output could be classically verified given a suitable witness. If a quantum computer says x \in L, maybe there is a short classical proof a classical verifier could check.

This is not known, and there are reasons to think it is false.

The intuition: a quantum algorithm's output is the result of interference among exponentially many amplitudes. Even if the final measurement outcome is classical, the reason the outcome is correct depends on the full quantum state, which classical verification cannot inspect. There is no obvious "compact classical certificate" that a quantum algorithm produced the right answer.

The formal evidence is stronger: Raz and Tal (2019) constructed an oracle O relative to which \mathrm{BQP}^O \not\subseteq \mathrm{PH}^O, where PH is the polynomial hierarchy — a whole tower of complexity classes built on top of NP and coNP. Since \mathrm{NP} \subseteq \mathrm{PH}, this implies \mathrm{BQP}^O \not\subseteq \mathrm{NP}^O for that oracle. In the black-box world, BQP can exceed not just NP but every constant-alternation level of classical complexity.

Raz–Tal does not directly prove \mathrm{BQP} \not\subseteq \mathrm{NP} in the unrelativised world, but it is strong evidence — if BQP were inside NP, it would be inside PH too, and Raz–Tal would have to fail oracle-relative to every oracle, which it doesn't.

The community's working belief is \mathrm{BQP} \not\subseteq \mathrm{NP}, but like its cousin conjecture \mathrm{BQP} \supsetneq \mathrm{BPP}, it has no unconditional proof.

Is NP ⊆ BQP?

The other direction is the one pop-science gets wrong. Does NP sit inside BQP — that is, does a quantum computer solve every NP problem in polynomial time?

No polynomial-time quantum algorithm is known for any NP-complete problem. That is the empirical answer, and after 30 years of intensive quantum-algorithm research it is quite a strong empirical answer. The theoretical answer is even sharper.

Grover's is the best quantum attack, and it's only quadratic

Grover's algorithm searches an unstructured space of N candidates in O(\sqrt{N}) queries for a marked item. Applied to a Boolean satisfiability problem with n variables, the search space has N = 2^n assignments, and Grover's runs in O(\sqrt{2^n}) = O(2^{n/2}) quantum queries. Compared to the classical brute-force O(2^n), this is a quadratic improvement.

But it is still exponential in n. For n = 100 variables:

2^{100} \approx 1.27 \times 10^{30} \text{ classical operations}, \qquad 2^{50} \approx 1.13 \times 10^{15} \text{ quantum operations}.

Classical brute force is infeasible. Quantum brute force is also infeasible — 10^{15} operations on a hypothetical quantum computer at 10^9 gates per second is 10^6 seconds, about 11 days. And that is for n = 100; at n = 200, Grover's already takes 2^{100} \approx 10^{30} operations, which is back to classical-infeasibility territory.

Quadratic speedup is not the same as polynomial time. A quadratic speedup of an exponential algorithm is still an exponential algorithm. Grover's does not put SAT in BQP.

The BBBV lower bound closes the door

Could a cleverer quantum algorithm do better than Grover's on unstructured search? The answer, remarkably, is no — and it is a theorem, not a conjecture.

The BBBV theorem (Bennett, Bernstein, Brassard, Vazirani 1997) proves that any quantum algorithm that searches N candidates for a marked item in the unstructured oracle model requires \Omega(\sqrt{N}) queries. The proof uses the polynomial method: the success probability of any T-query algorithm is a polynomial of degree \leq 2T in the oracle's input bits, and any polynomial that correctly distinguishes the all-zeros oracle from any single-one oracle must have degree \Omega(\sqrt{N}).

The implication: for any NP-complete problem attacked by unstructured search, Grover's \sqrt{2^n} is optimal. A polynomial-time quantum SAT algorithm — if it exists — would have to exploit structure specific to SAT, not just search the space of assignments faster.

Could there be such a structure-exploiting algorithm? Nobody knows. Nobody has found one in 30 years. Most researchers believe none exists, on the grounds that (a) SAT has been studied exhaustively by both classical and quantum algorithm designers, (b) the specific structural exploits known to give quantum speedups (hidden-subgroup problems, Fourier analysis on abelian groups) do not seem applicable to SAT, and (c) oracle separations suggest NP \not\subseteq BQP is plausible.

Grover's quadratic speedup on 3-SAT is still exponentialA two-line graph on a logarithmic y-axis showing operation count versus number of variables n. The upper line is 2 to the n (classical brute force); the lower line is 2 to the n over 2 (Grover's). Both grow exponentially; both cross feasibility limits before polynomial scaling ever catches up.Grover on 3-SAT: 2^(n/2) vs 2^n — quadratic, still exponentialn (number of variables)operations (log)05010015020010^010^1510^3010^4510^60feasibility wallclassical: 2^nGrover: 2^(n/2)at n=100: 2^100 classical, 2^50 quantumboth still exponential
Grover's algorithm gives a quadratic speedup on 3-SAT — $2^{n/2}$ quantum operations instead of $2^n$ classical — but both are exponential functions of $n$. The quadratic improvement halves the exponent, not the base. Quantum brute force on SAT runs into the feasibility wall only slightly later than classical brute force, at twice the number of variables.

Factoring is not NP-complete

A common confusion: "factoring is in BQP, and factoring sounds hard like NP-complete problems, so this shows BQP beats NP." This conflates two separate things.

Factoring sits in NP \cap coNP — it is in NP (the factorisation itself is a witness), and also in coNP (a proof that N has no non-trivial factorisation, in the form of a primality certificate, also works). Problems in NP \cap coNP are widely believed to be not NP-complete, because if any problem in NP \cap coNP were NP-complete, then NP = coNP, which is believed false (and would collapse the polynomial hierarchy).

So factoring is a special problem inside NP — one with more structure than generic NP problems. That structure is exactly what Shor's algorithm exploits. The fact that quantum algorithms solve factoring does not generalise to NP-complete problems; the quantum advantage comes from the hidden-subgroup structure specific to factoring, which 3-SAT does not have.

The rule: quantum speedups come from structure. Factoring has structure; 3-SAT does not. This is the consistent story the lessons-about-quantum-speedups article makes — quantum advantage is not uniform across NP.

Factoring sits in NP ∩ coNP — not NP-completeVenn-style diagram with two intersecting circles for NP and coNP, a small shared region NP ∩ coNP, a larger NP-complete region inside NP but outside coNP, and another NP region outside the intersection. Factoring is labelled inside the small NP ∩ coNP sliver; 3-SAT is labelled in the NP-complete region.factoring lives in a tight sliver — and sliver-problems are not NP-completeNPcoNPNP ∩ coNPfactoring3-SATNP-completeNP-complete problems cannot be in NP ∩ coNP unless NP = coNP — strongly believed false
Factoring sits in NP $\cap$ coNP — the sliver of NP problems that have both polynomial certificates for yes-instances and polynomial certificates for no-instances. Any NP-complete problem in NP $\cap$ coNP would imply NP = coNP, which would collapse the polynomial hierarchy. So factoring is believed *not* NP-complete. Its quantum speedup doesn't generalise to SAT or other NP-complete problems.

Hype check

Hype check. "Quantum computers solve NP-hard problems in polynomial time" is wrong, in exactly the senses above. It is not a controversial statement among researchers — it is a consensus error in popular coverage. When you see it, flag it. The correct statement: quantum computers give quadratic speedups on NP-complete problems via Grover's algorithm, which is not enough to put NP inside BQP, and the BBBV theorem proves this quadratic speedup is optimal in the unstructured model.

The sibling claim — "quantum annealers (like D-Wave) solve NP-hard optimisation" — is a stronger version of the same error. Quantum annealing is a heuristic, not a polynomial-time algorithm with provable guarantees. Its theoretical analysis (via the adiabatic theorem) permits exponential runtime in the worst case; no paper has demonstrated polynomial-time solutions to NP-hard problems via annealing, and the class of problems annealers reliably outperform classical solvers on is currently very limited.

The common thread: claims of quantum advantage on NP-complete problems do not survive scrutiny. The nearest honest claim is "quadratic speedup via Grover's", which is real but not revolutionary.

What quantum does do on NP-complete problems

The honest picture — so you know where the real value sits — is that quantum offers three things for NP problems, none of which is polynomial time.

Grover's search with amplitude amplification. Quadratic speedup for any search-verifiable NP problem. The constant in O(\sqrt{2^n}) matters; for SAT, 2^{n/2} is twice the exponent of improvement per doubling of quantum operations-per-second. Real but modest.

QAOA — Quantum Approximate Optimization Algorithm. A variational algorithm that tries to approximate solutions to optimisation problems (including NP-hard combinatorial ones). The theoretical performance guarantees are unclear — no rigorous quantum speedup has been proved for QAOA over classical approximation algorithms for any specific NP-complete problem as of 2026. It is a hopeful heuristic with strong empirical interest and no theorem.

Quantum walks on specific graphs. For some graph problems (element distinctness, triangle-finding), quantum-walk-based algorithms offer polynomial speedups (e.g. O(N^{2/3}) vs O(N^{3/4})). These apply to specific structured search problems, not generic NP-complete problems.

All three are on the speedup ladder: Grover (quadratic), QAOA (unknown), quantum walks (polynomial). None of them is on the exponential rung for NP-complete problems. The exponential rung is reserved for problems with hidden-subgroup structure, which NP-complete problems are not conjectured to have.

Example 1: brute-force 3-SAT at n=100 — classical vs quantum

Concrete numbers for a Boolean 3-SAT instance with n = 100 variables and, say, 10n = 1000 clauses. You want to decide whether there exists a satisfying assignment.

Setup. The search space is 2^{100} assignments. Classical brute force: try each, verify in O(m) = O(1000) time per trial. Grover's: encode the SAT predicate as a quantum oracle O_f where O_f|x\rangle = -|x\rangle if x satisfies the formula and O_f|x\rangle = |x\rangle otherwise; run O(\sqrt{2^{100}}) Grover iterations.

Step 1 — count classical operations. Classical brute force on 2^{100} candidates at 1000 gates per verification:

\text{classical ops} = 2^{100} \times 10^3 \approx 1.27 \times 10^{33}.

Why: we need a concrete number to compare against Grover's — exponent of the search size, linear per-trial verification.

At 10^{15} operations per second on a massive classical cluster, that is 10^{18} seconds — about 30 billion years, still 2 billion times the age of the universe.

Step 2 — count Grover operations. Grover's algorithm uses \lceil \pi/4 \cdot \sqrt{2^{100}} \rceil \approx 0.785 \times 2^{50} \approx 8.84 \times 10^{14} iterations. Each iteration applies the oracle once and the diffusion operator once; each oracle call encodes the SAT predicate, which requires O(m) = O(1000) gates plus ancilla overhead.

\text{quantum ops} = 8.84 \times 10^{14} \times 10^3 \approx 8.84 \times 10^{17}.

Why: Grover's iteration count is \pi/4 \cdot \sqrt{N} for a single marked item and scales as \sqrt{N/k} for k marked items — the formula above assumes the generic single-marked case.

Step 3 — compare. Classical: 1.27 \times 10^{33} ops \to 10^{18} seconds \to 3 \times 10^{10} years. Grover: 8.84 \times 10^{17} ops \to 10^{9} seconds (at 10^9 quantum gate operations per second) \to about 30 years.

Step 4 — note the key fact. Thirty years is much better than thirty billion years, but thirty years is still not "polynomial time." A true polynomial-time algorithm at n=100 would take perhaps milliseconds to seconds. Grover's gets from "age-of-universe infeasible" to "infeasible for a human lifetime" — a real speedup by \sim 10^{16}, but NP-complete problems are still exponentially hard even for quantum machines. At n = 200, the classical time becomes 2 \times 10^{60} years and Grover's becomes 3 \times 10^{15} years — both infeasible.

Result. Grover's speedup is quadratic in the exponent, meaning it halves the effective number of variables from the classical-attacker's perspective: a classically-secure 200-bit search space is only as secure as a 100-bit space against a Grover attacker. But both 100-bit and 200-bit search spaces are exponentially sized in n; halving the exponent does not turn an exponential algorithm into a polynomial one. NP-complete problems remain hard for quantum computers.

3-SAT at n=100: classical brute force vs GroverA horizontal bar chart comparing classical operations (10 to the 33) and Grover operations (10 to the 18). Both bars are long; the classical bar extends to the right edge while Grover is about half the log-length, illustrating that both are exponential but Grover is quadratically smaller.3-SAT at n=100: both exponential, quantum quadratically smaller10^010^1010^2010^3010^40operations (log scale)classical brute force — 10^33 ops — 30 billion yearsGrover — 10^18 ops — 30 yearsquadratic gap — neither feasible
At $n = 100$ variables, both classical brute force ($10^{33}$ operations) and Grover's ($10^{18}$ operations) are exponential in $n$. The quantum quadratic speedup is real but does not turn an exponential problem into a polynomial one. Both runtimes are beyond any useful horizon; NP-complete problems remain hard for quantum computers.

Interpretation. The example is the core argument in numbers. Grover's is the best known quantum attack on NP-complete problems; BBBV proves nothing better is possible in the unstructured model; and even the best-known-optimal quadratic speedup leaves NP-complete problems exponentially hard. Hence NP \not\subseteq BQP is believed, and the "quantum solves NP" claim is wrong.

Example 2: factoring is not NP-complete — here is why that matters

Take factoring: given N = pq where p, q are two large primes, find p and q. This problem is famously in BQP (Shor's algorithm) and famously conjectured to be outside BPP. Is factoring NP-complete?

Setup. We need to show factoring is in both NP and coNP, then invoke the (widely believed) conjecture that NP \neq coNP to conclude factoring is not NP-complete.

Step 1 — factoring is in NP. A factor p is a witness for "yes, N is composite" and, more usefully, a full factorisation is a witness for the decision variant "does N have a factor \leq k?". Given p \leq k and the claim that p divides N, a classical verifier checks in O((\log N)^2) time whether p \cdot (N/p) = N. So the decision variant is in NP.

Why: the verifier side of NP requires a witness and a fast check. A candidate factor is a perfectly compact witness, and modular arithmetic checks it in polylogarithmic time.

Step 2 — factoring is in coNP. The negation "no, N has no factor \leq k" also has a short classical witness: a certificate of primality of every possible factor candidate in a restricted range, or more efficiently a Pratt certificate of primality for the full N that rules out any small factors. Pratt (1975) gave a polynomial-size primality certificate, so the no-instance is also polynomial-verifiable.

Why: membership in coNP requires a short witness for no-instances. Pratt's primality certificate gives one. This is what makes factoring special among NP problems.

Step 3 — so factoring is in NP ∩ coNP. Combining the two: the decision variant of factoring ("does N have a factor \leq k?") is in both NP and coNP.

Step 4 — NP-complete problems are not in NP ∩ coNP (conjecturally). Suppose for contradiction factoring were NP-complete. Then every NP problem reduces to factoring in polynomial time. Since factoring is in coNP, every NP problem is in coNP via the reduction. So NP \subseteq coNP. By symmetry, coNP \subseteq NP. So NP = coNP. But NP = coNP implies the polynomial hierarchy collapses to its first level, a statement strongly believed false on independent grounds.

Therefore: assuming NP \neq coNP (which is widely believed), factoring is not NP-complete. It lives in the NP \cap coNP sliver, which generic NP-complete problems do not inhabit.

Result. Factoring's position in NP \cap coNP is exactly why Shor's algorithm works for it. NP \cap coNP problems have dual structural descriptions (both yes and no instances have short proofs), and that extra structure is the mathematical handhold quantum algorithms exploit. Generic NP-complete problems like 3-SAT have only the yes-instance witness structure, which is not enough for Shor-style exponential speedup. The quantum advantage on factoring does not generalise to NP-complete — not because of a technical obstacle, but because factoring is not really an NP-complete-style problem.

Factoring has dual witnesses; 3-SAT has only oneA two-column comparison. Left column for factoring: two arrow boxes pointing to yes-witness (a factor p) and no-witness (a primality certificate). Right column for 3-SAT: one arrow box pointing to yes-witness (a satisfying assignment) and a red X on the no-witness side indicating no known short certificate for unsatisfiability.factoring has a rare dual-witness structure; NP-complete problems don'tfactoring — NP ∩ coNPyes-witnessfactor p of Nno-witnessPratt cert.both directions have short proofs→ Shor exploits the structure3-SAT — NP-completeyes-witnessassignmentno-witness?✗no known short proof of unsatisfiability→ no structural handle for Shor
Factoring has short classical witnesses for both yes-instances (a factor) and no-instances (a primality certificate), placing it in NP $\cap$ coNP. 3-SAT has a yes-witness (the assignment) but no known short no-witness — that asymmetry is the NP-completeness signature. Shor's algorithm leverages factoring's dual structure; nothing analogous is known for 3-SAT.

Interpretation. This is the cleanest argument against the "quantum solves NP" claim. The one exponential quantum speedup the public knows about — Shor's on factoring — lives on a problem that is structurally different from NP-complete problems. The structure that makes Shor's work is also the structure that keeps factoring out of NP-complete's territory. The two observations reinforce each other: factoring's quantum speedup is special because factoring is special.

Common confusions

Going deeper

You have the incomparability picture and the main evidence. The rest of this section walks through the formal statements of the oracle separations, the details of the BBBV lower bound as applied to NP-complete problems, a more careful discussion of QAOA and adiabatic quantum computation as routes that have been tried (and so far not succeeded in putting NP inside BQP), and the relationship to other complexity classes like QMA. Optional reading beyond the main argument.

The polynomial hierarchy and the Raz–Tal separation

The polynomial hierarchy \mathrm{PH} is built out of alternating \exists and \forall quantifiers over polynomial-time verifiable predicates. Level \Sigma_1^p = \mathrm{NP}, level \Pi_1^p = \mathrm{coNP}, level \Sigma_2^p involves \exists \forall, and so on. PH contains every constant-alternation bounded class — a genuinely rich landscape.

Raz and Tal (2019) proved: there exists an oracle O such that \mathrm{BQP}^O \not\subseteq \mathrm{PH}^O. The specific problem is Forrelation: given two Boolean functions f, g: \{0,1\}^n \to \{\pm 1\} accessed via oracle, decide whether g is close to the Fourier transform of f. A BQP algorithm solves Forrelation in O(1) queries; Raz–Tal show any PH algorithm needs \Omega(\sqrt{N}/\log N) queries, which is exponential in n (here N = 2^n).

Because \mathrm{NP} \subseteq \mathrm{PH}, the same oracle gives \mathrm{BQP}^O \not\subseteq \mathrm{NP}^O. This is the strongest known oracle-relative evidence that NP does not contain BQP (and by symmetry-of-evidence, that BQP does not contain NP either).

BBBV applied to NP-complete problems

BBBV's statement in its cleanest form: any quantum algorithm that, given oracle access to f: \{0,1\}^n \to \{0,1\}, decides with probability \geq 2/3 whether there exists x with f(x) = 1, requires \Omega(\sqrt{2^n}) queries in the worst case.

Applied to SAT: the oracle f encodes the SAT predicate — f(x) = 1 iff x satisfies the formula. Any quantum algorithm that decides satisfiability by querying this oracle needs \Omega(\sqrt{2^n}) queries. Grover's matches this with O(\sqrt{2^n}) queries. Tight.

What BBBV does not rule out: a quantum algorithm that exploits the specific structure of the SAT predicate — the clause structure, the variable sharing, the resolution-style inference rules. If such an algorithm exists, BBBV does not constrain it (BBBV assumes the oracle is a black box). The question "does NP \subseteq BQP?" reduces to "does some NP-complete problem have a quantum algorithm that exploits its structure polynomially?" — and the empirical answer after 30 years is no, but no proof exists.

QAOA, adiabatic QC, and why they don't close the gap

Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm proposed by Farhi, Goldstone, Gutmann (2014) for combinatorial optimisation. The algorithm alternates two parameterised unitaries p times; classical optimisation tunes the parameters to maximise expected solution quality. For p = 1, QAOA on MaxCut achieves the approximation ratio 0.6924 — slightly better than the best classical polynomial-time approximation algorithm for some graph classes. But as p increases, the classical parameter optimisation becomes exponentially hard (the cost function has \exp(p) local minima), so QAOA doesn't give an unbounded advantage.

Adiabatic quantum computation (Farhi, Goldstone, Gutmann, Sipser 2000) starts in the ground state of an easy Hamiltonian and slowly evolves to the ground state of a hard Hamiltonian encoding the NP problem. The adiabatic theorem says if the evolution is slow enough, the system stays in the ground state throughout — and the final ground state encodes the answer. The catch: "slow enough" means the evolution time scales as 1/g^2_{\min} where g_{\min} is the smallest energy gap encountered during evolution. For NP-hard problems, the minimum gap is generically exponentially small, making the required evolution time exponential.

Both QAOA and adiabatic QC are respected research directions with real results on specific problems. Neither has produced a polynomial-time quantum algorithm for any NP-complete problem. The community consensus: these are heuristics that may give practical advantages on structured instances, not routes to putting NP in BQP.

BQP versus QMA — the real quantum analogue of NP

If NP is "polynomial-time classical verification," what is its quantum analogue? The answer is QMA — Quantum Merlin-Arthur — the class of decision problems with a quantum verifier given a polynomial-size quantum state as witness.

QMA contains BQP (a BQP machine can ignore the witness and compute the answer itself) and is believed to contain NP (with some technical caveats about classical vs quantum witnesses). So the containment chain is:

\mathrm{BQP} \subseteq \mathrm{QMA}, \qquad \mathrm{NP} \subseteq \mathrm{QMA}.

QMA is the "natural" quantum analogue of NP — it captures the essence of verification when the prover is allowed to send quantum information. The local Hamiltonian problem (ground-state energy of a local quantum Hamiltonian) is QMA-complete, as proved by Kitaev's quantum Cook-Levin theorem. This is the quantum analogue of 3-SAT being NP-complete.

The BQP-vs-NP question you might then restate: is BQP \subseteq NP or NP \subseteq BQP? The quantum-native version is: is BQP \subsetneq QMA? The latter is the focus of most modern quantum complexity research, because it has the right structural analogy. (See QMA defined for the detailed treatment.)

The integrated picture

Combining the BQP-vs-BPP and BQP-vs-NP results:

The landscape is messy and open. What's clean: quantum computers do not solve NP-complete problems in polynomial time, and no reasonable theoretical route suggests they should.

Indian context — IISc complexity theory and the research community

IISc Bangalore's Department of Computer Science and Automation has an active theoretical-CS group contributing to quantum complexity, including work on QMA-related problems and classical–quantum separations. The broader Indian theoretical-CS community (TIFR Mumbai, CMI Chennai, IIT Delhi) participates in complexity conferences like FOCS and CCC where results like the Raz–Tal separation are discussed. The training pipeline — undergraduate topology and algebra courses, followed by graduate-level complexity theory — is actively producing researchers who engage with these questions. India is not an outsider to this frontier; the frontier is thinly staffed everywhere, and IISc and TIFR hold respected positions in it.

Where this leads next

References

  1. Bennett, Bernstein, Brassard, Vazirani, Strengths and weaknesses of quantum computing (1997) — the BBBV theorem proving Grover's \sqrt{N} is optimal for unstructured search. arXiv:quant-ph/9701001.
  2. Raz and Tal, Oracle separation of BQP and PH (2019) — the exponential oracle separation between BQP and the polynomial hierarchy. ECCC TR18-107.
  3. Scott Aaronson, Shtetl-Optimized blog: BQP vs NP and related questions — accessible commentary on the conjectured incomparability.
  4. Wikipedia, BQP — the standard reference with the containment and separation diagrams.
  5. Wikipedia, NP-completeness — background on why factoring is not believed NP-complete.
  6. John Preskill, Lecture Notes on Quantum Computation, Chapter 6 — complexity-theoretic foundations of quantum computing. theory.caltech.edu/~preskill/ph229.