BQP and Where Quantum Helps
BQP is the class of problems a quantum computer can solve efficiently, and it is believed to strictly extend classical polynomial time for some tasks.
The class
BQP (bounded-error quantum polynomial time) is the set of decision problems a quantum computer can solve in polynomial time with error probability below one third. It is the quantum analog of the classical randomized class BPP, and it captures what "efficiently solvable by a quantum computer" means.
How quantum computers gain power
A quantum computer manipulates a state in an exponentially large space using superposition and entanglement, and it steers interference so that wrong answers cancel and right answers reinforce. The trick is never just "try everything at once"; it is arranging interference so the measurement is likely to reveal the answer.
Where quantum clearly helps
- Factoring integers and discrete logarithms (Shor's algorithm), exponentially faster than any known classical method
- Simulating quantum systems, the original motivation, believed hard classically
- Unstructured search (Grover's algorithm), a quadratic speedup
Where it does not
Quantum computers are not a universal speedup. For many problems the best quantum algorithm is no better than the classical one. Grover's quadratic gain is real but modest, and it is proven optimal for unstructured search. There is no evidence quantum computers can solve NP-complete problems efficiently.
Where BQP sits
BQP contains P and is contained in PSPACE. Its exact relationship to NP is unknown; the two are believed incomparable, with BQP neither containing NP nor being contained in it. Factoring, in BQP, is thought not to be NP-complete, consistent with this picture.
The honest state of things
BQP marks a genuine but bounded advantage. The strongest case for quantum computing remains simulating quantum systems, exactly the class of problems that motivated the idea. For classical intractability rooted in combinatorial search, quantum machines offer no known escape.