Quantum Computing: Inversion About the Mean

Quantum Computing: Grover’s Algorithm

Inversion About the Mean via HZH Interference

Introduction

Grover’s algorithm provides a quadratic speedup for searching unstructured data. The core mechanism is the HZH (Hadamard-Phase-Hadamard) operation, which performs “Inversion about the Mean” by using constructive and destructive interference.

1. Initial State: Uniform Superposition

|ψ> = 1/√8 [ |000> + |001> + |010> + |011> + |100> + |101> + |110> + |111> ]

2. Round 1, Step 1.1: The Oracle Flip

The Oracle flips the sign of the target state |101>:

|ψoracle> = 1/√8 [ |000> + |001> + |010> + |011> + |100> - |101> + |110> + |111> ]

3. Round 1, Step 1.2: HZH Diffusion Expansion

Horizontal scroll to see the full interference map:

(1/8) [ +|000> +|001> +|010> +|011> +|100> +|101> +|110> +|111> ] ← H|000> (1/8) [ +|000> -|001> +|010> -|011> +|100> -|101> +|110> -|111> ] ← H|001> (1/8) [ +|000> +|001> -|010> -|011> +|100> +|101> -|110> -|111> ] ← H|010> (1/8) [ +|000> -|001> -|010> +|011> +|100> -|101> -|110> +|111> ] ← H|011> (1/8) [ +|000> +|001> +|010> +|011> -|100> -|101> -|110> -|111> ] ← H|100> -(1/8) [ +|000> -|001> +|010> -|011> -|100> +|101> -|110> +|111> ] ← Flipped H|101> (1/8) [ +|000> +|001> -|010> -|011> -|100> -|101> +|110> +|111> ] ← H|110> (1/8) [ +|000> -|001> -|010> +|011> -|100> +|101> +|110> -|111> ] ← H|111>

4. Round 2: Final Amplitudes

|ψfinal> = -0.09|000> - 0.09|001> - 0.09|010> - 0.09|011> - 0.09|100> + 0.95|101> - 0.09|110> - 0.09|111>
Success: Measurement probability of |101> is ≈ 90.2%.
Search Comparison
Items (N) Classical Checks Grover Iterations
8 (3 qubits)42
1,000,000500,000785

Summary Checklist

  • Prepare: Create uniform superposition with H gates.
  • Mark: Use Oracle to flip target sign.
  • Amplify: Apply HZH to invert about the mean.
  • Repeat: Iterate ~√N times for maximum probability.

Leave a comment