A different machine, not a faster one
In guide 1 of this rung you let a Turing machine flip coins and accepted a small chance of error; that gave you BPP, the problems a randomized machine solves efficiently. A quantum computer sounds like the same idea cranked up — "try everything at once" — but that slogan is the single most misleading thing ever said about it, and unlearning it is the whole point of this guide. A quantum machine is not a Turing machine running faster, and it is not a randomized machine with better dice. It is a different model of computation, with its own rule for how a configuration evolves, and from that rule comes its own complexity class, BQP (bounded-error quantum polynomial time).
Here is the honest core of the difference, in everyday terms. A randomized machine, at any moment, is in one definite configuration — you just do not know which, so you describe it with probabilities that are non-negative numbers summing to one. A quantum machine instead carries a list of amplitudes, one per possible configuration, and amplitudes are signed (they can be positive or negative, in fact complex). To read off the chance of seeing a given configuration when you finally measure, you square its amplitude. Probabilities only ever add up; amplitudes, because they have signs, can also subtract. That one fact — that two paths to the same outcome can cancel each other out — is the entire engine of quantum speed-up. Nothing here is mystical; it is bookkeeping with signed numbers instead of unsigned ones.
Interference, in one tiny picture
The smallest honest example uses one qubit and one gate. A qubit's configuration is captured by two amplitudes, one for the outcome "0" and one for the outcome "1". A randomized coin-flip gate would send a sure "0" to a half-and-half mixture, and flipping the same coin twice would just leave you at half-and-half — randomness never un-mixes. The quantum analogue, the Hadamard gate, does something randomness cannot: applied to a sure "0" it produces equal amplitudes for 0 and 1, but applied a second time the two routes into "1" carry opposite signs and cancel, while the two routes into "0" reinforce — so you land back on a sure "0" with certainty. Two random steps blur; two quantum steps can sharpen. That is interference doing visible work.
Coin (randomness): probabilities, never subtract
|0> --flip--> {0: 1/2, 1: 1/2} --flip--> {0: 1/2, 1: 1/2} blurred, stuck
Qubit (quantum): amplitudes are SIGNED, so they can cancel
|0> --H--> { 0: +1/sqrt2 , 1: +1/sqrt2 } (equal amplitudes)
--H--> outcome 0 : (+1/sqrt2)(+1/sqrt2) + (+1/sqrt2)(+1/sqrt2) = +1
outcome 1 : (+1/sqrt2)(+1/sqrt2) + (+1/sqrt2)(-1/sqrt2) = 0 <-- CANCELS
==> measure 0 with probability 1 (sharpened back to certainty)
Measure once -> ONE outcome, prob = amplitude^2. You never read all paths.What BQP is, and where it sits on the map
BQP is defined to be the exact quantum mirror of BPP. A language is in BQP if some polynomial-size sequence of quantum gates decides it: on every input the machine outputs the right answer with probability at least, say, 2/3, and as with BPP you can drive that 2/3 as close to certainty as you like by repeating and taking a majority vote. So BQP is "efficiently solvable by a quantum computer with a small, controllable chance of error". It is a perfectly respectable complexity class, defined by a resource bound (polynomial time) on a model (quantum gates), exactly like P and NP before it.
Where does it slot into the class map you have been building? Two inclusions are proved and worth the names. First, BPP is in BQP: a quantum machine can always choose not to interfere and just simulate fair coin flips, so anything randomness can do, quantum can do. Second, and the real ceiling, BQP is in PSPACE: you can simulate a quantum circuit on an ordinary Turing machine by, in effect, summing the amplitudes over all computation paths to each final configuration — there are exponentially many paths, but each is short, so you can total them up reusing only a polynomial amount of space. That single fact is a powerful sanity check on all the hype, and we unpack it next.
Why it is NOT a magic NP-solver
Now the headline correction. The popular claim is that a quantum computer simply cracks every NP-complete problem — every Sudoku, every travelling-salesman tour, every scheduling puzzle — by checking all candidate solutions at once. As far as anyone has ever proved, this is false, and it is not even believed to be true. The trouble is the very thing the slogan ignores: superposition over all 2^n candidate answers is easy, but a measurement returns just one of them, picked with probability equal to its squared amplitude. To solve a hard search problem you would need interference to wipe out the amplitude of every wrong answer and pile it onto the rare right one — and for a generic NP problem with no exploitable structure, nobody knows how to make that interference happen.
What quantum computers do buy on unstructured search is precisely measured and modest. Grover's algorithm searches an unsorted space of N candidates in about sqrt(N) steps instead of N — a genuine quadratic speed-up, and provably the best any quantum algorithm can do for blind search. Quadratic is real and useful, but it is not the exponential leap NP-completeness would demand: turning 2^n into about 2^(n/2) still leaves you facing an exponential, just with the exponent halved. So even Grover, applied to a 3-SAT instance, does not make NP-complete problems tractable; it shaves the exponent, nothing more.
The famous exponential win, Shor's algorithm for factoring large integers, looks like a counterexample but is the opposite — it is the exception that proves the rule. Factoring is not NP-complete; it is a special problem with deep hidden periodic structure, and Shor's algorithm works precisely by using interference to detect that period (via a quantum Fourier transform). The lesson is sharp: quantum speed-ups come from structure a problem happens to have, not from brute parallel search. This is also why quantum computing threatens specific cryptosystems — RSA and Diffie-Hellman rest on factoring and discrete logs being hard, the very structured problems Shor breaks — while it leaves the security of generic one-way functions and well-chosen symmetric ciphers (only quadratically dented by Grover) largely intact.
What it really shakes: the Church-Turing thesis
If a quantum computer cannot crack NP, what is the deep significance? It is not about what can be computed — a quantum machine computes exactly the same languages a Turing machine does, since (as we saw) a classical machine can simulate it, just slowly. The Church-Turing thesis on what is computable at all stands untouched. The challenge lands on a stronger, quantitative cousin: the extended Church-Turing thesis, which claims every reasonable physical computer can be simulated by a Turing machine with only polynomial slowdown. If Shor's algorithm really does factor exponentially faster than any possible classical method — which we believe but, again, have not proved — then a quantum computer is a physically reasonable device that a classical machine canNOT keep up with polynomially, and the extended thesis is false.
That is the honest headline. Quantum computing's revolutionary claim is not "NP is now easy" but "the efficiency version of the Church-Turing thesis may be wrong — the natural unit of efficient computation might be the quantum circuit, not the classical Turing machine." Everything else flows from that: BQP, not P or BPP, may be the truest class of "feasibly solvable" problems, with classical computers a strict, slower subset on certain structured tasks. It is a profound shift, and notice how disciplined it is — it rests entirely on the model-of-computation thinking you have used since the very first rung: define a machine, bound its resources, and ask honestly which problems fall inside.