Short answer: BQP, bounded-error quantum polynomial time, is the class of problems feasible for a quantum computer, and complexity theory places it between classical probabilistic computing and the counting class P#P. Researchers have oracle evidence that BQP does not contain NP, and no one regards that evidence as decisive. This is theory, and it says nothing certain about what future hardware can do.
Where BQP sits
A 2009 arXiv paper on BQP and the polynomial hierarchy describes BQP as the class of all problems feasible for a quantum computer. It recalls that in the original 1993 paper defining BQP, Bernstein and Vazirani showed that BPP is contained in BQP, which is contained in P#P. Informally, the paper says, quantum computers are at least as fast as classical probabilistic computers and no more than exponentially faster, since they can be simulated using an oracle for counting. It adds that the upper bound was later improved to PP by Adleman, DeMarrais and Huang.
Evidence that quantum is stronger
The same paper says Bernstein and Vazirani gave evidence that BPP is not equal to BQP, with an oracle problem called Recursive Fourier Sampling that requires n to the power of order log n queries on a classical computer but only n queries on a quantum one. The case became dramatically stronger a year later, it says, when Shor, building on work of Simon, showed that factoring and discrete logarithm are in BQP.
What about NP-complete problems
The paper says that Bennett and co-authors gave oracle evidence that NP is not contained in BQP. It adds that while no one regards such evidence as decisive, today it seems extremely unlikely that quantum computers can solve NP-complete problems in polynomial time. A vast body of research seeks to map the boundary between the NP problems that are feasible for quantum computers and those that are not.
BQP and the polynomial hierarchy
The paper calls the question of whether BQP is in the polynomial hierarchy one of the grand challenges of the field, one that had essentially zero progress over sixteen years before its work. It says the default conjecture is presumably that BQP is not contained in PH, since no one knows what a simulation of BQP in PH would look like, and that before this work there was no formal evidence for or against it.
A 2022 paper from the Computational Complexity Conference says it builds on the 2018 achievement by Raz and Tal of an oracle relative to which BQP is not contained in PH. It shows that in the black-box setting BQP can be remarkably decoupled from classical classes like NP. For example, it reports an oracle relative to which NP with BQP access is not contained in BQP with PH access, resolving a 2005 problem of Fortnow, and an oracle relative to which P equals NP but BQP does not equal QCMA. It also reports an oracle relative to which BQP equals P#P and yet PH is infinite. These are oracle separations: they show what cannot be proven by relativizing techniques, not facts about the real world.
What this does not tell you
None of these papers proves that quantum computers are faster than classical ones for any real problem, because unconditional separations of BQP from classical classes remain open, and oracle results do not settle the unrelativized questions. Nor do the papers say anything about when useful hardware might exist.
FAQ
What is BQP?
The class of problems feasible for a quantum computer, per the 2009 paper.
Is BQP inside NP?
The sources do not say that. They say oracle evidence suggests NP is not contained in BQP, and that BQP is contained in P#P.
Can quantum computers solve NP-complete problems quickly?
The paper says it seems extremely unlikely, while noting that that evidence is not decisive.
What does an oracle result mean?
A result relative to a hypothetical oracle. It shows limits of relativizing proofs and is not a statement about the real world.
Why do Shor's results matter here?
They put factoring and discrete logarithm in BQP, which the paper says made the case for quantum power dramatically stronger.
All field notes