Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

prove2quantum library: Defs.FreshCopyTomographyPrograms

Definition
QAlgorithms_Defs_FreshCopyTomographyPrograms

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Shared definitions of the prove2quantum Lean library (QAlgorithms.Defs.FreshCopyTomographyPrograms), reused by its paper formalizations.

  • BellLabel: Phase-free Bell labels (2305.15398 p.5, Eqs.(9)-(10)).
  • bellVector: Bell basis vector (I tensor P)|Phi>, with normalized maximally entangled state (2305.15398 p.5, §4).
  • bellInstrument: Projective Bell instrument: a single Kraus operator |P><P| for each phase-free label. The basis is computed from Paulis, not chosen from the unknown state (2305.15398 p.5). Completeness of this explicit family is supporting verification, not an accuracy field.
  • bellShot: Actual Bell probability on two fresh copies of the same rotated state; neither copy is replaced by a conjugate (2305.15398 p.5, Eq.(10)).
  • pauliProjector: Single-copy Pauli projectors, with true representing +1 (2305.15398 p.4, stabilizer test).
  • pauliShot: Actual one-copy Pauli shot after a known Clifford rotation (2305.15398 pp.4,6). No access to an exact expectation oracle is granted.
  • CopyClassicalInstruction: Explicit elementary classical register operations, not arbitrary real maps at unit cost (2305.15398 pp.4,6, generator extraction and tableau manipulation).
  • CopyClassicalInstruction.run: Computed classical transition and branch flag; one executed instruction costs one additional operation (2305.15398 pp.4,6).
  • CopyProgram: Finite adaptive fresh-copy program with explicit elementary classical work. Bell nodes consume two copies and Pauli nodes one. Report leaves are fixed finite code, not a true-state certified report (2305.15398 pp.4-6).
  • CopyLeaf: Branch data: optional report, counters (Bell outcomes, Pauli shots, additional work), and actual Born weight (2305.15398 p.6, resource paragraph).
  • copyProgramLaw: Computed fresh-copy program law. The separate counters retain failed reports. No probability, tomography or resource guarantees are assumed (2305.15398 pp.4-6).
  • CopyLeaf.copies: Physical copies are computed from separate fresh-shot counters (2305.15398 p.6: a Bell outcome is obtained from two copies).
Definition code
import Definitions.Def_QAlgorithms_Defs_DopedPauliDescriptions
import Definitions.Def_QAlgorithms_Defs_FiniteVectorSamplingPrograms

noncomputable section

attribute [local instance] Classical.propDecidable

open scoped Matrix

namespace QAlgorithms.DopedTomography

/-- Phase-free Bell labels (2305.15398 p.5, Eqs.(9)-(10)). -/
abbrev BellLabel (n : ℕ) := Fin n → Stabilizer.Pauli

/-- Bell basis vector (I tensor P)|Phi>, with normalized maximally entangled state
(2305.15398 p.5, §4). -/
def bellVector {n : ℕ} (P : BellLabel n) : EuclideanSpace ℂ (Qubits n × Qubits n) :=
  act (Matrix.kronecker (1 : Matrix (Qubits n) (Qubits n) ℂ) (pauliOps P)) (maxEntangled n)

/-- Projective Bell instrument: a single Kraus operator |P><P| for each phase-free label.
The basis is computed from Paulis, not chosen from the unknown state (2305.15398 p.5).
Completeness of this explicit family is supporting verification, not an accuracy field. -/
def bellInstrument {n : ℕ} (P : BellLabel n) :
    Matrix (Qubits n × Qubits n) (Qubits n × Qubits n) ℂ :=
  pureDensity (bellVector P)

/-- Actual Bell probability on two fresh copies of the same rotated state; neither copy
is replaced by a conjugate (2305.15398 p.5, Eq.(10)). -/
def bellShot {n : ℕ} (psi : EuclideanSpace ℂ (Qubits n)) (_state : IsState psi)
    (U : Matrix.unitaryGroup (Qubits n) ℂ) (P : BellLabel n) : ℝ :=
  let phi := act (U : Matrix _ _ ℂ) psi
  effectProb (bellInstrument P) (pureDensity (tensorVec phi phi))

/-- Single-copy Pauli projectors, with true representing +1 (2305.15398 p.4, stabilizer test). -/
def pauliProjector {n : ℕ} (P : BellLabel n) (plus : Bool) :
    Matrix (Qubits n) (Qubits n) ℂ :=
  (2⁻¹ : ℂ) • (1+(if plus then (1 : ℂ) else -1) • pauliOps P)

