Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Quantum, classical and triangular systems in product coordinates

Definition
GPTIP632_Classical_Supplement_Trees

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information

System presentations are finite binary trees of positive-dimensional quantum systems, positive-dimensional standard classical systems and a distinguished three-coordinate leaf. A quantum leaf uses the real Hermitian basis EjjE_{jj}Ejj​, Ejk+EkjE_{jk}+E_{kj}Ejk​+Ekj​ and iEkj−iEjkiE_{kj}-iE_{jk}iEkj​−iEjk​. Classical leaves use diagonal matrix units. Nodes use Kronecker products, giving ordinary quantum composites and direct sums for classical factors. In the standard reading the distinguished leaf is another presentation of Δ3\Delta_3Δ3​. In the triangular reading it is WvW_vWv​ in the original coordinates, with e0=(0,0,1)e_0=(0,0,1)e0​=(0,0,1), e1=(1,0,1)e_1=(1,0,1)e1​=(1,0,1), e2=(1,v,1)e_2=(1,v,1)e2​=(1,v,1). The transport is Lv(x,y,z)=(z−x,x−y/v,y/v)L_v(x,y,z)=(z-x,x-y/v,y/v)Lv​(x,y,z)=(z−x,x−y/v,y/v), inverted by the matrix with these three columns. On a composite, transport is the tensor product of the transports on its leaves. The parameter satisfies 0<v<10<v<10<v<1, so the inverse divisions are defined. Tree labels and parentheses retain presentations of the same operational system; they do not introduce a different cone or a new message capability.

Definition code
import Mathlib
import Definitions.Def_GPTIP632_Classical_Supplement_Frames

set_option autoImplicit false

/-!
# Systems of the constructed theories: trees of quantum, classical and triangular systems

Kishor Bharti, *Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical
Theories*, STOC 2027 submission #632 (October 2026), Example B.2, B.3, B.5 (p.14, PDF p.16),
Examples B.17, B.18 (p.18, PDF p.20), Examples B.22, B.23 (p.19, PDF p.21).

A system of the theories QC, classical theory, `G_v` and `G^Q_v` is a binary tree whose leaves are
the quantum systems `Q_{d+1}`, the classical systems `Δ_{n+1}` and the triangular system `W_v`;
an inner node is the composite of its two subtrees, in product coordinates (local tomography, (T1)).

* `Q_{d+1}` has the coordinates `Fin (d+1) × Fin (d+1)` of the standard real basis of
  `Herm_{d+1}(ℂ)` (`hermB`), the positive semidefinite cone and the trace (Example B.3).
* `Δ_{n+1}` has `ℝ^{n+1}`, the nonnegative orthant and the coordinate sum (Example B.2), presented
  by the diagonal matrix units.
* In the *quantum–classical reading* (`frame`, `hsys`) a triangular leaf is read as `Δ_3`; this is
  the QC system `A ⊗ Δ_3^{⊗c}` of Example B.23.
* `wsys v t` transports `hsys t` through `L_v` on every triangular leaf and the identity elsewhere
  (`Tmat`); on a triangular leaf this is `W_v` in the paper's coordinates `(x, y, z)` with cone
  generated by `e0 = (0,0,1)`, `e1 = (1,0,1)`, `e2 = (1,v,1)` and unit `u(x,y,z) = z`
  (Example B.5). For trees with classical and triangular leaves only, the cone is the minimal tensor
  product of the leaf cones (Example B.22); that it coincides is part of Theorem G.1 (i).
-/

noncomputable section

namespace GPTIP632.Classical.Supplement

open GPTIP632.Classical Matrix Complex
open scoped Kronecker ComplexOrder

/-! ### The standard real basis of `Herm_n(ℂ)` -/

/-- The standard real basis of the Hermitian `n × n` matrices, indexed by `(j, k)`:
`E_jj` for `j = k`; `E_jk + E_kj` for `j < k`; `i E_kj − i E_jk` for `j > k`. A Hermitian `H` has
the coordinates `H_jj`, `Re H_jk` (`j < k`) and `Im H_kj` (`j > k`). -/
def hermB (n : ℕ) (p : Fin n × Fin n) : Matrix (Fin n) (Fin n) ℂ := fun a b =>
  if p.1 = p.2 then (if a = p.1 ∧ b = p.1 then 1 else 0)
  else if p.1 < p.2 then (if a = p.1 ∧ b = p.2 then 1 else 0) + (if a = p.2 ∧ b = p.1 then 1 else 0)
  else (if a = p.2 ∧ b = p.1 then I else 0) - (if a = p.1 ∧ b = p.2 then I else 0)

