Quantum Parallelism

Quantum Computation and Quantum Information, Machael A. Nielsen, Isaac L. Chuang

Quantum Parallelism is foundational technique that gives quantum computers their potential speed advantage. It explains how a quantum computer can evaluate a function f(x) for many different input values x simultaneously, a feat impossible for a classical computer.

The oracle Uf​ maps the basis states as follows: $Uf​:∣x⟩∣y⟩⟶∣x⟩∣y⊕f(x)⟩$. Here, x is the n-bit input, y is the single-bit target, and ⊕ is addition modulo 2 (the XOR operation).

How it works:

1. Put the input qubits in superposition: every possible x equally likely.
2. Apply the oracle U_f.
3. Result: a massive superposition containing f(x) for every x simultaneously.

$|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_x |x\rangle |f(x)\rangle$

This looks like exponential parallelism — 2ⁿ evaluations in one step.

The catch:

Measuring collapses the state — you get only one random (x, f(x)) pair. To extract all values, you’d need ~2ⁿ measurements: no speedup.

Quantum parallelism alone gives no advantage.

The real power:

Quantum algorithms (e.g., Deutsch-Jozsa, Shor’s) don’t measure directly. They apply additional gates to create interference, amplifying probabilities for global properties of f (constant? balanced? periodic?).

This interference lets us extract useful information exponentially faster than classical methods – that’s where quantum speedups come from.

Bottom line: Parallelism computes everything; interference lets us cleverly read out what matters.