Quantum Parallelism

Every algorithm in Part V is some clever variation on a single trick: put n qubits into superposition with H gates, query a function once, and the result somehow encodes information about every possible input at once. This chapter is purely about that trick — quantum parallelism itself — before the next nine chapters show what you can actually do with it.

The setup

Start with n qubits at |0...0⟩, apply H to every one of them. Ch. 1's linear-combination idea, scaled up: the result is an equal superposition of all 2ⁿ possible n-bit strings.

H^⊗n |0...0⟩ = (1/√N) Σₓ |x⟩, N = 2ⁿ

Now query an oracle — a black box implementing some function f — once. Because the oracle acts linearly on a superposition (Ch. 4: every quantum gate is linear), it touches every term in that sum simultaneously. One query; every value of f, all encoded into the resulting amplitudes at once.

The catch — and why it matters

Here's the sentence that separates a real understanding of this topic from a popular-science one: quantum parallelism on its own gives you nothing useful. Measure the state in Fig. 22.2 right now and you get one random x with its one value of f(x) — exactly what a classical random guess would give you. All that rich, simultaneously-computed information is sitting in the amplitudes, but Ch. 7's Born rule only ever lets you read out one outcome, and it destroys the rest.

What actually makes an algorithm work

Every algorithm from Ch. 25 onward is, underneath the specific problem it solves, an exercise in designing the second half of the circuit — what happens after the oracle — so that interference concentrates probability onto one specific, useful measurement outcome instead of leaving it spread uniformly across all 2ⁿ possibilities. Quantum parallelism supplies the raw material (every value of f, computed at once); a second layer of carefully chosen gates is what turns that raw material into an actual speedup. Ch. 26's Deutsch–Jozsa algorithm is the simplest possible example of this two-step pattern, and you already have every piece you need to understand exactly how it works.