Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 15C (Quantum Information and Computation)

Starting from the $n$-qubit computational basis state $|0{⟩}^{\otimes n}$, apply one Hadamard gate to every qubit. Since $H|0⟩=(|0⟩+|1⟩)/\sqrt{2}$,Thus parallel Hadamard gates prepare the uniform quantum superposition.

The Hadamard gate conjugates the Pauli X gate into the Pauli Z gate:When the control qubit is $|0⟩$, all three circuits act as the identity on the target. When it is $|1⟩$, the right-hand circuit acts on the target as $HXH=Z$. It therefore agrees with the Controlled-Z gate on every computational basis state, provingConjugating both sides by $I\otimes H$ and using $H^2=I$ immediately gives the reverse identity

The three controlled-NOT gates have directions $1\to 2$, $2\to 1$, and $1\to 2$. On computational basis bits they act asBy linearity, the whole quantum circuit is the SWAP gate. Thereforeso $|\alpha ⟩=|\varphi ⟩$ and $|\beta ⟩=|\psi ⟩$.

After the first Hadamard gate, the joint state isThe controlled SWAP gate then givesAfter the second Hadamard gate, it is

The Born rule says that each probability is the squared norm of the corresponding ancilla component. Since the states are normalized,Consequently

This circuit is the swap test. If the two pure states are identical up to a physically irrelevant global phase, then $|⟨\psi |\varphi ⟩|=1$ and outcome one never occurs. If they are distinct, then $|⟨\psi |\varphi ⟩|<1$ and each run produces outcome one with positive probability $p_1$.

Run the circuit independently on fresh copies. Observing even one outcome one proves that the states differ. If no one occurs in $N$ runs, that event has probabilitywhen the states differ, which tends to zero as $N\to \infty$. Repetition therefore distinguishes equality from inequality with arbitrarily high probability.