Day: December 9, 2025

Deutsch’s Algorithm in Quantum Computing: The 4 Cases

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).

1. Constant Zero Function: f(x) = 0
x
0
Identity (No Gates)
2. Constant One Function: f(x) = 1
X
3. Balanced ID Function: f(x) = x
+
4. Balanced NOT Function: f(x) = ¬x
+
X

The General Oracle (Uf)

x
y
Uf
x
y ⊕ f(x)

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:
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

Understanding Phase Kickback in Quantum Computing

How the target controls the controller.

In standard classical logic, a Control Bit dictates what happens to a target. However, in quantum mechanics, the relationship is symmetric. When the target qubit is in an eigenstate of the operator, the phase is “kicked back” to the control qubit.

|+⟩
|−⟩
|−⟩
|−⟩
CNOT CIRCUIT

Notice above: The Target qubit remains unchanged (|−⟩), but the Control qubit flips from |+⟩ to |−⟩.

STEP 1: DEFINE INITIAL STATE

|ψ0⟩ = |+⟩ ⊗ |−⟩

= (1/√2) (|0⟩ + |1⟩)  ⊗  (1/√2) (|0⟩ − |1⟩)

STEP 2: EXPAND TERMS

Multiplying coefficients gives 1/2:
|ψ0⟩ = ½ [ |00⟩ − |01⟩ + |10⟩ − |11⟩ ]

STEP 3: APPLY CNOT GATE

Target flips (0↔1) only if Control is 1:
|ψ1⟩ = ½ [ |00⟩ − |01⟩ + |11⟩ − |10⟩ ]

STEP 4: FACTOR & REARRANGE

Group terms by the control qubit:
|ψ1⟩ = ½ [ |0⟩(|0⟩ − |1⟩) − |1⟩(|0⟩ − |1⟩) ]
∴ |ψ1⟩ = |−⟩ ⊗ |−⟩

Why is this important?

The math shows that while we applied the gate to the target, the relative phase of the control qubit changed from positive to negative. This mechanism is the foundation of quantum algorithms like Shor’s and Grover’s.