Deutsch’s Algorithm
This algorithm is used to find the parity of a pair of bits.1 It’s quantum circuit is:
# Derivation
We can ignore the answer Qubit, $\ket{-}$ as it doesn’t change. We first apply the Hadamard Gate to the input qubit: $$\ket{0} \overset{H}{\longrightarrow} \frac{1}{\sqrt 2}(\ket{0} + \ket{1}.$$ Next, we query the Oracle, which acts as a Phase Oracle because the answer qubit is $\ket{-}$. This gives us $$\frac{1}{\sqrt 2}[(-1)^{f(0)}\ket{0} + (-1)^{f(1)}\ket{1}].$$
Substituting the values of the oracle, we get $$\frac{1}{\sqrt 2}[(-1)^{b_0}\ket{0} + (-1)^{b_1}\ket{1}].$$
Then, we factor out $(-1)^{b_0}$. $$(-1)^{b_0}\frac{1}{\sqrt 2}\left[\ket{0} + (-1)^{b_1 - b_0}\ket{1}\right].$$
Now, depending on whether $b_0$ and $b_1$ are equal, this is $$\begin{cases}
(-1)^{b_0}\frac{1}{\sqrt 2} (\ket{0} + \ket{1}), & b_0 = b_1 \
(-1)^{b_0}\frac{1}{\sqrt 2} (\ket{0} - \ket{1}), & b_0 \neq b_1
\end{cases}.$$
$$\begin{cases}
(-1)^{b_0}(\ket{+}), & b_0 = b_1 \
(-1)^{b_0}(\ket{-}), & b_0 \neq b_1
\end{cases}.$$ We can measure these in the $X$-basis or we can apply a Hadamard Gate again and then measure in the $Z$-basis. By applying Hadamard Gate, we get $$\begin{cases}
(-1)^{b_0}(\ket{0}), & b_0 = b_1 \
(-1)^{b_0}(\ket{1}), & b_0 \neq b_1
\end{cases}.$$
If we measure this, we either get $|0⟩$ or $|1⟩$, since the overall phase of $(−1)^{b_0}$ does not matter. If we get $|0⟩$, we know that $b_0 = b_1$, and so the parity of the bits is $0$ (even). On the other hand, if we get $|1⟩$, we know that $b_0 \neq b_1$, and so the parity of the bits is $1$ (odd).
The quantum query complexity of this algorithm is $1$.