Deutsch-Jozsa Algorithm

🎯 Why Learn This First?

Deutsch-Jozsa is the simplest quantum algorithm that beats classical computing. It's like the "Hello World" of quantum algorithms.

❓ The Problem We're Solving

You're given a black box function f(x) that takes an n-bit input and returns 0 or 1.

The function is guaranteed to be one of two types:

f(0) = 0, f(1) = 0, f(2) = 0, ... → all 0s
f(0) = 1, f(1) = 1, f(2) = 1, ... → all 1s

f(0) = 0, f(1) = 0, f(2) = 1, f(3) = 1
(exactly 50% zeros, 50% ones)

Your Task: Determine whether f is constant or balanced.

💻 Classical Solution (Why It's Slow)

Without quantum tricks, you have to query the function multiple times:

// For 3-bit input (8 possible values)
results = []
for i in range(5):  # Need to check 5 values minimum
    results.append(f(i))

if all_same(results):
    return "Constant"
else:
    return "Balanced"

Why 5 queries? If you see 4 zeros, the 5th could still be 0 (constant) or 1 (balanced). You need at least half + 1 checks.

⚛️ Quantum Solution (The Elegant Way)

The quantum algorithm queries f exactly once using superposition.

Step-by-Step Circuit

1. Initialize: Start with |0⟩ on n input qubits and |1⟩ on 1 output qubit

   |ψ₀⟩ = |0⟩ⁿ |1⟩

2. Apply Hadamard to all qubits: Create superposition

   |ψ₁⟩ = H⊗ⁿ⁺¹ |ψ₀⟩
        = (1/√2ⁿ) Σₓ |x⟩ · (|0⟩-|1⟩)/√2

   Now you're querying all possible inputs simultaneously

3. Apply the black box function Uᶠ: Evaluate f(x) for all x at once

   |ψ₂⟩ = Uᶠ |ψ₁⟩
        = (1/√2ⁿ) Σₓ (-1)^f(x) |x⟩

   This encodes f(x) as a phase (not a classical value)

4. Apply Hadamard again to input qubits: Extract global pattern

   |ψ₃⟩ = H⊗ⁿ |ψ₂⟩

5. Measure input qubits:
   • If all qubits are |0⟩ → function is constant
   • If any qubit is |1⟩ → function is balanced

🎨 Visual Intuition

Think of it like this:

The quantum computer doesn't look at individual outputs. It detects the global symmetry of the function.

💻 Implement It Yourself (Qiskit)

Here's the complete working code:

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.primitives import Sampler

def deutsch_jozsa(n, oracle):
    """
    n = number of input bits
    oracle = function that adds the black box to the circuit
    """
    # Create circuit
    qr = QuantumRegister(n + 1, 'q')
    cr = ClassicalRegister(n, 'c')
    qc = QuantumCircuit(qr, cr)
    
    # Step 1: Initialize output qubit to |1⟩
    qc.x(qr[n])
    
    # Step 2: Apply Hadamard to all qubits
    for i in range(n + 1):
        qc.h(qr[i])
    
    qc.barrier()
    
    # Step 3: Apply the oracle (black box)
    oracle(qc, qr)
    
    qc.barrier()
    
    # Step 4: Apply Hadamard to input qubits
    for i in range(n):
        qc.h(qr[i])
    
    # Step 5: Measure input qubits
    for i in range(n):
        qc.measure(qr[i], cr[i])
    
    return qc

# Example: Constant function (always returns 0)
def constant_oracle(qc, qr):
    # Do nothing - this means f(x) = 0 for all x
    pass

# Example: Balanced function (returns x₀ XOR x₁)
def balanced_oracle(qc, qr):
    qc.cx(qr[0], qr[2])  # CNOT from first input to output
    qc.cx(qr[1], qr[2])  # CNOT from second input to output

# Run the algorithm
n = 2  # 2 input bits
circuit = deutsch_jozsa(n, balanced_oracle)

# Execute
sampler = Sampler()
job = sampler.run(circuit, shots=1)
result = job.result()
counts = result.quasi_dists[0]

# Interpret result
measured = max(counts, key=counts.get)
if measured == 0:
    print("Function is CONSTANT")
else:
    print("Function is BALANCED")

🎯 When Does This Actually Matter?

Real-World Applications (Rare)

Honestly? Deutsch-Jozsa is mostly a teaching tool. The problem it solves is artificial.

However, the techniques it uses appear in:

• ✅ Simon's Algorithm (finds hidden periodicities)
• ✅ Bernstein-Vazirani (recovers hidden bit strings)
• ✅ Grover's Algorithm (unstructured search)

What You Actually Learn

Bottom line: Master this, and Grover/Shor will make much more sense.

⚠️ Common Mistakes

🛠️ Practice Exercises

def constant_one_oracle(qc, qr):
    # Flip the output qubit
    qc.x(qr[-1])  # Now f(x) = 1 for all x

def copy_first_bit_oracle(qc, qr):
    qc.cx(qr[0], qr[-1])  # CNOT: if x₀=1, flip output

🚀 What's Next?

You've learned:

• ✅ How quantum algorithms use superposition + interference
• ✅ Phase kickback technique
• ✅ Building circuits with oracles

Next up: Grover's Search Algorithm — the most practical quantum algorithm for real-world problems.