§4, p. 16 — second term of Eq. (5): ‖|µ⊥_{k+1}⟩ − |µ⊥_k⟩‖ ≤ 2‖ω_{k+1}‖/cos ϕ_{k+1} ≤ 12β_{k+1}3^kϕ₀ for k < t − 1
ProvedQuantumWalkSearch.ApproxRAA.drift_secondamplitude-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 , where . Let be the error state of level and . Then for every
This bounds the middle terms of the error recursion (5): the unmarked direction of the ideal states drifts by at most per level.
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
/-- Second term of Eq. (5) (§4, p. 16, proof of Lemma 2). With `t` as in Lemma 1,
`0 < γ ≤ 1/40`, `ϕ₀ = sin⁻¹ √p_M` and the error state
`|ω_{k+1}⟩ = E_{k+1} · ref(M̃⊥) |φ_k⟩` (p. 13), for every `k < t − 1` (here `k : Fin T`):
`‖|µ⊥_{k+1}⟩ − |µ⊥_k⟩‖ ≤ 2‖ω_{k+1}‖ / cos ϕ_{k+1} ≤ 12 β_{k+1} 3^k ϕ₀`. -/
theorem drift_second {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 : ℕ)
(k : Fin T) (hkt : k.val + 1 < t) :
‖muPerp M z R piState T (k.val + 1) - muPerp M z R piState T k.val‖ ≤
2 * ‖act (errOp M z R piState T k) (act (flipMarked M) (phi M z R piState T k.val))‖ /
Real.cos (markedAngle M (phi M z R piState T (k.val + 1))) ∧
2 * ‖act (errOp M z R piState T k) (act (flipMarked M) (phi M z R piState T k.val))‖ /
Real.cos (markedAngle M (phi M z R piState T (k.val + 1))) ≤
12 * beta γ (k.val + 1) *
((3 : ℝ) ^ k.val * Real.arcsin (Real.sqrt (markedWeight M piState))) := 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 (second term of Eq. (5)); ω_{k+1} defined p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.