Deutsch Algorithm

The Deutsch Algorithm, proposed by David Deutsch in 1985, was the first quantum algorithm to prove that a quantum computer could solve a specific problem using fewer queries than any possible classical algorithm. It addresses a simple, abstract question about a one-bit function: is the function constant (returns the same output for all inputs) or balanced (returns 0 for half the inputs and 1 for the other half)?

Imagine you have a coin that might be normal (one heads, one tails) or trick (both sides heads, or both sides tails). A normal coin is 'balanced'; a trick coin is 'constant'. Classically, to determine which type of coin you have, you must look at both sides, requiring 2 looks. The Deutsch algorithm allows you to look at a quantum superposition of both sides simultaneously. By using a target qubit in a state of destructive interference, the output of the coin flip is 'kicked back' as a phase shift onto your query qubit. A final measurement reveals whether the phases interfered constructively (constant) or destructively (balanced) in just 1 look.

Let $f: \{0,1\} \to \{0,1\}$ be a black-box function. There are four possible such functions: 1. $f(0) = 0, f(1) = 0$ (Constant) 2. $f(0) = 1, f(1) = 1$ (Constant) 3. $f(0) = 0, f(1) = 1$ (Balanced) 4. $f(0) = 1, f(1) = 0$ (Balanced)

Classically, determining whether $f$ is constant or balanced requires evaluating both $f(0)$ and $f(1)$, which takes 2 queries. The Deutsch algorithm solves this in 1 quantum query using the following circuit:

1. State Preparation: Initialize two qubits in the state $|\psi_0\rangle = |0\rangle|1\rangle$. 2. Superposition: Apply a Hadamard gate to both qubits: $$|\psi_1\rangle = (H \otimes H)|0\rangle|1\rangle = |+\rangle|-\rangle = \frac{1}{2}(|0\rangle + |1\rangle)(|0\rangle - |1\rangle)$$ 3. Oracle Query: Apply the unitary oracle $U_f |x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$. Let's analyze the action of $U_f$ on a state $|x\rangle|-\rangle$: $$U_f |x\rangle|-\rangle = U_f |x\rangle \left( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \right) = \frac{|x\rangle|0 \oplus f(x)\rangle - |x\rangle|1 \oplus f(x)\rangle}{\sqrt{2}}$$ If $f(x) = 0$, this is $\frac{|x\rangle|0\rangle - |x\rangle|1\rangle}{\sqrt{2}} = |x\rangle|-\rangle$. If $f(x) = 1$, this is $\frac{|x\rangle|1\rangle - |x\rangle|0\rangle}{\sqrt{2}} = -|x\rangle|-\rangle$. Thus, we can write this compactly as: $$U_f |x\rangle|-\rangle = (-1)^{f(x)} |x\rangle|-\rangle$$ This is the phase kickback mechanism: the state of the target qubit $|-\rangle$ is unchanged, but the function value $f(x)$ is kicked back as a phase factor $(-1)^{f(x)}$ onto the control qubit. Applying $U_f$ to our full state $|\psi_1\rangle$ yields: $$|\psi_2\rangle = \frac{1}{2} \left( (-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle \right) |-\rangle$$ 4. Interference: Apply a Hadamard gate to the first qubit: If $f$ is constant ($f(0) = f(1)$): $$|\psi_3\rangle = \pm \frac{1}{2}(|0\rangle + |1\rangle) \xrightarrow{H} \pm |0\rangle$$ If $f$ is balanced ($f(0) \neq f(1)$): $$|\psi_3\rangle = \pm \frac{1}{2}(|0\rangle - |1\rangle) \xrightarrow{H} \pm |1\rangle$$ 5. Measurement: Measuring the first qubit yields $|0\rangle$ with probability 1 if $f$ is constant, and $|1\rangle$ with probability 1 if $f$ is balanced.