Theorem 6, properties 2–3 — fixes and for ,
ProvedQuantumWalkSearch.PhaseReflection.theorem_6Let be an ergodic and reversible Markov chain on a state space of size , with stationary distribution , quantum walk and phase gap . For an integer let and let be the circuit on obtained by applying the phase-estimation circuit to ancilla registers, flipping the phase of every basis state with a non-zero estimate in some register, and reversing the phase estimation. Then:
- ;
- for every orthogonal to ,
So on , with the ancillas initialised to , is within of the reflection about . This is the diffusion operator of the quantum-walk search algorithm of §3.3: it replaces the costly exact reflection by phase estimations of the walk, which is the source of the dependence of the search cost.
Formalization Note 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 has a second singular value , fixes a vector of orthogonal to ). Property 2's premise "if is the unique 1-eigenvector" holds under these hypotheses and is not assumed. "Ergodic" is Matrix.IsPrimitive. The explicit of the proof replaces ""; with the convention when has no singular value in , . Property 1 (gate counts and calls to ), the qubit count (the system register is rather than qubits) and uniformity are cost statements and are not formalized. is allowed (then and the bound reads ).
import Mathlib import Definitions.Def_QuantumWalkSearch_PhaseReflection_ReflectionCircuit
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.