Table of Contents
Deutsch-Jozsa
Deutsch-Jozsa algorithm is a quantum algorithm that determines whether a function 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's algorithm to -bit inputs.
The function is promised to be either constant (returns the same value for all 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 queries. The Deutsch-Jozsa algorithm solves this with a single query to the quantum oracle.
Algorithm
The algorithm uses qubits. Initialize the first qubits to and the ancilla to . Apply Hadamard gates to all qubits, then query the oracle, then apply Hadamard gates to the first qubits, then measure the first qubits.
After the second set of Hadamard gates, the amplitude of in the output is . If is constant, all terms have the same sign and this sum is , so the register is definitely . If is balanced, the positive and negative terms cancel exactly to 0, so the register is never measured as .
Phase kickback
Just as in Deutsch's algorithm, the ancilla qubit initialized to causes the oracle to write as a phase on each basis state . The second set of Hadamard gates then performs an interference that concentrates probability on for constant and spreads it away from for balanced .
