Quantum, classical and triangular systems in product coordinates
DefinitionGPTIP632_Classical_Supplement_TreesSystem 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 , and . 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 . In the triangular reading it is in the original coordinates, with , , . The transport is , 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 , 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.
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