Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6, properties 2–3 — R(P)R(P)R(P) fixes ∣π⟩∣0ks⟩|\pi\rangle|0^{ks}\rangle∣π⟩∣0ks⟩ and ∥(R(P)+Id)∣ψ⟩∣0ks⟩∥≤21−k∥ψ∥\|(R(P)+\mathrm{Id})|\psi\rangle|0^{ks}\rangle\|\le2^{1-k}\|\psi\|∥(R(P)+Id)∣ψ⟩∣0ks⟩∥≤21−k∥ψ∥ for ψ∈A+B\psi\in\mathcal A+\mathcal Bψ∈A+B, ψ⊥π\psi\perp\piψ⊥π

Proved
QuantumWalkSearch.PhaseReflection.theorem_6

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1phase-estimationquantum-searchquantum-walk

Let PPP be an ergodic and reversible Markov chain on a state space XXX of size n≥2n\ge2n≥2, with stationary distribution π\piπ, quantum walk W(P)W(P)W(P) and phase gap Δ(P)\Delta(P)Δ(P). For an integer k≥0k\ge0k≥0 let s=⌈log⁡2(2π/Δ(P))⌉s=\lceil\log_2(2\pi/\Delta(P))\rceils=⌈log2​(2π/Δ(P))⌉ and let R(P)R(P)R(P) be the circuit on CX×X⊗(C2s)⊗k\mathbb C^{X\times X}\otimes(\mathbb C^{2^s})^{\otimes k}CX×X⊗(C2s)⊗k obtained by applying the phase-estimation circuit C(W(P))C(W(P))C(W(P)) to kkk ancilla registers, flipping the phase of every basis state with a non-zero estimate in some register, and reversing the phase estimation. Then:

  1. R(P) ∣π⟩∣0ks⟩=∣π⟩∣0ks⟩R(P)\,|\pi\rangle|0^{ks}\rangle=|\pi\rangle|0^{ks}\rangleR(P)∣π⟩∣0ks⟩=∣π⟩∣0ks⟩;
  2. for every ∣ψ⟩∈A+B|\psi\rangle\in\mathcal A+\mathcal B∣ψ⟩∈A+B orthogonal to ∣π⟩|\pi\rangle∣π⟩,
∥(R(P)+Id) ∣ψ⟩∣0ks⟩∥ ≤ 21−k ∥ψ∥.\big\|(R(P)+\mathrm{Id})\,|\psi\rangle|0^{ks}\rangle\big\|\ \le\ 2^{1-k}\,\|\psi\| .​(R(P)+Id)∣ψ⟩∣0ks⟩​ ≤ 21−k∥ψ∥.

So on A+B\mathcal A+\mathcal BA+B, with the ancillas initialised to ∣0ks⟩|0^{ks}\rangle∣0ks⟩, R(P)R(P)R(P) is within 21−k2^{1-k}21−k of the reflection ref(π)\mathrm{ref}(\pi)ref(π) about ∣π⟩|\pi\rangle∣π⟩. This is the diffusion operator of the quantum-walk search algorithm of §3.3: it replaces the costly exact reflection by kkk phase estimations of the walk, which is the source of the 1/δ1/\sqrt\delta1/δ​ dependence of the search cost.

Formalization Note R(P)R(P)R(P) is the explicit circuit of the proof (definition reflectionCircuit), not "some circuit with properties 2–3". Reversibility is the standing assumption of §3.2 (p. 8: "in the rest of this section, and in the next one, we assume that the classical Markov chain P is ergodic and reversible"); Theorem 6's own text says only "ergodic", but property 3 fails without it (if D(P)D(P)D(P) has a second singular value 111, W(P)W(P)W(P) fixes a vector of A+B\mathcal A+\mathcal BA+B orthogonal to ∣π⟩|\pi\rangle∣π⟩). Property 2's premise "if ∣π⟩|\pi\rangle∣π⟩ is the unique 1-eigenvector" holds under these hypotheses and is not assumed. "Ergodic" is Matrix.IsPrimitive. The explicit sss of the proof replaces "s∈log⁡2(1/Δ(P))+O(1)s\in\log_2(1/\Delta(P))+O(1)s∈log2​(1/Δ(P))+O(1)"; with the convention Δ(P)=π\Delta(P)=\piΔ(P)=π when D(P)D(P)D(P) has no singular value in (0,1)(0,1)(0,1), s≥1s\ge1s≥1. Property 1 (gate counts and calls to c-W(P)c\text{-}W(P)c-W(P)), the qubit count 2⌈log⁡2n⌉+ks2\lceil\log_2n\rceil+ks2⌈log2​n⌉+ks (the system register is CX×X\mathbb C^{X\times X}CX×X rather than qubits) and uniformity are cost statements and are not formalized. k=0k=0k=0 is allowed (then R(P)=IdR(P)=\mathrm{Id}R(P)=Id and the bound reads 2∥ψ∥2\|\psi\|2∥ψ∥).

Preamble
import Mathlib
import Definitions.Def_QuantumWalkSearch_PhaseReflection_ReflectionCircuit
Formal statement
namespace QuantumWalkSearch.PhaseReflection

/-- Theorem 6 (p. 9), properties 2 and 3, for the circuit `R(P)` of its proof, under the standing
assumption of §3.2 (p. 8) that `P` is ergodic and reversible. -/
theorem theorem_6 {X : Type*} [Fintype X] [DecidableEq X] (P : Matrix X X ℝ) (πd : X → ℝ)
    (hP : P ∈ Matrix.rowStochastic ℝ X) (herg : P.IsPrimitive)
    (hπ : IsStationaryDist P πd) (hrev : IsReversible P πd)
    (hn : 2 ≤ Fintype.card X) (k : ℕ) :
    Matrix.toEuclideanLin (reflectionCircuit P πd k) (tensorZero (piState P πd)) =
      tensorZero (piState P πd) ∧
    ∀ ψ ∈ spaceA P ⊔ spaceB P πd, inner ℂ (piState P πd) ψ = 0 →
      ‖Matrix.toEuclideanLin (reflectionCircuit P πd k + 1) (tensorZero ψ)‖ ≤
        (2 : ℝ) ^ (1 - (k : ℤ)) * ‖ψ‖ := by sorry

end QuantumWalkSearch.PhaseReflection
Source
Magniez, Nayak, Roland, Santha, Search via Quantum Walk, arXiv:quant-ph/0608026v4, p. 9, Theorem 6, properties 2 and 3 (proof pp. 9–10); standing assumption §3.2, p. 8
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me