BQP
/ B-Q-P /
A quantum computer is not just a faster ordinary computer; it computes by a genuinely different physics, manipulating quantum bits (qubits) that can be in superpositions and can interfere with one another like waves. BQP is the class of decision problems that a quantum computer can solve efficiently: in polynomial time, with bounded error (correct with high probability, like BPP but quantum). It is the honest definition of 'what quantum computers can do well'.
How does it work, and what is the real source of any speedup? A quantum algorithm spreads a computation across a superposition of many possibilities at once, then uses interference to make the wrong answers cancel out and the right answer reinforce, so that a final measurement is likely to read off something useful. The famous successes are specific: Shor's algorithm factors integers and computes discrete logarithms in polynomial time (problems believed hard classically, which is why it threatens RSA-style cryptography), and Grover's algorithm searches an unstructured space of N items in about square-root-of-N steps — a real but only quadratic speedup, not exponential. The power comes from exploiting hidden mathematical structure (like periodicity in factoring), not from blindly trying everything.
Now the crucial honesty, because this is the most over-hyped topic in the subject. A quantum computer is NOT a magic device that solves all NP problems instantly by 'trying every answer in parallel'. The superposition does explore many branches, but measurement collapses it to a single outcome, and without clever interference you cannot read off the one you want. It is widely believed that BQP does NOT contain all of NP — quantum computers are not thought to solve NP-complete problems like SAT or TSP efficiently. We know P is inside BQP, and BQP is inside PSPACE, but the exact relationship between BQP and classical classes (even whether BQP differs from P) is open. Quantum computing is a real and important frontier, not a universal shortcut.
Shor's algorithm shows the power and the limits at once. It factors a large number n in polynomial time on a quantum computer by finding a hidden period using a quantum Fourier transform — a task believed exponentially hard classically. But it works precisely because factoring has rich number-theoretic structure to exploit. There is no analogous quantum trick known for generic NP-complete search, which has no such structure.
Quantum speedups come from interference exploiting structure — not from trying all answers at once.
The biggest myth: a quantum computer does NOT solve NP-complete problems efficiently — BQP is not believed to contain NP. Superposition explores many states, but measurement returns just one, so 'parallel-trying every answer' is not how the speedups work; they come from interference on structured problems.