lemma hermB_herm (n : ℕ) (p : Fin n × Fin n) : (hermB n p).IsHermitian := by
  obtain ⟨j, k⟩ := p
  ext a b
  simp only [conjTranspose_apply, hermB]
  rcases lt_trichotomy j k with h | rfl | h
  · have h1 : j ≠ k := ne_of_lt h
    simp only [h1, h, if_false, if_true]
    split_ifs <;> simp_all
  · split_ifs <;> simp_all
  · have h1 : j ≠ k := ne_of_gt h
    have h2 : ¬ j < k := not_lt.mpr (le_of_lt h)
    simp only [h1, h2, if_false]
    split_ifs <;> simp_all

lemma hermB_sum_apply (n : ℕ) (y : Fin n × Fin n → ℂ) (a b : Fin n) :
    (∑ p, y p • hermB n p) a b =
      if a = b then y (a, a) else if a < b then y (a, b) + I * y (b, a) else y (b, a) - I * y (a, b) := by
  rw [Matrix.sum_apply]
  simp only [Matrix.smul_apply, smul_eq_mul]
  rcases lt_trichotomy a b with h | rfl | h
  · have hne : a ≠ b := ne_of_lt h
    rw [if_neg hne, if_pos h, Fintype.sum_eq_add (a, b) (b, a) (by simp [hne])]
    · have hb : ¬ b < a := not_lt.mpr (le_of_lt h)
      simp [hermB, hne, h, hb, hne.symm, mul_comm]
    · rintro ⟨j, k⟩ ⟨h1, h2⟩
      simp only [hermB]
      split_ifs <;> simp_all <;> aesop
  · rw [if_pos rfl, Fintype.sum_eq_single (a, a)]
    · simp [hermB]
    · rintro ⟨j, k⟩ hjk
      simp only [hermB]
      split_ifs <;> simp_all <;> aesop
  · have hne : a ≠ b := ne_of_gt h
    have hb : ¬ a < b := not_lt.mpr (le_of_lt h)
    rw [if_neg hne, if_neg hb, Fintype.sum_eq_add (b, a) (a, b) (by simp [hne])]
    · simp [hermB, hne, h, hb, hne.symm, mul_comm]; ring
    · rintro ⟨j, k⟩ ⟨h1, h2⟩
      simp only [hermB]
      split_ifs <;> simp_all <;> aesop

