acts on the plane as the reflection across
ProvedGroverWiki.phaseOracle_reflection_perpgrover-algorithmquantum-computingquantum-search
Let have exactly one index with , let , and let . Then for all ,
That is, on the plane spanned by and the oracle is the reflection across (the reflection at the hyperplane orthogonal to ); in particular it maps the plane to itself.
Formalization Note For the sum defining is empty and ; the statement then only concerns multiples of .
Preamble
import Mathlib import Definitions.Def_GroverWiki_Defs open Matrix
Formal statement
namespace GroverWiki
/-- In the plane spanned by `|s'⟩` and `|ω⟩`, `U_ω` acts as the reflection across `|s'⟩`. -/
theorem phaseOracle_reflection_perp {N : ℕ} (f : Fin N → Fin 2) (ω : Fin N)
(hω : ∀ x, f x = 1 ↔ x = ω) (a b : ℂ) :
phaseOracle f *ᵥ (a • ket ω + b • perpState ω) = (-a) • ket ω + b • perpState ω := 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 "Geometric proof" (PDF p. 4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.