Quantum Parallelism and Its Limits
A quantum computer can evaluate a function on a superposition of all inputs at once, but measurement retrieves only one result.
Evaluating everything at once
Prepare n qubits in an equal superposition of all 2^n inputs, then apply a circuit implementing a function f. Linearity carries f across the superposition, producing a state that contains f(x) for every x simultaneously. This is quantum parallelism, and it sounds like a free exponential speedup.
The catch
You cannot read out all those values. A single measurement collapses the superposition and returns just one pair (x, f(x)), chosen at random. Holevo's bound confirms that n qubits yield at most n classical bits. Naive parallelism, by itself, gives no advantage over classical computing — you did the work but cannot harvest it.
Where the real advantage lives
Speedup comes not from parallel evaluation but from interference. A good algorithm arranges the amplitudes so that unwanted answers cancel and the wanted answer's amplitude grows. What is extracted is not every f(x) but a single global property of f — a period, a phase, a marked item — that would be expensive to find classically.
- Parallelism creates the superposition of all f(x)
- Measurement collapses to one random value — no free lunch
- Interference concentrates amplitude on a useful global property
Examples of the pattern
Shor's algorithm does not read all function values; it extracts a period through the quantum Fourier transform. Grover's search does not check all items in parallel and report; it amplitudes the marked item over many controlled steps. Both exploit structure, and both would fail if you tried to just measure the parallel superposition.
The honest summary
Quantum parallelism is necessary scaffolding but not the source of power. The discipline of quantum algorithm design is turning a broad superposition into a narrow, readable answer via interference. Problems lacking exploitable structure gain nothing.