/-- Actual one-copy Pauli shot after a known Clifford rotation (2305.15398 pp.4,6).
No access to an exact expectation oracle is granted. -/
def pauliShot {n : ℕ} (psi : EuclideanSpace ℂ (Qubits n)) (_state : IsState psi)
    (U : Clifford.normalizer n) (P : BellLabel n) (plus : Bool) : ℝ :=
  effectProb (pauliProjector P plus) (pureDensity (act (U.val : Matrix _ _ ℂ) psi))

/-- Explicit elementary classical register operations, not arbitrary real maps at unit cost
(2305.15398 pp.4,6, generator extraction and tableau manipulation). -/
inductive CopyClassicalInstruction where
  | constant (dst value : ℕ)
  | add (dst a b : ℕ)
  | xor (dst a b : ℕ)
  | load (dst address : ℕ)
  | store (address src : ℕ)
  | compare (a b : ℕ)

/-- Computed classical transition and branch flag; one executed instruction costs one
additional operation (2305.15398 pp.4,6). -/
def CopyClassicalInstruction.run (memory : ℕ → ℕ) :
    CopyClassicalInstruction → Bool × (ℕ → ℕ)
  | .constant dst value => (false,Function.update memory dst value)
  | .add dst a b => (false,Function.update memory dst (memory a+memory b))
  | .xor dst a b => (false,Function.update memory dst (Nat.xor (memory a) (memory b)))
  | .load dst address => (false,Function.update memory dst (memory (memory address)))
  | .store address src => (false,Function.update memory (memory address) (memory src))
  | .compare a b => (decide (memory a ≤ memory b),memory)

/-- Finite adaptive fresh-copy program with explicit elementary classical work. Bell nodes
consume two copies and Pauli nodes one. Report leaves are fixed finite code, not a
true-state certified report (2305.15398 pp.4-6). -/
inductive CopyProgram (n : ℕ) where
  | output (D : Option (Description n))
  | bell (U : Clifford.normalizer n) (next : BellLabel n → CopyProgram n)
  | pauli (U : Clifford.normalizer n) (P : BellLabel n) (next : Bool → CopyProgram n)
  | random (size : ℕ) (weights : PMF (Fin size)) (next : Fin size → CopyProgram n)
  | classical (op : CopyClassicalInstruction) (next : Bool → CopyProgram n)

/-- Branch data: optional report, counters (Bell outcomes, Pauli shots, additional work),
and actual Born weight (2305.15398 p.6, resource paragraph). -/
abbrev CopyLeaf (n : ℕ) := (Option (Description n) × (Fin 3 → ℕ)) × ℝ

/-- Computed fresh-copy program law. The separate counters retain failed reports.
No probability, tomography or resource guarantees are assumed (2305.15398 pp.4-6). -/
def copyProgramLaw {n : ℕ} (psi : EuclideanSpace ℂ (Qubits n)) (state : IsState psi) :
    CopyProgram n → (ℕ → ℕ) → List (CopyLeaf n)
  | .output D, _ => [((D,0),1)]
  | .bell U next, memory => (Finset.univ.toList : List (BellLabel n)).flatMap fun P =>
      (copyProgramLaw psi state (next P) memory).map fun l =>
        ((l.1.1,l.1.2+Pi.single 0 1),bellShot psi state U.val P*l.2)
  | .pauli U P next, memory => [false,true].flatMap fun b =>
      (copyProgramLaw psi state (next b) memory).map fun l =>
        ((l.1.1,l.1.2+Pi.single 1 1),pauliShot psi state U P b*l.2)
  | .random _ weights next, memory => (List.finRange _).flatMap fun i =>
      (copyProgramLaw psi state (next i) memory).map fun l => (l.1,(weights i).toReal*l.2)
  | .classical op next, memory =>
      let result := op.run memory
      (copyProgramLaw psi state (next result.1) result.2).map fun l =>
        ((l.1.1,l.1.2+Pi.single 2 1),l.2)

/-- Physical copies are computed from separate fresh-shot counters
(2305.15398 p.6: a Bell outcome is obtained from two copies). -/
def CopyLeaf.copies {n : ℕ} (l : CopyLeaf n) : ℕ := 2*l.1.2 0+l.1.2 1

example {n : ℕ} (psi : EuclideanSpace ℂ (Qubits n)) (state : IsState psi) (memory : ℕ → ℕ) :
    copyProgramLaw psi state (.output none) memory = [((none,0),1)] := rfl

example {n : ℕ} (P : BellLabel n) :
    pauliProjector P true+pauliProjector P false = 1 := by
  ext a b
  simp [pauliProjector, Matrix.one_apply]
  split_ifs <;> ring

example : CopyLeaf.copies (⟨⟨none,![1,0,0]⟩,1⟩ : CopyLeaf 0) = 2 := rfl

end QAlgorithms.DopedTomography
Source
prove2quantum Lean library, module QAlgorithms.Defs.FreshCopyTomographyPrograms
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 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