Curriculum / Quantum Algorithms / Deutsch-Jozsa Algorithm
Deutsch-Jozsa Algorithm
The first quantum algorithm to provably beat classical.
Deutsch-Jozsa Algorithm
A Problem Designed for Quantum Speedup
Consider a function f that takes an n-bit input and produces a single bit output. You are promised that f is either constant (outputs the same value, all 0s or all 1s, regardless of input) or balanced (outputs 0 for exactly half of all inputs and 1 for the other half). Your task is to determine which.
Classically, in the worst case, you need to evaluate f on inputs to be certain. Even if you see all 0s on the first evaluations, the last input might be the one that returns 1, making it balanced. There's no shortcut: you might have to check more than half the inputs.
Deutsch and Jozsa's quantum algorithm determines the answer in exactly one evaluation. Always. For any n. This was the first proof that quantum computers could solve a well-defined problem exponentially faster than classical computers.
The quantum algorithm evaluates f on a superposition of all 2ⁿ inputs simultaneously, using the oracle circuit once. But the trick isn't parallel evaluation, it's phase kickback. The oracle's effect is encoded into the phases of the superposition in a way that globally distinguishes constant from balanced functions. A final Hadamard layer reads out this global property in one shot.
Phase Kickback: The Core Mechanism
The algorithm works by placing the ancilla qubit in the |−⟩ = (|0⟩ − |1⟩)/√2 state, which is the -1 eigenstate of X. When an oracle CNOT gate fires (applying X to the ancilla), the eigenvalue -1 "kicks back" onto the control qubit instead of changing the target.
Mathematically: if the ancilla is |−⟩ and the oracle computes f(x) via CNOT(x, ancilla), then:
- •If f(x) = 0: ancilla stays |−⟩, control phase unchanged
- •If f(x) = 1: CNOT applies X to |−⟩ = (|0⟩ − |1⟩)/√2, giving -(|0⟩ − |1⟩)/√2 = −|−⟩, and the sign -1 propagates to the control
This is the opening of the lesson. The full walkthrough, the interactive circuit, and the graded challenge continue inside myqubit.
How this lesson works
A hands-on coding challenge. You write Qiskit-compatible Python in the browser editor, run it instantly via WebAssembly, watch the circuit and Bloch sphere react, and pass automatic output checks. The AI tutor Qubitus gives Socratic hints if you get stuck.
Part of: Quantum Algorithms
Learn the algorithms that make quantum computers powerful.
This lesson is part of Pro
Unlock Quantum Algorithms and all 10 tracks with Pro: $12.99/month, $79/year, or $97 lifetime. Start with the free track first if you are new.