Deutsch-Jozsa Algorithm

Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm (1992) is one of the first problems where a quantum computer provably outperforms any deterministic classical algorithm. It answers a simple yes-or-no question: is a given Boolean function constant (same output for all inputs) or balanced (outputs 0 for exactly half the inputs and 1 for the other half)?

Classically, you need up to queries in the worst case to be certain. The quantum algorithm decides it in exactly one query — an exponential separation that, while not practically useful on its own, was a pivotal early proof that quantum interference could be harnessed for computation.

How it works

The algorithm exploits the fact that a Hadamard transform, followed by an oracle query, followed by another Hadamard transform, creates constructive or destructive interference depending on the oracle's structure:

1. Initialize input qubits in and one output qubit in .
2. Apply Hadamard gates to all qubits, creating an equal superposition.
3. Query the oracle — it encodes the Boolean function as a phase kickback.
4. Apply Hadamard again to the input qubits.
5. Measure — if all input qubits read , the function is constant; any other result means it is balanced.

The key insight is that balanced functions introduce phase differences that the final Hadamard exposes, while constant functions leave the superposition unchanged.

What the example does

The implementation constructs both types of oracles:

• Balanced oracle — generates a random non-zero bit string and uses it to decide which qubits get X gates before and after a cascade of CNOTs. This ensures exactly half the inputs flip the output.
• Constant oracle — randomly outputs 0 or 1 for all inputs (either does nothing or flips the output qubit).

The example runs a 4-qubit balanced oracle and verifies that the all-zeros measurement outcome never appears — confirming the function is correctly identified as balanced.

Getting started

python -m venv .venv && source .venv/bin/activate
pip install -r requirements.lock
python deutsch_jozsa.py

The example runs the algorithm against both oracle types. For each oracle, the output reports the most likely measurement outcome, classifies the oracle as constant or balanced (based on whether all-zeros dominates), and confirms the classification is correct. A sanity-check assertion enforces that a balanced oracle never produces the all-zeros outcome.

Dependencies

• Python 3.12
• Qiskit (< 2.0)
• Qiskit Aer
• NumPy

References

• Deutsch, D. & Jozsa, R. (1992). Rapid Solution of Problems by Quantum Computation. doi:10.1098/rspa.1992.0167

License

Apache 2.0 — see LICENSE.