Deutsch-Jozsa Algorithm

What You'll Learn: How quantum parallelism and interference combine to solve a problem with one query that classically requires up to 2^(n-1)+1 queries — the first exponential quantum speedup.

Level: Beginner | Time: 20 minutes | Qubits: 3 | Framework: Qiskit

Prerequisites: Bell State

The Idea

Imagine you have a mysterious black box (an "oracle") that takes an n-bit input and outputs a single bit: 0 or 1. You're promised that the function is either:

• Constant: Outputs the same value (0 or 1) for every possible input
• Balanced: Outputs 0 for exactly half the inputs and 1 for the other half

Your job: figure out which type it is.

Classically, you'd need to check at least half the inputs plus one to be certain. For n = 100 bits, that's over 2^99 ≈ 10^29 queries. The Deutsch-Jozsa algorithm does it in one single query.

How? By evaluating the function on a superposition of all inputs simultaneously, then using interference to amplify the signal that tells constant from balanced.

How It Works

The Circuit

CODECopy
     ┌───┐     ┌──────────┐     ┌───┐
q_0: ┤ H ├─────┤          ├─────┤ H ├─── M
     ├───┤     │          │     ├───┤
q_1: ┤ H ├─────┤  Oracle  ├─────┤ H ├─── M
     ├───┤┌───┐│          │     └───┘
q_2: ┤ X ├┤ H ├┤          ├──────────
     └───┘└───┘└──────────┘

Step 1: Initialize

PYTHONCopy
qc.x(2)      # Ancilla qubit: |0⟩ → |1⟩
qc.h(2)      # Ancilla: |1⟩ → |−⟩ = (|0⟩ − |1⟩)/√2
qc.h(0)      # Input qubit 0: superposition
qc.h(1)      # Input qubit 1: superposition

The ancilla is prepared in the |−⟩ state to enable phase kickback: when the oracle flips the ancilla, the −1 sign kicks back onto the input register as a phase.

Step 2: Apply the Oracle

The oracle maps |x⟩|−⟩ → (−1)^f(x) |x⟩|−⟩. The ancilla doesn't change — instead, each input basis state |x⟩ acquires a phase of (−1)^f(x).

• Constant f: All states get the same phase → no relative phase change
• Balanced f: Half get +1, half get −1 → relative phase differences

Step 3: Interfere and Measure

PYTHONCopy
qc.h(0)      # Final Hadamard on input qubits
qc.h(1)
qc.measure([0, 1], [0, 1])

The final Hadamard causes interference:

• Constant: All phases agree → constructive interference on |00⟩
• Balanced: Phases cancel on |00⟩ → destructive interference

Decision rule: Measure all zeros → CONSTANT. Anything else → BALANCED.

The Math

State Evolution (2-input case)

1. After initialization: |ψ₁⟩ = |+⟩|+⟩|−⟩ = ½(|00⟩ + |01⟩ + |10⟩ + |11⟩)|−⟩

2. After oracle (phase kickback): |ψ₂⟩ = ½((−1)^f(00)|00⟩ + (−1)^f(01)|01⟩ + (−1)^f(10)|10⟩ + (−1)^f(11)|11⟩)|−⟩

3. After final Hadamard on inputs: The amplitude of |00⟩ is: (1/2^n) Σ_x (−1)^f(x)

   • Constant f: Sum = ±2^n → amplitude = ±1 → P(|00⟩) = 1
   • Balanced f: Sum = 0 → amplitude = 0 → P(|00⟩) = 0

Why One Query Suffices

The quantum trick is evaluating f on all 2^n inputs simultaneously (quantum parallelism) and then using interference to extract a global property of f (constant vs. balanced) rather than individual output values. You can't learn what f(x) is for any specific x — but you learn whether f is constant or balanced, which is the only question we're asking.

Expected Output

The algorithm is deterministic on a perfect simulator — no statistical uncertainty. One shot is enough.

Running the Circuit

PYTHONCopy
from circuit import run_circuit, classify, verify_deutsch_jozsa

# Test a balanced oracle
counts = run_circuit(oracle_type="balanced")
print(classify(counts))  # "BALANCED"

# Test a constant oracle
counts = run_circuit(oracle_type="constant_0")
print(classify(counts))  # "CONSTANT"

# Verify all oracle types
result = verify_deutsch_jozsa()
for check in result["checks"]:
    print(f"  {check['name']}: {check['detail']}")

Oracle Types

Try It Yourself

1. One query: Run with shots=1 and oracle_type="balanced". Do you get the right answer? (Yes — this algorithm is deterministic.)

2. Custom balanced oracle: Modify the circuit to implement f(x) = x₀ (instead of x₀ ⊕ x₁). Is it still classified correctly?

3. Scale up: Add a third input qubit. How does the circuit change? (Hint: just add another H, another CNOT to the oracle, and another H.)

4. Classical comparison: Write a classical function that determines constant vs. balanced. How many evaluations does it need in the worst case?

What's Next

• Bernstein-Vazirani — Find a hidden string with one query (extends the Deutsch-Jozsa idea)
• Grover's Search — Quadratic speedup for unstructured search
• Quantum Fourier Transform — The workhorse behind Shor's algorithm

Applications

References

• Deutsch, D. & Jozsa, R. (1992). "Rapid Solution of Problems by Quantum Computation." Proceedings of the Royal Society A 439(1907), 553-558. DOI: 10.1098/rspa.1992.0167
• Cleve, R. et al. (1998). "Quantum algorithms revisited." Proceedings of the Royal Society A 454(1969), 339-354.
• Nielsen, M.A. & Chuang, I.L. Quantum Computation and Quantum Information, Section 1.4.4.