deutsch's algorithm

Only one evaluation of the function \(f\) is needed to determine a global property of \(f\)

• You have a gate \(U_f\) that takes \(\ket{x}\ket{y}\) to \(\ket{x}\ket{y\oplus f(x)}\)
• Set the first qubit to \(\ket{0}\). Set the second qubit to \(\ket{1}\)

• the initial state is \(\ket{0}\ket{1}\)
• send both qubits through a hadamard gate (see quantum gates). So the state is \(\left(\frac{\ket{0} + \ket{1}}{\sqrt{2}}\right)\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right)\)
• send the qubits through \(U_f\) and what happens? Consider what happens when we send \(\ket{x}\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right)\) through \(U_f\), where \(x\) is 0 or 1?
  • The result is \((-1)^{f(x)}\ket{x}\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right)\). Why? Because if \(f(x)=0\), then \(y\oplus f(x) = y\), so nothing happens to the second qubit. If \(f(x)=1\) then the second qubit becomes \(\left(\frac{\ket{0\oplus 1} - \ket{1\oplus 1}}{\sqrt{2}}\right) = \left(\frac{\ket{1} - \ket{0}}{\sqrt{2}}\right)\)
• So, the possible outcomes are

\[\begin{cases} \pm\left(\frac{\ket{0} + \ket{1}}{\sqrt{2}}\right)\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right) & \text{if } f(0)=f(1)\\ \pm\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right)\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right) & \text{if } f(0)\neq f(1)\\ \end{cases}\] In the first row, the \(pm\) represents the fact that \(f(0)=f(1)\) could either be a 0 or a 1. But, no matter what \(f(0)\) and \(f(1)\) are, if they are the same, the sign of the whole state will be the same. In the second row, the first qubit is in state \(\ket{0} - \ket{1}\). This is because the sign of the whole state will depend on what \(f(x)\) is.

Then, we apply a Hadamard gate to the first qubit to obtain \[\begin{cases} \pm\ket{0}\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right) & \text{if } f(0)=f(1)\\ \pm\ket{1}\left(\frac{\ket{0} - \ket{1}}{\sqrt{2}}\right) & \text{if } f(0)\neq f(1)\\ \end{cases}\]

Then, by measuring the first qubit, we can tell whether or not \(f(0)=f(1)\)