Deutsch’s Algorithm

  1. Problem Statement

  2. Quantum Solution

1. Problem Statement

Deutsch’s algorithm is used to solve the parity problem: Parity \(= f(0) \oplus f(1)\). Here, \(\oplus\) denotes the XOR operator. For example:

  • \(f(0) = f(1)\), Parity \(= 0\) (even parity, constant function)

  • \(f(0) \neq f(1)\), Parity \(= 1\) (odd parity, balanced function)

2. Quantum Solution

0bb280e7e90642489032f4f1133ebcfb

The circuit starts with:

\[\ket{\psi_0} = \ket{01}\]

After the Hadamard gate is applied, it transforms \(\ket{0} \to \ket{+}\) and \(\ket{1} \to \ket{-}\). Therefore, \(\ket{\psi_0} = \ket{+-}\). To simplify, rewrite the plus state and distribute the negative state:

\[\ket{\psi_1}=\frac{1}{\sqrt{2}}(\ket{0} \ket{-} + \ket{1}\ket{-})\]

Now, query the oracle \(U_f\).

\[\begin{split}\ket{\psi_1}=\frac{1}{\sqrt{2}}U_f(\ket{0} \ket{-} + \ket{1}\ket{-}) \\ \ket{\psi_1}=\frac{1}{\sqrt{2}}(U_f\ket{0} \ket{-} + U_f\ket{1}\ket{-})\end{split}\]

As per definition of phase oracles: \(U_f\ket{x}\ket{-} = (-1)^{f(x)}=\ket{x}\ket{-}\), plug it into the equation:

\[\ket{\psi_2}=\frac{1}{\sqrt{2}}((-1)^{f(0)}\ket{0}) + (-1)^{f(1)}\ket{1}))\]

Back to the parity equation:

\[f(0) = f(1): \pm\frac{1}{\sqrt{2}}(\ket{0}+\ket{1}) = \pm \ket{+}\]
\[f(0) \neq f(1): \pm\frac{1}{\sqrt{2}}(\ket{0}-\ket{1}) = \pm \ket{-}\]

Applying last Hadamard gate flips the plus state to zero, and minus state to one:

\[f(0) = f(1): \pm \ket{0}\]
\[f(0) \neq f(1): \pm \ket{1}\]

Finally, we measure the first qubit. This matches the parity problem, where:

  • If we measure 0, then the function is constant: \(f(0) = f(1)\)

  • If we measure 1, then the function is constant: \(f(0) \neq f(1)\)