Deutsch-Jozsa Algorithm

The Deutsch-Jozsa Algorithm, proposed by David Deutsch and Richard Jozsa in 1992, generalizes the Deutsch algorithm to a function with an $n$-bit input. It provides a striking example of an exponential separation in query complexity between classical deterministic algorithms and quantum algorithms.

Imagine a black-box function that takes a string of $n$ bits (like a password of length $n$) and outputs either 0 or 1. You are promised that the function is either *constant* (outputs the same value for all $2^n$ inputs) or *balanced* (outputs 0 for exactly half of the inputs, and 1 for the other half). Classically, to be absolutely certain which type it is, you might have to check more than half of all possible inputs, which is $2^{n-1} + 1$ queries. For $n=30$, this is over 500 million queries! The Deutsch-Jozsa algorithm prepares a uniform superposition of all $2^n$ inputs, queries the oracle exactly once, and uses multi-qubit interference to determine with 100% certainty whether the function is constant or balanced.

Let $f: \{0,1\}^n \to \{0,1\}$ be a function that is guaranteed to be either constant or balanced.

Classical Complexity: In the worst case, a deterministic classical algorithm must query the oracle $2^{n-1} + 1$ times to distinguish between a constant and balanced function. Even with a probabilistic classical algorithm, achieving absolute certainty requires exponential queries.

Quantum Complexity: The Deutsch-Jozsa algorithm requires exactly 1 query.

Circuit Construction: 1. Initialize: Prepare $n$ control qubits in state $|0\rangle^{\otimes n}$ and 1 target qubit in state $|1\rangle$. 2. Superposition: Apply $H^{\otimes n}$ to the control register and $H$ to the target register: $$|\psi_1\rangle = \left( H^{\otimes n} |0\rangle^{\otimes n} \right) \left( H |1\rangle \right) = \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle \right) |-\rangle$$ 3. Oracle Query: Apply the unitary oracle $U_f |x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$. By phase kickback: $$|\psi_2\rangle = \left( \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{f(x)} |x\rangle \right) |-\rangle$$ 4. Interference: Apply $H^{\otimes n}$ to the control register. Recall that the action of $H^{\otimes n}$ on a basis state $|x\rangle$ is: $$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$$ where $x \cdot y = \sum_{i=1}^n x_i y_i \pmod 2$ is the bitwise dot product. Applying this to the control register of $|\psi_2\rangle$ yields: $$|\psi_3\rangle = \frac{1}{2^n} \sum_{y \in \{0,1\}^n} \left( \sum_{x \in \{0,1\}^n} (-1)^{f(x) + x \cdot y} \right) |y\rangle$$ 5. Measurement: Measure the control register. Let us calculate the amplitude of the all-zero state $|0\rangle^{\otimes n}$ (where $y = 00\dots0$): $$\text{Amplitude of } |0\rangle^{\otimes n} = \frac{1}{2^n} \sum_{x \in \{0,1\}^n} (-1)^{f(x)}$$

• If $f$ is constant, then $(-1)^{f(x)}$ is either always $+1$ or always $-1$. The sum is $\pm 2^n$, so the amplitude is $\pm 1$. The probability of measuring $|0\rangle^{\otimes n}$ is $1$.
• If $f$ is balanced, then $(-1)^{f(x)}$ is $+1$ for half the inputs and $-1$ for the other half. The sum is $0$, so the amplitude is $0$. The probability of measuring $|0\rangle^{\otimes n}$ is $0$.

Thus, if we measure $|0\rangle^{\otimes n}$, the function is constant. If we measure any other state, the function is balanced.