Stopping at , is observed with error at most
ProvedGroverWiki.measureProb_groverState_floorgrover-algorithmquantum-computingquantum-search
Let have exactly one index with , let and . After Grover iterations, measuring the state yields with probability
i.e. with error at most . This is a quantitative form of the source's claim that stopping at gives the correct answer with error .
Formalization Note The source's is in general not an integer; the mission rounds it down, and replaces "" by the explicit bound .
Preamble
import Mathlib import Definitions.Def_GroverWiki_Defs open Matrix
Formal statement
namespace GroverWiki
/-- Stopping at `r = ⌊π/(4t)⌋` iterations, `t = arcsin(1/√N)`, the measurement yields `ω` with
error at most `1/N`. -/
theorem measureProb_groverState_floor {N : ℕ} (f : Fin N → Fin 2) (ω : Fin N)
(hω : ∀ x, f x = 1 ↔ x = ω) :
1 - 1 / (N : ℝ) ≤
measureProb (groverState f ⌊Real.pi / (4 * Real.arcsin (1 / Real.sqrt N))⌋₊) ω := by
sorry
end GroverWiki
Source
Wikipedia, "Grover's algorithm", revision oldid=1373498442, https://en.wikipedia.org/w/index.php?title=Grover%27s_algorithm&oldid=1373498442, section "Algebraic proof" (PDF p. 6), with section "Geometric proof" (PDF p. 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.