Theorem 12 (Amplitude Estimation), p. 19 — |ã − a| ≤ 2πk√(a(1−a))/M + k²π²/M² w.p. ≥ 8/π² (k = 1), > 1 − 1/(2(k−1)) (k ≥ 2); exact for a = 0, and for a = 1 with M even
ProvedQAmpEst.Est.theorem_12Let be a unitary on a finite-dimensional Hilbert space with computational basis indexed by , let mark the good basis states, and let be the probability that measuring gives a good state. Let , and let be the output of , where is the measured value of the first register. For every positive integer , the event
has probability
- at least when , and
- greater than when .
Moreover,
- if then with certainty, and
- if and is even, then with certainty.
This is the main estimation result of the paper: applications of give an estimate of with additive error of order , a quadratic improvement over classical sampling.
Formalization Note The probability of an event is the sum, over the outcomes in it, of , where . The clause "it uses exactly evaluations of " is not formalized: the matrix model has no oracle whose calls could be counted. holds by construction. No restriction and no lower bound on is assumed.
import Mathlib import Definitions.Def_QAmpEst_Est_Setting open scoped Real Kronecker
namespace QAmpEst.Est
/-- Theorem 12 (Amplitude Estimation), arXiv:quant-ph/0005055v1, p. 19: for any positive
integer `k`, the output `ã = sin²(πy/M)` of `Est_Amp(A, χ, M)` satisfies
`|ã − a| ≤ 2πk√(a(1 − a))/M + k²π²/M²` with probability at least `8/π²` when `k = 1` and with
probability greater than `1 − 1/(2(k − 1))` for `k ≥ 2`. If `a = 0` then `ã = 0` with
certainty, and if `a = 1` and `M` is even, then `ã = 1` with certainty.
(The query count "exactly `M` evaluations of `f`" is not formalized.) -/
theorem theorem_12 {ι : Type*} [Fintype ι] [DecidableEq ι] (A : Matrix ι ι ℂ)
(hA : A ∈ Matrix.unitaryGroup ι ℂ) (χ : ι → Bool) (z0 : ι) (M : ℕ) (hM : 0 < M) (k : ℕ) (hk : 1 ≤ k) :
let a := succProb A χ z0
let P := outcomeProb M A χ z0
let E := Finset.univ.filter (fun y : Fin M =>
|estimate M y - a| ≤
2 * π * (k : ℝ) * Real.sqrt (a * (1 - a)) / (M : ℝ) + (k : ℝ) ^ 2 * π ^ 2 / (M : ℝ) ^ 2)
(k = 1 → 8 / π ^ 2 ≤ ∑ y ∈ E, P y) ∧
(2 ≤ k → 1 - 1 / (2 * ((k : ℝ) - 1)) < ∑ y ∈ E, P y) ∧
(a = 0 → ∑ y ∈ Finset.univ.filter (fun y : Fin M => estimate M y = 0), P y = 1) ∧
(a = 1 → Even M →
∑ y ∈ Finset.univ.filter (fun y : Fin M => estimate M y = 1), P y = 1) := by sorry
end QAmpEst.Est
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.