Bqp Complexity Class Relation To Np

Short answer: BQP is the class of problems a quantum computer can solve efficiently with small error. NP is the class of problems whose solutions can be checked efficiently. Whether BQP contains NP-complete problems is open. What is known is that BQP sits inside PP and PSPACE, and relative to oracles, which are abstract black boxes, BQP and NP can behave very differently. So the complexity picture gives no proof that quantum computers solve NP-hard problems quickly, and no proof that they cannot.

The classes

Lecture notes from a Carnegie Mellon quantum computation course define NP through a prover and a verifier. The prover sends a polynomial-length proof, and the verifier checks it in deterministic polynomial time. If the statement is true some proof is accepted, and if it is false none is. The notes say P is contained in NP, since the verifier can ignore the proof, that NP is contained in PSPACE, and that it is not known whether BPP, the randomized class, is contained in NP.

A paper from 2000 on arXiv (quant-ph/0003035) asks how useful quantum computing can be, and what the complexity of BQP is. It asks whether BQP contains NP-complete problems such as graph 3-colorability, and how BQP relates to the polynomial-time hierarchy. The paper argues that BQP can be thought of as a regular complexity class, not conceptually much different from BPP, and that it is a rather robust class with much in common with other classes. It cites results that BQP can simulate any deterministic or probabilistic polynomial-time algorithm, that BQP of BQP equals BQP, and that BQP is contained in PP, which is contained in PSPACE.

Is NP in BQP?

The 2000 paper says that the question cannot be answered directly, but some unlikely consequences can be shown, for example that the polynomial-time hierarchy collapses. It also says that the only evidence at that time against BQP sitting in the polynomial-time hierarchy came from Bernstein and Vazirani, who built a relativized world with a language in the quantum class but not in BPP.

Oracle results

A 2022 paper presented at the Computational Complexity Conference shows how far BQP can be decoupled from classical classes in the black-box setting. The authors say one can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness of a quantum algorithm. They show an oracle relative to which NP with a BQP oracle is not contained in BQP with a polynomial-hierarchy oracle, resolving a 2005 problem of Fortnow, and as a corollary an oracle relative to which P equals NP but BQP differs from QCMA. They also show an oracle relative to which BQP with an NP oracle is not contained in the polynomial hierarchy with a BQP oracle, and oracles relative to which BQP equals P with a sharp-P oracle while the polynomial hierarchy is infinite, and where P equals NP but differs from BQP. They build on a 2018 result by Raz and Tal of an oracle relative to which BQP is not contained in the polynomial hierarchy.

What this does not tell you

Oracle results show what proof techniques cannot settle, and do not decide the real relationship between BQP and NP. The sources here do not show that quantum computers solve NP-complete problems, and they do not show that they cannot. The 2000 paper's claims about unlikely consequences are conditional.

FAQ

What is BQP?

The class of problems a quantum computer can solve efficiently with bounded error.

Is NP inside BQP?

Unknown. The 2000 paper notes that showing it would have unlikely consequences such as a collapse of the polynomial-time hierarchy.

What do we know for sure about BQP?

That it contains the efficiently solvable classical problems, and sits inside PP and PSPACE.

What do oracle results show?

That BQP can behave very differently from NP in black-box settings, per the 2022 paper.

Does this mean quantum computers cannot solve hard problems?

No. It means the exact power of BQP relative to NP is unresolved.