Quantum Parallelism

A classical computer that wants to know $f(0)$ and $f(1)$ for some function $f$ must call $f$ twice. Quantum mechanics offers a striking shortcut: by preparing the input in a superposition of every possible value and calling $f$ only once, both results are encoded in the output state simultaneously. This is the phenomenon called quantum parallelism.

How it works

Set up two registers. The input register is a single qubit starting in $|0\rangle$ ; the output register is also a single qubit starting in $|0\rangle$ . Apply a Hadamard to the input:

H|0\rangle = \frac{1}{\sqrt{2}}\big(|0\rangle + |1\rangle\big).

The combined state of both registers is now

\frac{1}{\sqrt{2}}\big(|0\rangle + |1\rangle\big) \otimes |0\rangle = \frac{1}{\sqrt{2}}\big(|00\rangle + |10\rangle\big),

where the first index labels the input and the second labels the output (qubit 0 is the most significant bit in this platform's convention).

A query oracle $U_f$ acts on the combined state according to

U_f\,|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle,

where $\oplus$ is addition modulo 2. With $y = 0$ this simplifies to $U_f|x\rangle|0\rangle = |x\rangle|f(x)\rangle$ , so the output register simply stores $f(x)$ .

Applying $U_f$ to the superposed state gives

U_f\,\frac{1}{\sqrt{2}}\big(|00\rangle + |10\rangle\big) = \frac{1}{\sqrt{2}}\big(|0\rangle|f(0)\rangle + |1\rangle|f(1)\rangle\big).

Both values $f(0)$ and $f(1)$ appear in the state at the same time — the oracle was called only once.

The f(x) = x oracle as a CNOT

For the function $f(x) = x$ the oracle maps $|x\rangle|0\rangle \to |x\rangle|x\rangle$ . That is exactly the action of a CNOT gate with qubit 0 as control and qubit 1 as target:

\text{CNOT}: |00\rangle \to |00\rangle, \quad |10\rangle \to |11\rangle.

After $H$ on qubit 0 followed by CNOT, the state is

\frac{1}{\sqrt{2}}\big(|00\rangle + |11\rangle\big),

a maximally entangled Bell state. The oracle has evaluated $f$ on both inputs in one step.

Try it

Build the circuit that places the input register in superposition and then evaluates $f(x) = x$ via a CNOT oracle. The grader checks the full state vector.

Run your code to see the quantum state.

After running, inspect the amplitudes: you should see $\tfrac{1}{\sqrt{2}} \approx 0.707$ on $|00\rangle$ and $|11\rangle$ , and zero everywhere else.