Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Deutsch-Jozsa
**Deutsch-Jozsa algorithm** is a quantum algorithm that determines whether a function $f:\{0,1\}^n \to \{0,1\}$ is constant or balanced using exactly one quantum query. It was proposed by David Deutsch and Richard Jozsa in 1992 as a generalization of [[deutsch|Deutsch's algorithm]] to $n$-bit inputs.

The function $f$ is promised to be either **constant** (returns the same value for all $2^n$ inputs) or **balanced** (returns 0 for exactly half the inputs and 1 for the other half). Classically, distinguishing these two cases in the worst case requires $2^{n-1} + 1$ queries. The Deutsch-Jozsa algorithm solves this with a single query to the quantum oracle.

## Algorithm
The algorithm uses $n + 1$ qubits. Initialize the first $n$ qubits to $\lvert 0\rangle^{\otimes n}$ and the ancilla to $\lvert 1\rangle$. Apply Hadamard gates to all $n+1$ qubits, then query the oracle, then apply Hadamard gates to the first $n$ qubits, then measure the first $n$ qubits.

$$\lvert 0\rangle^{\otimes n}\lvert 1\rangle \xrightarrow{H^{\otimes n+1}} \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\lvert x\rangle \otimes \lvert -\rangle \xrightarrow{U_f} \frac{1}{\sqrt{2^n}}\sum_{x}(-1)^{f(x)}\lvert x\rangle \otimes \lvert -\rangle \xrightarrow{H^{\otimes n}}$$

After the second set of Hadamard gates, the amplitude of $\lvert 0\rangle^{\otimes n}$ in the output is $\frac{1}{2^n}\sum_x (-1)^{f(x)}$. If $f$ is constant, all terms have the same sign and this sum is $\pm 1$, so the register is definitely $\lvert 0\rangle^{\otimes n}$. If $f$ is balanced, the positive and negative terms cancel exactly to 0, so the register is never measured as $\lvert 0\rangle^{\otimes n}$.

## Phase kickback
Just as in [[deutsch|Deutsch's algorithm]], the ancilla qubit initialized to $\lvert -\rangle$ causes the oracle to write $(-1)^{f(x)}$ as a phase on each basis state $\lvert x\rangle$. The second set of Hadamard gates then performs an interference that concentrates probability on $\lvert 0\rangle^{\otimes n}$ for constant $f$ and spreads it away from $\lvert 0\rangle^{\otimes n}$ for balanced $f$.