Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact finite-graph valence-bond projection amplitudes

Proved
QAlgorithms.Papers.Independent.Intakenext100.P52.valenceProjection_coordinates

by Mrnaiq · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

measurement-based-quantum-computationquantum-information

Let VVV be a finite set of sites and E⊆V×VE\subseteq V\times VE⊆V×V a finite set of ordered edges. Place one normalized H-bond CZ∣+,+⟩CZ|+,+\rangleCZ∣+,+⟩ on every edge. For an output string x∈{0,1}Vx\in\{0,1\}^Vx∈{0,1}V, the local all-equal projection requires each virtual edge endpoint to equal the bit at its incident site. Denote this contraction by ΠE\Pi_EΠE​ and the product of H-bonds by ∣HE⟩|H_E\rangle∣HE​⟩. Then

⟨x∣ΠE∣HE⟩=2−∣E∣∏(u,v)∈E(−1)xuxv.\langle x|\Pi_E|H_E\rangle=2^{-|E|}\prod_{(u,v)\in E}(-1)^{x_u x_v}.⟨x∣ΠE​∣HE​⟩=2−∣E∣(u,v)∈E∏​(−1)xu​xv​.

This is the unnormalized amplitude calculation in the valence-bond representation of graph cluster states. The finite-graph form includes empty products; no division by a branch norm is used.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P52
noncomputable section
open QAlgorithms QAlgorithms.Papers.Independent.Intakenext100.P52 QAlgorithms.Papers.Independent.Information100.P21 QAlgorithms.Papers.Independent.Gap20.P01
open scoped Matrix ComplexConjugate
private theorem hBond_apply (a b : Bool) : hBond (a,b) = (1 / 2 : ℂ) * czPhase a b := by
  have h2 : ((Real.sqrt 2 : ℝ) : ℂ)^2 = 2 := by
    rw [← Complex.ofReal_pow, Real.sq_sqrt (by norm_num)]; norm_num
  cases a <;> cases b <;>
    norm_num [hBond, czPhase, act, tensorVec, hadamard, ket, controlled, pauliZ,
      Matrix.mulVec, dotProduct, Matrix.one_apply, Fintype.sum_prod_type, Fintype.sum_bool,
      Complex.ofReal_inv, ← pow_two, inv_pow, h2]
private theorem valenceProjection_apply {V : Type*} [Fintype V] [DecidableEq V]
    (E : Finset (V × V)) (x : V → Bool) (w : (EdgeLabel E × Bool) → Bool) :
    valenceProjection E x w =
      if w = (fun p => if p.2 then x p.1.val.2 else x p.1.val.1) then 1 else 0 := by
  unfold valenceProjection
  congr 1
  apply propext
  constructor
  · intro h
    funext p
    rcases p with ⟨e,b⟩
    cases b
    · exact (h e).1
    · exact (h e).2
  · intro h e
    subst w
    simp
Formal statement
theorem QAlgorithms.Papers.Independent.Intakenext100.P52.valenceProjection_coordinates {V : Type} [Fintype V] [DecidableEq V]
    (E : Finset (V × V)) (x : V → Bool) :
    applyRect (valenceProjection E) (bondGrid E) x = (1 / 2 : ℂ)^E.card * edgePhase E x := by sorry
Source
R. Jozsa, An introduction to measurement based quantum computation, https://arxiv.org/abs/quant-ph/0508124v2, PDF pp.17–18, Lemma 3 and Figures 13–15; finite-graph coordinate form of the projection calculation.

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