§4, p. 16 — the accumulated error of Tolerant RAA: δ_t ≤ π/8 + 9γ/8
ProvedQuantumWalkSearch.ApproxRAA.drift_totalamplitude-amplificationerror-analysisp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithms
Under the hypotheses of Lemma 1 with , let be the smallest non-negative integer with , and run Tolerant RAA with registers. Let be the state after Step 4 of attempt and . Then
Re-using the leftover state of a failed attempt instead of a fresh copy of costs at most this much at the decisive attempt ; combined with Lemma 1 it leaves a marked projection of length at least .
Formalization Note The paper states this under , which makes . The Lean statement does not assume it: when one has and , so the bound holds trivially. At the formula reads .
Preamble
import Mathlib import Definitions.Def_QuantumWalkSearch_ApproxRAA_Setting import Definitions.Def_QuantumWalkSearch_ApproxRAA_Circuit import Definitions.Def_QuantumWalkSearch_ApproxRAA_Tolerant
Formal statement
namespace QuantumWalkSearch.ApproxRAA
/-- The accumulated error (§4, p. 16, proof of Lemma 2). With `T ≥ t` registers, `t` as in
Lemma 1 and `0 < γ ≤ 1/40`, the drift at attempt `t` of Tolerant RAA satisfies
`δ_t = ‖|ψ_t⟩ − |φ_t⟩‖ ≤ π/8 + 9γ/8`. -/
theorem drift_total {X : Type*} [Fintype X] [DecidableEq X] {κ : ℕ → Type*}
[∀ i, Fintype (κ i)] [∀ i, DecidableEq (κ i)]
(M : Finset X) (piState : EuclideanSpace ℂ (X × X)) (hπ : ‖piState‖ = 1)
(z : ∀ i, κ i) (R : ∀ i, Matrix (X × X × κ i) (X × X × κ i) ℂ)
(γ : ℝ) (hγ : 0 < γ) (hγ' : γ ≤ 1 / 40) (hR : ApproxReflections piState z R γ) (t : ℕ)
(ht : IsFirstHit (Real.arcsin (Real.sqrt (markedWeight M piState))) t) (T : ℕ)
(htT : t ≤ T) :
‖tolState M z R piState T t - phi M z R piState T t‖ ≤ Real.pi / 8 + 9 * γ / 8 := by sorry
end QuantumWalkSearch.ApproxRAA
Source
Magniez, Nayak, Roland, Santha, Search via Quantum Walk, arXiv:quant-ph/0608026v4, p. 16, §4, proof of Lemma 2 (last line of the display after Eq. (5))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.