Deutsch’s Algorithm: Complete Guide
From Initialization to Measurement.
Deutsch’s Algorithm determines if a function f(x) is Constant or Balanced using only a single query. First, we examine how these functions are physically built.
The 4 Possible Functions
In these examples, we set the bottom input to 0 so the output is exactly f(x).
The General Oracle (Uf)
The Complete Circuit
To detect the function type, we initialize the bottom wire to |1⟩ and use Hadamard gates to create superposition.
|0⟩
|1⟩
H
H
Uf
KICKBACK ↑
H
|ψ₀⟩
|ψ₁⟩
|ψ₂⟩
Mathematical Proof
1. Initialization: |ψ₀⟩ = |0⟩|1⟩
2. Superposition: |ψ₁⟩ = |+⟩|-⟩ = ½(|0⟩+|1⟩)(|0⟩-|1⟩)
3. The Kickback Effect: Applying Uf to |x⟩|-⟩ results in:
This means the output of the function is shifted into the phase of the first qubit.
4. Global State |ψ₂⟩:
|ψ₂⟩ = 1/√2 [ (-1)f(0)|0⟩ + (-1)f(1)|1⟩ ] ⊗ |-⟩
2. Superposition: |ψ₁⟩ = |+⟩|-⟩ = ½(|0⟩+|1⟩)(|0⟩-|1⟩)
3. The Kickback Effect: Applying Uf to |x⟩|-⟩ results in:
Uf |x⟩|-⟩ = (-1)f(x) |x⟩|-⟩
This means the output of the function is shifted into the phase of the first qubit.
4. Global State |ψ₂⟩:
|ψ₂⟩ = 1/√2 [ (-1)f(0)|0⟩ + (-1)f(1)|1⟩ ] ⊗ |-⟩
Final Measurement
If f(0) = f(1) (Constant) → State is ±|+⟩ → Measure 0
If f(0) ≠ f(1) (Balanced) → State is ±|-⟩ → Measure 1
Techucation 