Quantum parallelism, honestly

Here is the trick every headline leans on: load a superposition of every possible input, run your function once, and the machine works on all inputs at the same time. That part is true, and we are going to build the exact state that does it. Then we are going to hit the wall that the headlines never mention - and see why the wall, not the trick, is the whole reason quantum algorithms are hard to design.

Play with the trap first

The widget below has two input qubits holding a number $x\in \{0,1,2,3\}$ and one output qubit holding $y$. Pick a function $f$, then walk the four stages: load the registers, superpose the input, fire a single query of the oracle, and measure. Watch the third stage carefully - one query really does write $f(x)$ next to all four values of $x$ at once. Then press Measure, and press it again.

Every measurement hands you a single pair $(x,f(x))$, chosen at random, and vaporizes the other three. Run it four times and, on average, you have paid four queries to see all four pairs - exactly what a classical computer does by calling $f$ four times. The superposition was real. The payoff was not.

The state one query actually builds

A quantum gate has to be reversible, so a function is fed in through an oracle $U_f$ that keeps a copy of the input around. It acts on an input register $x$ and an output register $y$ like this:

where $\oplus$ is XOR. Start the output at $|0⟩$ and the map simplifies to $U_f|x⟩|0⟩=|x⟩|f(x)⟩$ - it writes the answer into the second register. Nothing surprising yet; that is just a reversible way to evaluate $f$.

The move is what you feed it. Instead of one value of $x$, put the input register into an equal superposition of all $N=2^n$ inputs first (that is what a Hadamard on each input wire does), and then apply the single query^[2]:

This state is what people mean by quantum parallelism. It genuinely contains all $N$ input-output pairs, with equal weight $1/\sqrt{N}$. One query, every answer, present at the same time. Everything up to here is true and is what the demo showed at stage three.

The measurement wall

Now recall the Born rule from the measurement lesson: a measurement returns one basis state, with probability equal to that state's amplitude squared, and destroys the rest. Every pair here carries the same probability:

So a measurement of the parallelism state gives you one uniformly random $x$ together with its $f(x)$, and nothing else. That is identical to picking a random input and evaluating $f$ once on a classical machine. The exponential pile of evaluations sat right there in the amplitudes, and the readout let you keep exactly one of them. Storing an answer where you cannot read it is not the same as computing it.^[1]

This reframes the whole job of quantum algorithm design. You do not get credit for the superposition; every algorithm has that for free after a layer of Hadamards. You get credit for engineering the interference that follows, and only a few problems are known to have the right structure for it. The very next lesson builds the first one from scratch.

from qiskit import QuantumCircuit

# 2 input qubits (x) + 1 output qubit (y)
qc = QuantumCircuit(3)

qc.h(0)          # superpose the input register:
qc.h(1)          # x is now an equal mix of 0, 1, 2, 3

apply_oracle(qc) # one query of U_f writes f(x) onto qubit 2 for every x at once

qc.measure_all() # but this returns ONE random (x, f(x)) pair - the wall

Check yourself

Next: the first real speedup - Deutsch-Jozsa and phase kickback, where one query settles a yes/no question about $f$ that classically needs exponentially many.