Quantum Amplitude Estimation — QPE-Based Quadratic Speedup

Estimate a = sin²(θ) via Quantum Phase Estimation. QPE gives 1/ε precision with 1/ε queries vs classical 1/ε².

True a: 0.250
QPE estimate: —
Classical est: —
QPE error: —
Classical error: —
QAE Protocol:
1. Prepare |ψ⟩=√(1-a)|0⟩+√a|1⟩
2. Apply Grover operator Q_a
3. QPE on Q_a → phase θ/π
4. a = sin²(measured θ)
QPE: m bits → ε=1/2^m
Complexity: O(1/ε) vs O(1/ε²)
Complexity comparison:
Classical: O(1/ε²) samples
Quantum: O(1/ε) oracle calls
Quadratic speedup for Monte Carlo integration!