Deutsch's algorithm

Setup

Given an $n$-bit Unitary Operator $f:{\mathbb{F}}_{2^n}\to {\mathbb{F}}_{2^n}$, can we know whether this function is constant with a single evaluation?

Solution

We can solve the above in 3 steps, represented by the circuit below

Proof of correctness

• We have $|{\psi }_0⟩=|00⟩$.

• After applying $X$ to the 2nd Qubit we get $|01⟩$

• Applying the Hadamard gate $H$ to both matrices, we get the superposition $|00⟩-|01⟩+|10⟩-|11⟩$, up to normalisation.

• Applying $U_f$ we get $|0(0\oplus f(0))⟩-|0(1\oplus f(0))⟩+|1(0\oplus f(1))⟩-|1(1\oplus f(1))⟩$.

• After applying the Hadamard gates on each bit individually, we get the Quantum state $|{\psi }_1⟩={\sum }_{i=0}^{2^{n+1}-1}|i_2⟩$, up to normalisation, where $i_2$ is the binary representation of $i$, i.e. $5_2=101$.

• $|{\psi }_2⟩=U_f|{\psi }_1⟩={\sum }_{i=0}^{2^{n+1}-1}|i_2⟩$

• Complete the proof above.

More generically, there is always a way of building an Operator such that $U_f|x⟩=(-1{)}^{f(x)}|x⟩$.