/-- The frame of the quantum system `Q_n`: the standard real basis of `Herm_n(ℂ)`. -/
def quantumFrame (n : ℕ) : HermFrame (Fin n × Fin n) (Fin n) where
  β := hermB n
  herm := hermB_herm n
  inj := fun y hy => by
    have he : ∀ a b, (∑ p, y p • hermB n p) a b = 0 := fun a b => by rw [hy]; rfl
    funext ⟨j, k⟩
    rcases lt_trichotomy j k with h | rfl | h
    · have h1 := he j k
      have h2 := he k j
      rw [hermB_sum_apply, if_neg (ne_of_lt h), if_pos h] at h1
      rw [hermB_sum_apply, if_neg (ne_of_gt h), if_neg (not_lt.mpr (le_of_lt h))] at h2
      have : y (j, k) = 0 := by linear_combination (h1 + h2) / 2
      simpa using this
    · have := he j j
      rw [hermB_sum_apply, if_pos rfl] at this
      simpa using this
    · have h1 := he k j
      have h2 := he j k
      rw [hermB_sum_apply, if_neg (ne_of_lt h), if_pos h] at h1
      rw [hermB_sum_apply, if_neg (ne_of_gt h), if_neg (not_lt.mpr (le_of_lt h))] at h2
      have h3 : (2 * I) * y (j, k) = 0 := by linear_combination h1 - h2
      have h4 : (2 * I : ℂ) ≠ 0 := mul_ne_zero two_ne_zero I_ne_zero
      simpa using (mul_eq_zero.mp h3).resolve_left h4
  one_mem := ⟨fun p => if p.1 = p.2 then 1 else 0, by
    ext a b
    rw [hermB_sum_apply]
    by_cases h : a = b
    · subst h; simp
    · have h' : b ≠ a := Ne.symm h
      simp [h, h', one_apply_ne h]⟩

/-- The frame of the classical system `Δ_n`: the diagonal matrix units `E_ii`. -/
def classicalFrame (n : ℕ) : HermFrame (Fin n) (Fin n) where
  β := fun i => Matrix.single i i 1
  herm := fun i => by
    unfold IsHermitian
    rw [conjTranspose_single, star_one]
  inj := fun y hy => by
    funext i
    have := congrFun (congrFun hy i) i
    simpa [Matrix.sum_apply, single_apply] using this
  one_mem := ⟨fun _ => 1, by
    ext a b
    rw [Matrix.sum_apply, Fintype.sum_eq_single a]
    · by_cases h : a = b
      · subst h; simp
      · simp [single_apply, one_apply_ne h, h]
    · intro i hi
      simp [single_apply]
      intro h; exact absurd h hi⟩

/-! ### Trees of systems -/

/-- A system of the constructed theories: the quantum system `Q_{d+1}`, the classical system
`Δ_{n+1}`, the triangular system `W` (`W_v` in `G_v`, `G^Q_v`; `Δ_3` in the quantum–classical
reading), or the composite of two systems. -/
inductive Tree where
  | quantum (d : ℕ) : Tree
  | classical (n : ℕ) : Tree
  | tri : Tree
  | node (A B : Tree) : Tree
  deriving DecidableEq

namespace Tree

/-- The coordinate index type of a tree (product coordinates at nodes). -/
def ι : Tree → Type
  | quantum d => Fin (d + 1) × Fin (d + 1)
  | classical n => Fin (n + 1)
  | tri => Fin 3
  | node A B => ι A × ι B

/-- The matrix index type of a tree in the quantum–classical reading. -/
def D : Tree → Type
  | quantum d => Fin (d + 1)
  | classical n => Fin (n + 1)
  | tri => Fin 3
  | node A B => D A × D B

instance instFintypeι : (t : Tree) → Fintype t.ι
  | quantum d => inferInstanceAs (Fintype (Fin (d + 1) × Fin (d + 1)))
  | classical n => inferInstanceAs (Fintype (Fin (n + 1)))
  | tri => inferInstanceAs (Fintype (Fin 3))
  | node A B => @instFintypeProd _ _ (instFintypeι A) (instFintypeι B)

instance instDecEqι : (t : Tree) → DecidableEq t.ι
  | quantum d => inferInstanceAs (DecidableEq (Fin (d + 1) × Fin (d + 1)))
  | classical n => inferInstanceAs (DecidableEq (Fin (n + 1)))
  | tri => inferInstanceAs (DecidableEq (Fin 3))
  | node A B => @instDecidableEqProd _ _ (instDecEqι A) (instDecEqι B)

instance instFintypeD : (t : Tree) → Fintype t.D
  | quantum d => inferInstanceAs (Fintype (Fin (d + 1)))
  | classical n => inferInstanceAs (Fintype (Fin (n + 1)))
  | tri => inferInstanceAs (Fintype (Fin 3))
  | node A B => @instFintypeProd _ _ (instFintypeD A) (instFintypeD B)

instance instDecEqD : (t : Tree) → DecidableEq t.D
  | quantum d => inferInstanceAs (DecidableEq (Fin (d + 1)))
  | classical n => inferInstanceAs (DecidableEq (Fin (n + 1)))
  | tri => inferInstanceAs (DecidableEq (Fin 3))
  | node A B => @instDecidableEqProd _ _ (instDecEqD A) (instDecEqD B)

/-- The Hermitian frame of a tree in the quantum–classical reading: the standard basis of
`Herm_{d+1}` at a quantum leaf, the diagonal units at a classical leaf, `Δ_3` at a triangular leaf,
and Kronecker products at nodes (composites of quantum systems are `Herm(C^d ⊗ C^{d'})` with the
positive semidefinite cone; composites with classical systems are direct sums, Example B.18). -/
def frame : (t : Tree) → HermFrame t.ι t.D
  | quantum d => quantumFrame (d + 1)
  | classical n => classicalFrame (n + 1)
  | tri => classicalFrame 3
  | node A B => (frame A).kron (frame B)

/-- The system of a tree in the quantum–classical reading (QC, classical theory). -/
def hsys (t : Tree) : System := (frame t).toSystem

/-- Every leaf is quantum (`Q_{d+1}`): a finite-dimensional quantum memory. -/
def IsQuantum : Tree → Prop
  | quantum _ => True
  | classical _ => False
  | tri => False
  | node A B => IsQuantum A ∧ IsQuantum B

/-- Whether a tree has a quantum leaf / a triangular leaf (used to cut out the systems of each
theory). -/
def hasQ : Tree → Bool
  | quantum _ => true
  | classical _ => false
  | tri => false
  | node A B => hasQ A || hasQ B

def hasW : Tree → Bool
  | quantum _ => false
  | classical _ => false
  | tri => true
  | node A B => hasW A || hasW B

end Tree

/-! ### The triangular system and the transport `L_v` -/

/-- The linear map `L_v : ℝ³ → ℝ³` of Example B.5 with `L_v(e_i) = δ_{i+1}`:
`L_v(x, y, z) = (z − x, x − y/v, y/v)`. -/
def Lmat (v : ℝ) : Matrix (Fin 3) (Fin 3) ℝ := !![-1, 0, 1; 1, -1 / v, 0; 0, 1 / v, 0]

/-- `L_v^{-1}`, the matrix with columns `e0 = (0,0,1)`, `e1 = (1,0,1)`, `e2 = (1,v,1)`. -/
def Linv (v : ℝ) : Matrix (Fin 3) (Fin 3) ℝ := !![0, 1, 1; 0, 0, v; 1, 1, 1]

lemma Linv_mul_Lmat {v : ℝ} (hv : v ≠ 0) : Linv v * Lmat v = 1 := by
  ext i j
  fin_cases i <;> fin_cases j <;> simp [Linv, Lmat, Matrix.mul_apply, Fin.sum_univ_three, hv, neg_div, one_div]

lemma Lmat_mul_Linv {v : ℝ} (hv : v ≠ 0) : Lmat v * Linv v = 1 := by
  ext i j
  fin_cases i <;> fin_cases j <;> simp [Linv, Lmat, Matrix.mul_apply, Fin.sum_univ_three, hv, neg_div, one_div]

namespace Tree

/-- The transport matrix of a tree: `L_v` on triangular leaves, the identity on the other leaves,
Kronecker products at nodes (`id_{V_A} ⊗ L_v^{⊗c}`, Example B.23). -/
def Tmat (v : ℝ) : (t : Tree) → Matrix t.ι t.ι ℝ
  | quantum _ => 1
  | classical _ => 1
  | tri => Lmat v
  | node A B => Tmat v A ⊗ₖ Tmat v B

/-- The inverse transport matrix. -/
def Tinv (v : ℝ) : (t : Tree) → Matrix t.ι t.ι ℝ
  | quantum _ => 1
  | classical _ => 1
  | tri => Linv v
  | node A B => Tinv v A ⊗ₖ Tinv v B

lemma Tinv_mul_Tmat {v : ℝ} (hv : v ≠ 0) : (t : Tree) → Tinv v t * Tmat v t = 1
  | quantum _ => by simp [Tinv, Tmat]
  | classical _ => by simp [Tinv, Tmat]
  | tri => Linv_mul_Lmat hv
  | node A B => by
    show (Tinv v A ⊗ₖ Tinv v B : Matrix (A.ι × B.ι) (A.ι × B.ι) ℝ) * (Tmat v A ⊗ₖ Tmat v B) = 1
    rw [← mul_kronecker_mul, Tinv_mul_Tmat hv A, Tinv_mul_Tmat hv B, one_kronecker_one]

lemma Tmat_mul_Tinv {v : ℝ} (hv : v ≠ 0) : (t : Tree) → Tmat v t * Tinv v t = 1
  | quantum _ => by simp [Tinv, Tmat]
  | classical _ => by simp [Tinv, Tmat]
  | tri => Lmat_mul_Linv hv
  | node A B => by
    show (Tmat v A ⊗ₖ Tmat v B : Matrix (A.ι × B.ι) (A.ι × B.ι) ℝ) * (Tinv v A ⊗ₖ Tinv v B) = 1
    rw [← mul_kronecker_mul, Tmat_mul_Tinv hv A, Tmat_mul_Tinv hv B, one_kronecker_one]

/-- The system of a tree in the theories with the triangular system `W_v` adjoined (`G_v`,
`G^Q_v`): the QC system `hsys t` (triangular leaves read as `Δ_3`) transported through
`Tmat v t`, i.e., cone `{x : Tmat v t · x ∈ V⁺}` and unit `u ∘ Tmat v t`. A triangular leaf is
`W_v` with cone `cone{e0, e1, e2}` and unit `(0, 0, 1)`. -/
def wsys (v : Set.Ioo (0 : ℝ) 1) (t : Tree) : System :=
  System.transport (hsys t) (Tmat v t) (Tinv v t) (Tinv_mul_Tmat (ne_of_gt v.2.1) t)
    (Tmat_mul_Tinv (ne_of_gt v.2.1) t)

end Tree

end GPTIP632.Classical.Supplement

end
Source
Kishor Bharti, Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories, STOC 2027 submission #632 (October 2026), source.pdf SHA-256 ebbc45027e7a3b48cbfb1a2deb89e9a7d8374373b23763680b948fda16cf4da7, pp.14, 17–19, 22–23, 28, 32–35 (PDF pp.16, 19–21, 24–25, 30, 34–37), Examples B.3, B.5, B.17–B.23, Definitions D.3–D.4, F.1, §G

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