Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence

Definition
QAlgorithms_Papers_Independent_Intakenext100_P95

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

prove2quantum

The objects the formalized statements of Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence (arXiv:1503.06237) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • SubsetConfig: PDF pp.5–7: configurations on a named set of tensor legs.
  • mergeSubset: PDF p.7, (2.4)–(2.5): join complementary coordinate assignments, without conjugation.
  • flatten: PDF p.7, Definition 2: rows are outgoing legs; columns are incoming legs.
  • moveInput: PDF p.7, (2.5): move the first input factor to the second output factor.
  • IsPerfect: PDF p.7, Definition 2: even arity, nonzero, and positive scaled Gram identity for every at-most-half flattening. No marginal or entropy conclusion is assumed.
  • subsetDensity: PDF pp.12–13: actual partial trace retaining A, using the frozen traceLeft. The first coordinate of the reindexed density is the discarded complement.
  • entropyV: PDF pp.12–13: von Neumann entropy in units log(v), obtained from frozen bit entropy.
  • tripartiteInfo: PDF p.21, (4.13): tripartite information, with each union a physical subsystem.
  • encoderPurification: PDF pp.8,45: the normalized pure Choi vector of a one-spin encoder, reference leg last. This coefficient vector is distinct from frozen channel Choi density matrices.
  • IsPerfectErasureCode: PDF pp.8,45: maximum erasure protection for an isometric one-spin encoder: any set of at most n−1 erased physical spins admits a CPTP recovery independent of the input. The conversion theorem separately requires 2n−1 physical spins. Channel equality is on all operators, hence includes arbitrary reference systems. Purity and maximally mixed marginals are not hypotheses of this predicate.
  • fiveOps: PDF p.43, (A.1): the four signed +1 stabilizer generators, in physical wire order.
  • fiveGenerator: PDF p.43, (A.1): the actual generator matrices, including their +1 phases.
  • fiveCode: PDF p.43, (A.2): the simultaneous +1 eigenspace of exactly the A.1 generators.
  • fiveProjector: PDF pp.43–44: the product of the four commuting +1 spectral projectors.
  • fiveLogicalZero: PDF pp.44–45: a fixed normalized + logical-Z codeword; the projection of |00000⟩ has norm 1/4, so its scalar normalization is 4.
  • fiveLogicalOne: PDF p.44, (A.3): logical X maps the chosen zero codeword to the one codeword.
  • fiveEncoder: PDF pp.44–45: the explicit five-qubit encoder in the logical computational basis.
  • sixQubitState: PDF p.45: normalized version of the printed unnormalized six-qubit state, with its reference qubit last.
  • sixGenerator: PDF p.44, (A.5): recycle four checks, then append the all-X and all-Z checks.
  • Trit: PDF pp.45–46: the qutrit computational labels, with arithmetic modulo three.
  • qutritWeyl: PDF p.46, (A.10): X decrements labels, and Z multiplies |j⟩ by omega^j. Here omega = exp(2pii/3). This is the phase-free X^a Z^b representative on m qutrits.
  • qutritEncoder: PDF p.45: the three codewords (000+111+222), (012+120+201), and (021+102+210), each normalized by 1/sqrt(3).
  • fourQutritState: PDF p.45: the nine printed four-qutrit terms, each with amplitude 1/3. The last leg is the logical reference.
  • qutritChecks: PDF p.45, (A.9): identical X- and Z-type check vectors, expressing self-dual CSS.
  • qutritCSSSpace: PDF pp.45–46: the simultaneous +1 subspace for the four A.9 checks. The X and Z checks use the same two check rows, rather than a binary CSS surrogate.
  • addDown: PDF p.46, (A.11): first adder, controlled by wire 0 and targeting wire 1.
  • addUp: PDF p.46, (A.11): second adder, controlled by wire 1 and targeting wire 0.
  • qutritCircuit: PDF p.46, (A.11): the permutation (x1,x2) ↦ (2x1+x2,x1+x2).
  • IsQutritClifford: PDF p.46: a two-qutrit Clifford is unitary and normalizes the actual phase-aware qutrit Pauli group; phases are powers of omega.
  • BinaryPhaseSpace: PDF pp.60–61: a Pauli modulo its scalar phase is a pair of binary exponent vectors.
  • normalizerSpace: PDF pp.60–61: the Pauli centralizer in phase-free coordinates. The set inside span is already a vector subspace, since the displayed form is bilinear.
  • supportSpace: PDF pp.60–61: labels supported within A, in both X and Z coordinates.
  • logicalSupportDimension: PDF pp.60–61: ell(A), dimension of centralizing labels representable within A, modulo the stabilizer label space S. Scalar phases have already been removed. Independence here does not require the represented logical operators to commute.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Ensemble
import Definitions.Def_QAlgorithms_Defs_QECC
import Definitions.Def_QAlgorithms_Defs_PauliNoiseFourier

/-!
Statements from Pastawski, Yoshida, Harlow and Preskill, arXiv:1503.06237v2.
Page numbers below are PDF page numbers. Paper-local constructions are explicit;
network results requiring unavailable geometric interfaces are recorded in HARD.md.
Compilation and independent moderation are pending.
-/

namespace QAlgorithms.Papers.Independent.Intakenext100.P95

open scoped Matrix ComplexConjugate

noncomputable section

local instance (p : Prop) : Decidable p := Classical.propDecidable p

/-- PDF pp.5–7: configurations on a named set of tensor legs. -/
abbrev SubsetConfig (V : Type*) {L : Type*} (A : Finset L) := {i : L // i ∈ A} → V

/-- PDF p.7, (2.4)–(2.5): join complementary coordinate assignments, without conjugation. -/
def mergeSubset {L V : Type*} [Fintype L] [DecidableEq L] (A : Finset L)
    (a : SubsetConfig V A) (b : SubsetConfig V Aᶜ) : L → V :=
  fun i => if h : i ∈ A then a ⟨i, h⟩ else b ⟨i, Finset.mem_compl.mpr h⟩

/-- PDF p.7, Definition 2: rows are outgoing legs; columns are incoming legs. -/
def flatten {L V : Type*} [Fintype L] [DecidableEq L]
    (T : EuclideanSpace ℂ (L → V)) (A : Finset L) :
    Matrix (SubsetConfig V Aᶜ) (SubsetConfig V A) ℂ :=
  fun b a => T (mergeSubset A a b)

/-- PDF p.7, (2.5): move the first input factor to the second output factor. -/
def moveInput {A1 A2 B : Type*} (T : Matrix B (A2 × A1) ℂ) :
    Matrix (B × A2) A1 ℂ := fun ba a1 => T ba.1 (ba.2, a1)

/-- PDF p.7, Definition 2: even arity, nonzero, and positive scaled Gram identity
for every at-most-half flattening. No marginal or entropy conclusion is assumed. -/
def IsPerfect {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L] [DecidableEq V]
    (T : EuclideanSpace ℂ (L → V)) : Prop :=
  Even (Fintype.card L) ∧ T ≠ 0 ∧ ∀ A : Finset L,
    2 * A.card ≤ Fintype.card L → ∃ c : ℝ, 0 < c ∧
      (flatten T A)ᴴ * flatten T A = (c : ℂ) • 1

/-- PDF pp.12–13: actual partial trace retaining A, using the frozen traceLeft.
The first coordinate of the reindexed density is the discarded complement. -/
def subsetDensity {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L]
    (A : Finset L) (rho : Matrix (L → V) (L → V) ℂ) :
    Matrix (SubsetConfig V A) (SubsetConfig V A) ℂ :=
  traceLeft (fun p q : SubsetConfig V Aᶜ × SubsetConfig V A =>
    rho (mergeSubset A p.2 p.1) (mergeSubset A q.2 q.1))

/-- PDF pp.12–13: von Neumann entropy in units log(v), obtained from frozen bit entropy. -/
def entropyV {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L] [DecidableEq V]
    (psi : EuclideanSpace ℂ (L → V)) (A : Finset L) : ℝ :=
  vnEntropy (subsetDensity A (pureDensity psi)) / Real.logb 2 (Fintype.card V : ℝ)

/-- PDF p.21, (4.13): tripartite information, with each union a physical subsystem. -/
def tripartiteInfo {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L] [DecidableEq V]
    (psi : EuclideanSpace ℂ (L → V)) (A B C : Finset L) : ℝ :=
  entropyV psi A + entropyV psi B + entropyV psi C - entropyV psi (A ∪ B) -
    entropyV psi (A ∪ C) - entropyV psi (B ∪ C) + entropyV psi (A ∪ B ∪ C)

/-- PDF pp.8,45: the normalized pure Choi vector of a one-spin encoder, reference leg last.
This coefficient vector is distinct from frozen channel Choi density matrices. -/
def encoderPurification {L V : Type*} [Fintype V] (M : Matrix (L → V) V ℂ) :
    EuclideanSpace ℂ ((L ⊕ Unit) → V) :=
  WithLp.toLp 2 fun z => ((Real.sqrt (Fintype.card V : ℝ))⁻¹ : ℂ) *
    M (fun i => z (Sum.inl i)) (z (Sum.inr ()))

/-- PDF pp.8,45: maximum erasure protection for an isometric one-spin encoder:
any set of at most n−1 erased physical spins admits a CPTP recovery independent
of the input. The conversion theorem separately requires 2n−1 physical spins.
Channel equality is on all operators, hence includes arbitrary reference systems.
Purity and maximally mixed marginals are not hypotheses of this predicate. -/
def IsPerfectErasureCode {L V : Type*} [Fintype L] [Fintype V]
    [DecidableEq L] [DecidableEq V] (n : ℕ) (M : Matrix (L → V) V ℂ) : Prop :=
  Mᴴ * M = 1 ∧ ∀ A : Finset L, A.card ≤ n - 1 →
    ∃ R : Superop (SubsetConfig V Aᶜ) V, IsChannel R ∧
      ∀ rho : Matrix V V ℂ, R (subsetDensity Aᶜ (M * rho * Mᴴ)) = rho

example {L V : Type*} [Fintype L] [DecidableEq L] (A : Finset L)
    (a : SubsetConfig V A) (b : SubsetConfig V Aᶜ) (i : L) (hi : i ∈ A) :
    mergeSubset A a b i = a ⟨i, hi⟩ := by simp [mergeSubset, hi]

example {A1 A2 B : Type*} (T : Matrix B (A2 × A1) ℂ) (b : B) (a2 : A2) (a1 : A1) :
    moveInput T (b, a2) a1 = T b (a2, a1) := rfl

example {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L] [DecidableEq V] :
    ¬ IsPerfect (0 : EuclideanSpace ℂ (L → V)) := by simp [IsPerfect]

example {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L] (A : Finset L) :
    subsetDensity A (0 : Matrix (L → V) (L → V) ℂ) = 0 := by
  ext a b
  simp [subsetDensity, traceLeft]

example : (((Fintype.card Unit : ℂ)⁻¹ • (1 : Matrix Unit Unit ℂ)) () ()) = 1 := by
  simp

example {L V : Type*} [Fintype L] [Fintype V] [DecidableEq L] [DecidableEq V]
    (A : Finset L) : entropyV (0 : EuclideanSpace ℂ (L → V)) A = 0 := by
  have hp : pureDensity (0 : EuclideanSpace ℂ (L → V)) = 0 := by
    ext a b
    simp [pureDensity]
  have ht : subsetDensity A (0 : Matrix (L → V) (L → V) ℂ) = 0 := by
    ext a b
    simp [subsetDensity, traceLeft]
  rw [entropyV, hp, ht]
  simp [vnEntropy]

/-- PDF p.43, (A.1): the four signed +1 stabilizer generators, in physical wire order. -/
def fiveOps : Fin 4 → Fin 5 → Stabilizer.Pauli :=
  ![![.X, .Z, .Z, .X, .I], ![.I, .X, .Z, .Z, .X],
    ![.X, .I, .X, .Z, .Z], ![.Z, .X, .I, .X, .Z]]

/-- PDF p.43, (A.1): the actual generator matrices, including their +1 phases. -/
def fiveGenerator (j : Fin 4) : Matrix (Qubits 5) (Qubits 5) ℂ := pauliOps (fiveOps j)

/-- PDF p.43, (A.2): the simultaneous +1 eigenspace of exactly the A.1 generators. -/
def fiveCode : Submodule ℂ (EuclideanSpace ℂ (Qubits 5)) :=
  ⨅ j : Fin 4, LinearMap.ker (Matrix.toEuclideanLin (fiveGenerator j - 1))

/-- PDF pp.43–44: the product of the four commuting +1 spectral projectors. -/
def fiveProjector : Matrix (Qubits 5) (Qubits 5) ℂ :=
  (List.ofFn fun j : Fin 4 => (2⁻¹ : ℂ) • (1 + fiveGenerator j)).prod

/-- PDF pp.44–45: a fixed normalized + logical-Z codeword; the projection of
|00000⟩ has norm 1/4, so its scalar normalization is 4. -/
def fiveLogicalZero : EuclideanSpace ℂ (Qubits 5) := 4 • act fiveProjector (zeroKet 5)

/-- PDF p.44, (A.3): logical X maps the chosen zero codeword to the one codeword. -/
def fiveLogicalOne : EuclideanSpace ℂ (Qubits 5) :=
  act (pauliOps (fun _ : Fin 5 => Stabilizer.Pauli.X)) fiveLogicalZero

/-- PDF pp.44–45: the explicit five-qubit encoder in the logical computational basis. -/
def fiveEncoder : Matrix (Qubits 5) Bool ℂ :=
  fun z b => if b then fiveLogicalOne z else fiveLogicalZero z

/-- PDF p.45: normalized version of the printed unnormalized six-qubit state,
with its reference qubit last. -/
def sixQubitState : EuclideanSpace ℂ (Qubits 6) :=
  WithLp.toLp 2 fun z => ((Real.sqrt 2)⁻¹ : ℂ) *
    fiveEncoder (fun i : Fin 5 => z ⟨i.val, Nat.lt_trans i.isLt (by decide)⟩) (z 5)

/-- PDF p.44, (A.5): recycle four checks, then append the all-X and all-Z checks. -/
def sixGenerator (j : Fin 6) : Matrix (Qubits 6) (Qubits 6) ℂ :=
  if h : j.val < 4 then
    pauliOps (fun q : Fin 6 => if hq : q.val < 5 then fiveOps ⟨j.val, h⟩ ⟨q.val, hq⟩ else .I)
  else if j.val = 4 then pauliOps (fun _ => Stabilizer.Pauli.X)
  else pauliOps (fun _ => Stabilizer.Pauli.Z)

example : fiveOps 0 0 = Stabilizer.Pauli.X := rfl

example : fiveEncoder (fun _ => false) false = fiveLogicalZero (fun _ => false) := rfl

/-- PDF pp.45–46: the qutrit computational labels, with arithmetic modulo three. -/
abbrev Trit := ZMod 3

/-- PDF p.46, (A.10): X decrements labels, and Z multiplies |j⟩ by omega^j.
Here omega = exp(2*pi*i/3). This is the phase-free X^a Z^b representative on m qutrits. -/
def qutritWeyl (m : ℕ) (a b : Fin m → Trit) :
    Matrix (Fin m → Trit) (Fin m → Trit) ℂ :=
  fun y x => if ∀ i, y i = x i - a i then
    (Complex.exp (2 * (Real.pi : ℂ) * Complex.I / 3)) ^ (∑ i, b i * x i).val else 0

/-- PDF p.45: the three codewords (000+111+222), (012+120+201),
and (021+102+210), each normalized by 1/sqrt(3). -/
def qutritEncoder : Matrix (Fin 3 → Trit) Trit ℂ :=
  fun y l => if y 1 = y 0 + l ∧ y 2 = y 0 + 2 * l then
    ((Real.sqrt 3)⁻¹ : ℂ) else 0

/-- PDF p.45: the nine printed four-qutrit terms, each with amplitude 1/3.
The last leg is the logical reference. -/
def fourQutritState : EuclideanSpace ℂ (Fin 4 → Trit) :=
  WithLp.toLp 2 fun y => if y 1 = y 0 + y 3 ∧ y 2 = y 0 + 2 * y 3 then (1 / 3 : ℂ) else 0

/-- PDF p.45, (A.9): identical X- and Z-type check vectors, expressing self-dual CSS. -/
def qutritChecks : Fin 2 → Fin 4 → Trit := ![![1, 1, 1, 0], ![1, -1, 0, 1]]

/-- PDF pp.45–46: the simultaneous +1 subspace for the four A.9 checks.
The X and Z checks use the same two check rows, rather than a binary CSS surrogate. -/
def qutritCSSSpace : Submodule ℂ (EuclideanSpace ℂ (Fin 4 → Trit)) :=
  (⨅ j : Fin 2, LinearMap.ker
    (Matrix.toEuclideanLin (qutritWeyl 4 (qutritChecks j) 0 - 1))) ⊓
  (⨅ j : Fin 2, LinearMap.ker
    (Matrix.toEuclideanLin (qutritWeyl 4 0 (qutritChecks j) - 1)))

example : fourQutritState ![0, 0, 0, 0] = (1 / 3 : ℂ) := by
  change (if (0 : Trit) = 0 + 0 ∧ (0 : Trit) = 0 + 2 * 0 then
    (1 / 3 : ℂ) else 0) = (1 / 3 : ℂ)
  norm_num

example : qutritChecks 1 1 = (-1 : Trit) := rfl

/-- PDF p.46, (A.11): first adder, controlled by wire 0 and targeting wire 1. -/
def addDown : Matrix (Fin 2 → Trit) (Fin 2 → Trit) ℂ :=
  fun y x => if y 0 = x 0 ∧ y 1 = x 0 + x 1 then 1 else 0

/-- PDF p.46, (A.11): second adder, controlled by wire 1 and targeting wire 0. -/
def addUp : Matrix (Fin 2 → Trit) (Fin 2 → Trit) ℂ :=
  fun y x => if y 0 = x 0 + x 1 ∧ y 1 = x 1 then 1 else 0

/-- PDF p.46, (A.11): the permutation (x1,x2) ↦ (2x1+x2,x1+x2). -/
def qutritCircuit : Matrix (Fin 2 → Trit) (Fin 2 → Trit) ℂ :=
  fun y x => if y 0 = 2 * x 0 + x 1 ∧ y 1 = x 0 + x 1 then 1 else 0

/-- PDF p.46: a two-qutrit Clifford is unitary and normalizes the actual
phase-aware qutrit Pauli group; phases are powers of omega. -/
def IsQutritClifford (U : Matrix (Fin 2 → Trit) (Fin 2 → Trit) ℂ) : Prop :=
  Uᴴ * U = 1 ∧ ∀ a b : Fin 2 → Trit, ∃ aout bout : Fin 2 → Trit, ∃ c : Trit,
    U * qutritWeyl 2 a b * Uᴴ =
      (Complex.exp (2 * (Real.pi : ℂ) * Complex.I / 3)) ^ c.val • qutritWeyl 2 aout bout

example : qutritCircuit ![2, 1] ![1, 0] = 1 := by norm_num [qutritCircuit]

/-- PDF pp.60–61: a Pauli modulo its scalar phase is a pair of binary exponent vectors. -/
abbrev BinaryPhaseSpace (n : ℕ) := SparsePauliNoise.Label n

/-- PDF pp.60–61: the Pauli centralizer in phase-free coordinates. The set inside
span is already a vector subspace, since the displayed form is bilinear. -/
def normalizerSpace {n : ℕ} (S : Submodule (ZMod 2) (BinaryPhaseSpace n)) :
    Submodule (ZMod 2) (BinaryPhaseSpace n) :=
  Submodule.span (ZMod 2) {a | ∀ b ∈ S, SparsePauliNoise.symplecticPairing a b = 0}

/-- PDF pp.60–61: labels supported within A, in both X and Z coordinates. -/
def supportSpace {n : ℕ} (A : Finset (Fin n)) :
    Submodule (ZMod 2) (BinaryPhaseSpace n) :=
  Submodule.span (ZMod 2) {a | ∀ i, i ∉ A → a.1 i = 0 ∧ a.2 i = 0}

/-- PDF pp.60–61: ell(A), dimension of centralizing labels representable within A,
modulo the stabilizer label space S. Scalar phases have already been removed.
Independence here does not require the represented logical operators to commute. -/
def logicalSupportDimension {n : ℕ} (S : Submodule (ZMod 2) (BinaryPhaseSpace n))
    (A : Finset (Fin n)) : ℕ :=
  Module.finrank (ZMod 2) ((normalizerSpace S ⊓ supportSpace A).map S.mkQ)

example {n : ℕ} (a : BinaryPhaseSpace n) : SparsePauliNoise.symplecticPairing 0 a = 0 := by
  simp [SparsePauliNoise.symplecticPairing, dotProduct]

example {n : ℕ} (A : Finset (Fin n)) : (0 : BinaryPhaseSpace n) ∈ supportSpace A :=
  Submodule.zero_mem _

end

end QAlgorithms.Papers.Independent.Intakenext100.P95
Source
Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence, arXiv:1503.06237v2, https://arxiv.org/abs/1503.06237v2
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

QAlgorithms.Papers.Independent.Intakenext100.P95.BinaryPhaseSpace

For every natural number nnn, the binary phase space is the type

Vn=F2n×F2n,F2=Z/2Z.V_n=\mathbb F_2^n\times\mathbb F_2^n, \qquad \mathbb F_2=\mathbb Z/2\mathbb Z.Vn​=F2n​×F2n​,F2​=Z/2Z.

Thus an element is an ordered pair of functions from {0,…,n−1}\{0,\ldots,n-1\}{0,…,n−1} to F2\mathbb F_2F2​. The value n=0n=0n=0 is included; in that case both functions are empty and V0V_0V0​ has one element.

QAlgorithms.Papers.Independent.Intakenext100.P95.IsPerfect

For finite types L,VL,VL,V, both with decidable equality, a complex vector TTT indexed by configurations L→VL\to VL→V satisfies this predicate precisely when ∣L∣|L|∣L∣ is even, T≠0T\ne0T=0, and for every finite subset A⊆LA\subseteq LA⊆L with 2∣A∣≤∣L∣2|A|\le |L|2∣A∣≤∣L∣, there exists a real number c>0c>0c>0, possibly depending on AAA, such that

FA†FA=cI,FA(b,a)=T(merge⁡A(a,b)).F_A^\dagger F_A=cI, \qquad F_A(b,a)=T\bigl(\operatorname{merge}_A(a,b)\bigr).FA†​FA​=cI,FA​(b,a)=T(mergeA​(a,b)).

Here a:A→Va:A\to Va:A→V, b:(L∖A)→Vb:(L\setminus A)\to Vb:(L∖A)→V, the merged function equals aaa on AAA and bbb outside AAA, and III is the identity matrix on the configurations A→VA\to VA→V. No unit-norm condition is imposed on TTT. The subsets include A=∅A=\varnothingA=∅, and the definition permits L=∅L=\varnothingL=∅; in that case TTT has one coordinate and the predicate requires that coordinate to be nonzero.

QAlgorithms.Papers.Independent.Intakenext100.P95.IsPerfectErasureCode

For any finite types L,VL,VL,V, each equipped with decidable equality and possibly empty, any natural number nnn, and any complex matrix MMM with rows indexed by configurations L→VL\to VL→V and columns indexed by VVV, this property means that M†M=IVM^\dagger M=I_VM†M=IV​ and that every subset A⊆LA\subseteq LA⊆L with ∣A∣≤n−1|A|\le n-1∣A∣≤n−1 admits a recovery map RAR_ARA​ from matrices on configurations L∖A→VL\setminus A\to VL∖A→V to matrices on VVV, satisfying

RA ⁣(Tr⁡A(MρM†))=ρfor every complex matrix ρ on V.R_A\!\left(\operatorname{Tr}_A(M\rho M^\dagger)\right)=\rho \qquad\text{for every complex matrix }\rho\text{ on }V.RA​(TrA​(MρM†))=ρfor every complex matrix ρ on V.

Here Tr⁡A\operatorname{Tr}_ATrA​ sums over matching configurations on AAA: its entry at configurations u,u′u,u'u,u′ on L∖AL\setminus AL∖A is ∑a:A→V(MρM†)a∪u,  a∪u′\sum_{a:A\to V}(M\rho M^\dagger)_{a\cup u,\;a\cup u'}∑a:A→V​(MρM†)a∪u,a∪u′​, where the unions denote the unique merged configurations. The requirement that RAR_ARA​ be a channel means that there are a natural number rrr, possibly zero, and matrices EjE_jEj​ from configurations on L∖AL\setminus AL∖A to VVV, for 0≤j<r0\le j<r0≤j<r, such that ∑jEj†Ej=I\sum_jE_j^\dagger E_j=I∑j​Ej†​Ej​=I and RA(X)=∑jEjXEj†R_A(X)=\sum_jE_jXE_j^\daggerRA​(X)=∑j​Ej​XEj†​ for every matrix XXX. The recovery identity applies to all matrices ρ\rhoρ, without positivity or trace assumptions. The subtraction n−1n-1n−1 is truncated natural-number subtraction, so both n=0n=0n=0 and n=1n=1n=1 require recovery only for A=∅A=\varnothingA=∅.

QAlgorithms.Papers.Independent.Intakenext100.P95.IsPurePerfectCode

For finite types L,VL,VL,V, both with decidable equality, a natural number nnn, and a complex matrix MMM with rows indexed by configurations L→VL\to VL→V and columns by VVV, this predicate requires M†M=IVM^\dagger M=I_VM†M=IV​ and the following two conditions for every finite subset A⊆LA\subseteq LA⊆L satisfying ∣A∣≤n−1|A|\le n-1∣A∣≤n−1. First, there exists a map RRR from matrices on configurations (L∖A)→V(L\setminus A)\to V(L∖A)→V to matrices on VVV that has a finite Kraus representation

R(X)=∑j=0m−1EjXEj†,∑j=0m−1Ej†Ej=I,R(X)=\sum_{j=0}^{m-1}E_jXE_j^\dagger, \qquad \sum_{j=0}^{m-1}E_j^\dagger E_j=I,R(X)=j=0∑m−1​Ej​XEj†​,j=0∑m−1​Ej†​Ej​=I,

for some natural number mmm and matrices EjE_jEj​ with rows indexed by VVV and columns by configurations on L∖AL\setminus AL∖A, and that satisfies

R((MρM†)L∖A)=ρfor every complex matrix ρ on V.R\bigl((M\rho M^\dagger)_{L\setminus A}\bigr)=\rho \quad\text{for every complex matrix }\rho\text{ on }V.R((MρM†)L∖A​)=ρfor every complex matrix ρ on V.

Second, every vector ψ∈CV\psi\in\mathbb C^Vψ∈CV with ∥ψ∥=1\|\psi\|=1∥ψ∥=1 satisfies

(M∣ψ⟩⟨ψ∣M†)A=1∣{a:A→V}∣ I.\bigl(M|\psi\rangle\langle\psi|M^\dagger\bigr)_A = \frac{1}{|\{a:A\to V\}|}\,I.(M∣ψ⟩⟨ψ∣M†)A​=∣{a:A→V}∣1​I.

For any matrix XXX on configurations L→VL\to VL→V, its restriction-and-sum matrix on a subset DDD is defined by XD(a,a′)=∑b:(L∖D)→VX(a∪b,a′∪b)X_D(a,a')=\sum_{b:(L\setminus D)\to V}X(a\cup b,a'\cup b)XD​(a,a′)=∑b:(L∖D)→V​X(a∪b,a′∪b), where merging uses aaa on DDD and bbb outside it; also (∣ψ⟩⟨ψ∣)(v,v′)=ψ(v)ψ(v′)‾(|\psi\rangle\langle\psi|)(v,v')=\psi(v)\overline{\psi(v')}(∣ψ⟩⟨ψ∣)(v,v′)=ψ(v)ψ(v′)​. Recovery is required for all matrices ρ\rhoρ, without positivity or normalization assumptions. The subtraction n−1n-1n−1 is truncated natural-number subtraction, so for n=0n=0n=0 or n=1n=1n=1, only A=∅A=\varnothingA=∅ is tested. Empty types are permitted, and the universal condition on unit vectors is vacuous if VVV is empty.

QAlgorithms.Papers.Independent.Intakenext100.P95.IsQutritClifford

For a complex matrix UUU indexed by pairs of elements of F3=Z/3Z\mathbb F_3=\mathbb Z/3\mathbb ZF3​=Z/3Z, this predicate means that U†U=IU^\dagger U=IU†U=I and that, for every a,b∈F32a,b\in\mathbb F_3^2a,b∈F32​, there exist aout,bout∈F32a_{\mathrm{out}},b_{\mathrm{out}}\in\mathbb F_3^2aout​,bout​∈F32​ and c∈F3c\in\mathbb F_3c∈F3​ such that

UW(a,b)U†=ωval⁡(c)W(aout,bout).U W(a,b)U^\dagger=\omega^{\operatorname{val}(c)}W(a_{\mathrm{out}},b_{\mathrm{out}}).UW(a,b)U†=ωval(c)W(aout​,bout​).

Here U†U^\daggerU† is the conjugate transpose, ω=exp⁡(2πi/3)\omega=\exp(2\pi i/3)ω=exp(2πi/3), val⁡\operatorname{val}val takes the representative in {0,1,2}\{0,1,2\}{0,1,2}, and the matrix W(a,b)W(a,b)W(a,b) is defined, for x,y∈F32x,y\in\mathbb F_3^2x,y∈F32​, by

W(a,b)y,x={ωval⁡(∑j=01bjxj),yj=xj−aj for both j,0,otherwise.W(a,b)_{y,x}= \begin{cases} \omega^{\operatorname{val}(\sum_{j=0}^{1}b_jx_j)},& y_j=x_j-a_j\text{ for both }j,\\ 0,&\text{otherwise}. \end{cases}W(a,b)y,x​={ωval(∑j=01​bj​xj​),0,​yj​=xj​−aj​ for both j,otherwise.​

The sums, products, and coordinate differences inside F3\mathbb F_3F3​ are taken modulo 333; the existentially quantified output labels and phase need not be unique.

QAlgorithms.Papers.Independent.Intakenext100.P95.SubsetConfig

For arbitrary types VVV and LLL and a finite subset A⊆LA\subseteq LA⊆L, a configuration on AAA with values in VVV is a function A→VA\to VA→V, where the domain consists precisely of the elements of LLL belonging to AAA. No finiteness assumption on either type is required. When A=∅A=\varnothingA=∅, there is exactly one such function, including when VVV is empty.

QAlgorithms.Papers.Independent.Intakenext100.P95.Trit

This introduces Trit\mathrm{Trit}Trit as another name for the ring Z/3Z\mathbb Z/3\mathbb ZZ/3Z. Its elements are residue classes modulo 333, so all addition, subtraction, and multiplication on trits are performed modulo 333.

QAlgorithms.Papers.Independent.Intakenext100.P95.addDown

This defines a complex matrix DDD with rows and columns indexed by pairs of trits y,x∈(Z/3Z)2y,x\in(\mathbb Z/3\mathbb Z)^2y,x∈(Z/3Z)2, by

Dy,x={1,y0=x0 and y1=x0+x1,0,otherwise,D_{y,x}= \begin{cases} 1,&y_0=x_0\text{ and }y_1=x_0+x_1,\\ 0,&\text{otherwise}, \end{cases}Dy,x​={1,0,​y0​=x0​ and y1​=x0​+x1​,otherwise,​

where addition is modulo 333. Equivalently, its column indexed by (x0,x1)(x_0,x_1)(x0​,x1​) is the coordinate unit vector at (x0,x0+x1)(x_0,x_0+x_1)(x0​,x0​+x1​).

QAlgorithms.Papers.Independent.Intakenext100.P95.addUp

This defines a complex matrix UUU with rows and columns indexed by pairs of trits y,x∈(Z/3Z)2y,x\in(\mathbb Z/3\mathbb Z)^2y,x∈(Z/3Z)2, by

Uy,x={1,y0=x0+x1 and y1=x1,0,otherwise,U_{y,x}= \begin{cases} 1,&y_0=x_0+x_1\text{ and }y_1=x_1,\\ 0,&\text{otherwise}, \end{cases}Uy,x​={1,0,​y0​=x0​+x1​ and y1​=x1​,otherwise,​

where addition is modulo 333. Equivalently, its column indexed by (x0,x1)(x_0,x_1)(x0​,x1​) is the coordinate unit vector at (x0+x1,x1)(x_0+x_1,x_1)(x0​+x1​,x1​).

QAlgorithms.Papers.Independent.Intakenext100.P95.encoderPurification

For an arbitrary type LLL, a finite type VVV, and any complex matrix MMM whose rows are indexed by configurations L→VL\to VL→V and columns by VVV, this definition produces the complex vector indexed by configurations on the disjoint union L⊔{∗}L\sqcup\{*\}L⊔{∗}, with amplitudes

ΨM(z)=1∣V∣ M(z∣L,z(∗)).\Psi_M(z)= \frac{1}{\sqrt{|V|}}\, M\bigl(z|_L,z(*)\bigr).ΨM​(z)=∣V∣​1​M(z∣L​,z(∗)).

No finiteness assumption on LLL, isometry condition on MMM, or normalization condition is imposed. If VVV is empty, the inverse-square-root factor is zero under total inversion, and the resulting vector is zero.

QAlgorithms.Papers.Independent.Intakenext100.P95.entropyV

For finite types L,VL,VL,V, both with decidable equality, any complex vector ψ\psiψ indexed by configurations L→VL\to VL→V, and any finite subset A⊆LA\subseteq LA⊆L, define the matrix

σA(a,a′)=∑b:(L∖A)→Vψ(merge⁡A(a,b))ψ(merge⁡A(a′,b))‾,\sigma_A(a,a') = \sum_{b:(L\setminus A)\to V} \psi\bigl(\operatorname{merge}_A(a,b)\bigr) \overline{\psi\bigl(\operatorname{merge}_A(a',b)\bigr)},σA​(a,a′)=b:(L∖A)→V∑​ψ(mergeA​(a,b))ψ(mergeA​(a′,b))​,

where merging uses aaa or a′a'a′ on AAA and bbb outside it. The quantity defined here is

entropyV⁡(ψ,A)=−Re⁡tr⁡(f(σA))log⁡2∣V∣,f(t)=tlog⁡2t,\operatorname{entropyV}(\psi,A) = \frac{-\operatorname{Re}\operatorname{tr}\bigl(f(\sigma_A)\bigr)} {\log_2|V|}, \qquad f(t)=t\log_2t,entropyV(ψ,A)=log2​∣V∣−Retr(f(σA​))​,f(t)=tlog2​t,

where f(σA)f(\sigma_A)f(σA​) is obtained through continuous functional calculus. No normalization of ψ\psiψ is required. The logarithm and division use their total real-valued conventions: log⁡20=0\log_2 0=0log2​0=0, and division by zero is zero, so this quantity is zero when ∣V∣=0|V|=0∣V∣=0 or ∣V∣=1|V|=1∣V∣=1.

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveCode

This defines the complex linear subspace of vectors indexed by five-bit strings consisting exactly of those ψ\psiψ satisfying Gjψ=ψG_j\psi=\psiGj​ψ=ψ for every j=0,1,2,3j=0,1,2,3j=0,1,2,3, where

(G0,G1,G2,G3)=(X⊗Z⊗Z⊗X⊗I2,  I2⊗X⊗Z⊗Z⊗X,  X⊗I2⊗X⊗Z⊗Z,  Z⊗X⊗I2⊗X⊗Z).(G_0,G_1,G_2,G_3)= (X\otimes Z\otimes Z\otimes X\otimes I_2,\; I_2\otimes X\otimes Z\otimes Z\otimes X,\; X\otimes I_2\otimes X\otimes Z\otimes Z,\; Z\otimes X\otimes I_2\otimes X\otimes Z).(G0​,G1​,G2​,G3​)=(X⊗Z⊗Z⊗X⊗I2​,I2​⊗X⊗Z⊗Z⊗X,X⊗I2​⊗X⊗Z⊗Z,Z⊗X⊗I2​⊗X⊗Z).

Here I2I_2I2​ is the single-bit identity, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), in the basis false, true; matrix action is ordinary matrix-vector multiplication.

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveEncoder

This defines a complex matrix MMM whose rows are indexed by five-bit strings zzz and whose columns are indexed by a Boolean bbb, with

M(z,false)=4(Pe00000)(z),M(z,true)=4(X⊗5Pe00000)(z).M(z,\mathrm{false})=4(Pe_{00000})(z),\qquad M(z,\mathrm{true})=4(X^{\otimes5}Pe_{00000})(z).M(z,false)=4(Pe00000​)(z),M(z,true)=4(X⊗5Pe00000​)(z).

Here e00000e_{00000}e00000​ has amplitude one at the all-false string and zero elsewhere, P=I32+G02I32+G12I32+G22I32+G32P=\frac{I_{32}+G_0}{2}\frac{I_{32}+G_1}{2}\frac{I_{32}+G_2}{2}\frac{I_{32}+G_3}{2}P=2I32​+G0​​2I32​+G1​​2I32​+G2​​2I32​+G3​​, and (G0,G1,G2,G3)=(X⊗Z⊗Z⊗X⊗I2, I2⊗X⊗Z⊗Z⊗X, X⊗I2⊗X⊗Z⊗Z, Z⊗X⊗I2⊗X⊗Z)(G_0,G_1,G_2,G_3)=(X\otimes Z\otimes Z\otimes X\otimes I_2,\ I_2\otimes X\otimes Z\otimes Z\otimes X,\ X\otimes I_2\otimes X\otimes Z\otimes Z,\ Z\otimes X\otimes I_2\otimes X\otimes Z)(G0​,G1​,G2​,G3​)=(X⊗Z⊗Z⊗X⊗I2​, I2​⊗X⊗Z⊗Z⊗X, X⊗I2​⊗X⊗Z⊗Z, Z⊗X⊗I2​⊗X⊗Z). The matrices I32I_{32}I32​ and I2I_2I2​ are identities, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), with single-bit basis order false, true.

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveGenerator

For every j∈{0,1,2,3}j\in\{0,1,2,3\}j∈{0,1,2,3}, this defines a complex matrix GjG_jGj​ with rows and columns indexed by five-bit strings. With the single-bit basis ordered as false, true, let I2I_2I2​ be the identity, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1). The four matrices, in order, are

G0=X⊗Z⊗Z⊗X⊗I2,G1=I2⊗X⊗Z⊗Z⊗X,G2=X⊗I2⊗X⊗Z⊗Z,G3=Z⊗X⊗I2⊗X⊗Z.G_0=X\otimes Z\otimes Z\otimes X\otimes I_2,\quad G_1=I_2\otimes X\otimes Z\otimes Z\otimes X,\quad G_2=X\otimes I_2\otimes X\otimes Z\otimes Z,\quad G_3=Z\otimes X\otimes I_2\otimes X\otimes Z.G0​=X⊗Z⊗Z⊗X⊗I2​,G1​=I2​⊗X⊗Z⊗Z⊗X,G2​=X⊗I2​⊗X⊗Z⊗Z,G3​=Z⊗X⊗I2​⊗X⊗Z.

Each tensor product has entry equal to the product of its five single-bit matrix entries, with no additional phase factor.

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveLogicalOne

This defines the vector v1=4X⊗5Pe00000v_1=4X^{\otimes5}Pe_{00000}v1​=4X⊗5Pe00000​, where e00000e_{00000}e00000​ is the vector supported at the all-false five-bit string with amplitude one, and

P=I32+G02I32+G12I32+G22I32+G32.P=\frac{I_{32}+G_0}{2}\frac{I_{32}+G_1}{2}\frac{I_{32}+G_2}{2}\frac{I_{32}+G_3}{2}.P=2I32​+G0​​2I32​+G1​​2I32​+G2​​2I32​+G3​​.

Here (G0,G1,G2,G3)=(X⊗Z⊗Z⊗X⊗I2, I2⊗X⊗Z⊗Z⊗X, X⊗I2⊗X⊗Z⊗Z, Z⊗X⊗I2⊗X⊗Z)(G_0,G_1,G_2,G_3)=(X\otimes Z\otimes Z\otimes X\otimes I_2,\ I_2\otimes X\otimes Z\otimes Z\otimes X,\ X\otimes I_2\otimes X\otimes Z\otimes Z,\ Z\otimes X\otimes I_2\otimes X\otimes Z)(G0​,G1​,G2​,G3​)=(X⊗Z⊗Z⊗X⊗I2​, I2​⊗X⊗Z⊗Z⊗X, X⊗I2​⊗X⊗Z⊗Z, Z⊗X⊗I2​⊗X⊗Z), I32I_{32}I32​ and I2I_2I2​ are the respective identities, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1) in the basis false, true. Thus X⊗5X^{\otimes5}X⊗5 flips all five bits when acting on a vector.

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveLogicalZero

This defines the vector v0=4Pe00000v_0=4Pe_{00000}v0​=4Pe00000​ in the complex Euclidean space indexed by five-bit strings, where e00000e_{00000}e00000​ has amplitude one at the all-false string and zero elsewhere, and

P=I32+G02I32+G12I32+G22I32+G32.P=\frac{I_{32}+G_0}{2}\frac{I_{32}+G_1}{2}\frac{I_{32}+G_2}{2}\frac{I_{32}+G_3}{2}.P=2I32​+G0​​2I32​+G1​​2I32​+G2​​2I32​+G3​​.

The ordered tuple of matrices is (G0,G1,G2,G3)=(X⊗Z⊗Z⊗X⊗I2, I2⊗X⊗Z⊗Z⊗X, X⊗I2⊗X⊗Z⊗Z, Z⊗X⊗I2⊗X⊗Z)(G_0,G_1,G_2,G_3)=(X\otimes Z\otimes Z\otimes X\otimes I_2,\ I_2\otimes X\otimes Z\otimes Z\otimes X,\ X\otimes I_2\otimes X\otimes Z\otimes Z,\ Z\otimes X\otimes I_2\otimes X\otimes Z)(G0​,G1​,G2​,G3​)=(X⊗Z⊗Z⊗X⊗I2​, I2​⊗X⊗Z⊗Z⊗X, X⊗I2​⊗X⊗Z⊗Z, Z⊗X⊗I2​⊗X⊗Z), where I32I_{32}I32​ and I2I_2I2​ are the respective identity matrices, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1) in the basis false, true.

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveOps

This defines a table of Pauli symbols with four rows indexed by j=0,1,2,3j=0,1,2,3j=0,1,2,3 and five columns indexed by q=0,1,2,3,4q=0,1,2,3,4q=0,1,2,3,4. In column order, its rows are

(X,Z,Z,X,I),(I,X,Z,Z,X),(X,I,X,Z,Z),(Z,X,I,X,Z).(X,Z,Z,X,I),\qquad (I,X,Z,Z,X),\qquad (X,I,X,Z,Z),\qquad (Z,X,I,X,Z).(X,Z,Z,X,I),(I,X,Z,Z,X),(X,I,X,Z,Z),(Z,X,I,X,Z).

QAlgorithms.Papers.Independent.Intakenext100.P95.fiveProjector

This defines the complex matrix on five-bit strings

P=I32+G02 I32+G12 I32+G22 I32+G32,P=\frac{I_{32}+G_0}{2}\, \frac{I_{32}+G_1}{2}\, \frac{I_{32}+G_2}{2}\, \frac{I_{32}+G_3}{2},P=2I32​+G0​​2I32​+G1​​2I32​+G2​​2I32​+G3​​,

with the factors in the displayed order, where (G0,G1,G2,G3)=(X⊗Z⊗Z⊗X⊗I2, I2⊗X⊗Z⊗Z⊗X, X⊗I2⊗X⊗Z⊗Z, Z⊗X⊗I2⊗X⊗Z)(G_0,G_1,G_2,G_3)=(X\otimes Z\otimes Z\otimes X\otimes I_2,\ I_2\otimes X\otimes Z\otimes Z\otimes X,\ X\otimes I_2\otimes X\otimes Z\otimes Z,\ Z\otimes X\otimes I_2\otimes X\otimes Z)(G0​,G1​,G2​,G3​)=(X⊗Z⊗Z⊗X⊗I2​, I2​⊗X⊗Z⊗Z⊗X, X⊗I2​⊗X⊗Z⊗Z, Z⊗X⊗I2​⊗X⊗Z). Here I32I_{32}I32​ is the identity on five-bit strings, I2I_2I2​ is the single-bit identity, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), using false, true as the single-bit basis order.

QAlgorithms.Papers.Independent.Intakenext100.P95.flatten

For a finite type LLL with decidable equality, an arbitrary type VVV, a complex vector TTT indexed by functions L→VL\to VL→V, and a finite subset A⊆LA\subseteq LA⊆L, the flattening of TTT along AAA is the complex matrix whose rows are configurations b:Ac→Vb:A^c\to Vb:Ac→V and whose columns are configurations a:A→Va:A\to Va:A→V, with entries

FA(b,a)=T(x),x(i)={a(i),i∈A,b(i),i∉A.F_A(b,a)=T(x),\qquad x(i)= \begin{cases} a(i),&i\in A,\\ b(i),&i\notin A. \end{cases}FA​(b,a)=T(x),x(i)={a(i),b(i),​i∈A,i∈/A.​

Here Ac=L∖AA^c=L\setminus AAc=L∖A; neither finiteness of VVV nor normalization of TTT is assumed. An empty subset has a singleton configuration set, so A=∅A=\varnothingA=∅ gives one column and A=LA=LA=L gives one row.

QAlgorithms.Papers.Independent.Intakenext100.P95.fourQutritState

This defines a vector Φ\PhiΦ in the complex Euclidean space indexed by quadruples y∈(Z/3Z)4y\in(\mathbb Z/3\mathbb Z)^4y∈(Z/3Z)4, with coordinates

Φ(y)={1/3,y1=y0+y3 and y2=y0+2y3,0,otherwise.\Phi(y)= \begin{cases} 1/3,&y_1=y_0+y_3\text{ and }y_2=y_0+2y_3,\\ 0,&\text{otherwise}. \end{cases}Φ(y)={1/3,0,​y1​=y0​+y3​ and y2​=y0​+2y3​,otherwise.​

All coordinate arithmetic is modulo 333; equivalently,

Φ=13∑t,l∈Z/3Z∣t,t+l,t+2l,l⟩.\Phi=\frac13\sum_{t,l\in\mathbb Z/3\mathbb Z}|t,t+l,t+2l,l\rangle.Φ=31​t,l∈Z/3Z∑​∣t,t+l,t+2l,l⟩.

QAlgorithms.Papers.Independent.Intakenext100.P95.logicalSupportDimension

For every natural number nnn, every F2\mathbb F_2F2​-linear subspace S⊆Vn=F2n×F2nS\subseteq V_n=\mathbb F_2^n\times\mathbb F_2^nS⊆Vn​=F2n​×F2n​, and every finite subset A⊆{0,…,n−1}A\subseteq\{0,\ldots,n-1\}A⊆{0,…,n−1}, this definition gives the natural number

dim⁡F2qS(N(S)∩HA),\dim_{\mathbb F_2}q_S\bigl(N(S)\cap H_A\bigr),dimF2​​qS​(N(S)∩HA​),

where qS:Vn→Vn/Sq_S:V_n\to V_n/SqS​:Vn​→Vn​/S is the quotient map z↦z+Sz\mapsto z+Sz↦z+S, N(S)N(S)N(S) is the F2\mathbb F_2F2​-linear span of all (u,v)(u,v)(u,v) satisfying ∑jujsj+∑jvjrj=0\sum_j u_js_j+\sum_j v_jr_j=0∑j​uj​sj​+∑j​vj​rj​=0 for every (r,s)∈S(r,s)\in S(r,s)∈S, and HAH_AHA​ is the F2\mathbb F_2F2​-linear span of all (u,v)(u,v)(u,v) whose two coordinates vanish at every index outside AAA. All sums in the pairing are in F2=Z/2Z\mathbb F_2=\mathbb Z/2\mathbb ZF2​=Z/2Z. The dimension is taken of the image subspace in Vn/SV_n/SVn​/S; no isotropy assumption on SSS is part of this definition. If AAA is empty, including when n=0n=0n=0, this dimension is 000.

QAlgorithms.Papers.Independent.Intakenext100.P95.mergeSubset

For a finite type LLL with decidable equality, an arbitrary type VVV, a finite subset A⊆LA\subseteq LA⊆L, and configurations a:A→Va:A\to Va:A→V and b:Ac→Vb:A^c\to Vb:Ac→V, where Ac=L∖AA^c=L\setminus AAc=L∖A, their merged configuration is the function L→VL\to VL→V given by

merge⁡A(a,b)(i)={a(i),i∈A,b(i),i∉A.\operatorname{merge}_A(a,b)(i)= \begin{cases} a(i),&i\in A,\\ b(i),&i\notin A. \end{cases}mergeA​(a,b)(i)={a(i),b(i),​i∈A,i∈/A.​

This includes A=∅A=\varnothingA=∅ and A=LA=LA=L, when the merged function is determined entirely by bbb and aaa, respectively.

QAlgorithms.Papers.Independent.Intakenext100.P95.moveInput

For arbitrary types A1,A2,BA_1,A_2,BA1​,A2​,B and a complex matrix TTT with rows indexed by BBB and columns indexed by A2×A1A_2\times A_1A2​×A1​, moving the A2A_2A2​ input index produces the matrix with rows indexed by B×A2B\times A_2B×A2​ and columns indexed by A1A_1A1​, defined by

moveInput⁡(T)((b,a2),a1)=T(b,(a2,a1)).\operatorname{moveInput}(T)\bigl((b,a_2),a_1\bigr)=T\bigl(b,(a_2,a_1)\bigr).moveInput(T)((b,a2​),a1​)=T(b,(a2​,a1​)).

There are no finiteness or nonemptiness assumptions; this definition only rearranges the indices.

QAlgorithms.Papers.Independent.Intakenext100.P95.normalizerSpace

For every natural number nnn and every F2\mathbb F_2F2​-linear subspace SSS of Vn=F2n×F2nV_n=\mathbb F_2^n\times\mathbb F_2^nVn​=F2n​×F2n​, this definition gives the subspace

N(S)=span⁡F2{(u,v)∈Vn:∀(r,s)∈S, ∑j=0n−1ujsj+∑j=0n−1vjrj=0}.N(S)=\operatorname{span}_{\mathbb F_2} \left\{(u,v)\in V_n: \forall (r,s)\in S,\ \sum_{j=0}^{n-1}u_js_j+\sum_{j=0}^{n-1}v_jr_j=0 \right\}.N(S)=spanF2​​{(u,v)∈Vn​:∀(r,s)∈S, j=0∑n−1​uj​sj​+j=0∑n−1​vj​rj​=0}.

The displayed sums and equality are in F2\mathbb F_2F2​. No condition on pairings between elements of SSS is imposed. The definition includes n=0n=0n=0, when the sums are empty and N(S)N(S)N(S) is the zero subspace of the zero-dimensional space V0V_0V0​.

QAlgorithms.Papers.Independent.Intakenext100.P95.qutritCSSSpace

This defines a complex linear subspace of C(Z/3Z)4\mathbb C^{(\mathbb Z/3\mathbb Z)^4}C(Z/3Z)4. Put c0=(1,1,1,0)c_0=(1,1,1,0)c0​=(1,1,1,0), c1=(1,−1,0,1)c_1=(1,-1,0,1)c1​=(1,−1,0,1), and ω=e2πi/3\omega=e^{2\pi i/3}ω=e2πi/3. The subspace consists exactly of the vectors ψ\psiψ such that, for both j=0,1j=0,1j=0,1 and every y∈(Z/3Z)4y\in(\mathbb Z/3\mathbb Z)^4y∈(Z/3Z)4,

ψ(y+cj)=ψ(y),ω rep⁡(∑i=03(cj)iyi)ψ(y)=ψ(y).\psi(y+c_j)=\psi(y), \qquad \omega^{\,\operatorname{rep}(\sum_{i=0}^{3}(c_j)_i y_i)}\psi(y)=\psi(y).ψ(y+cj​)=ψ(y),ωrep(∑i=03​(cj​)i​yi​)ψ(y)=ψ(y).

Here addition and the sum in the exponent are modulo 333, and rep⁡\operatorname{rep}rep is the representative in {0,1,2}\{0,1,2\}{0,1,2}. Thus the definition takes the intersection of the fixed spaces of the two translation matrices with entries 111 when y=x−cjy=x-c_jy=x−cj​ and zero otherwise, and the two diagonal matrices with diagonal entries ωrep⁡(∑i(cj)iyi)\omega^{\operatorname{rep}(\sum_i(c_j)_iy_i)}ωrep(∑i​(cj​)i​yi​).

QAlgorithms.Papers.Independent.Intakenext100.P95.qutritChecks

This defines two four-coordinate vectors over Z/3Z\mathbb Z/3\mathbb ZZ/3Z, indexed by j=0,1j=0,1j=0,1, as

c0=(1,1,1,0),c1=(1,−1,0,1)=(1,2,0,1).c_0=(1,1,1,0),\qquad c_1=(1,-1,0,1)=(1,2,0,1).c0​=(1,1,1,0),c1​=(1,−1,0,1)=(1,2,0,1).

The coordinates in each vector are indexed by 0,1,2,30,1,2,30,1,2,3, and −1-1−1 denotes the residue class 222 modulo 333.

QAlgorithms.Papers.Independent.Intakenext100.P95.qutritCircuit

This defines a complex matrix QQQ with rows and columns indexed by pairs of trits y,x∈(Z/3Z)2y,x\in(\mathbb Z/3\mathbb Z)^2y,x∈(Z/3Z)2, by

Qy,x={1,y0=2x0+x1 and y1=x0+x1,0,otherwise,Q_{y,x}= \begin{cases} 1,&y_0=2x_0+x_1\text{ and }y_1=x_0+x_1,\\ 0,&\text{otherwise}, \end{cases}Qy,x​={1,0,​y0​=2x0​+x1​ and y1​=x0​+x1​,otherwise,​

where all arithmetic is modulo 333. Equivalently, its column indexed by (x0,x1)(x_0,x_1)(x0​,x1​) is the coordinate unit vector at (2x0+x1,x0+x1)(2x_0+x_1,x_0+x_1)(2x0​+x1​,x0​+x1​).

QAlgorithms.Papers.Independent.Intakenext100.P95.qutritEncoder

This defines a complex matrix EEE with rows indexed by triples y=(y0,y1,y2)∈(Z/3Z)3y=(y_0,y_1,y_2)\in(\mathbb Z/3\mathbb Z)^3y=(y0​,y1​,y2​)∈(Z/3Z)3 and columns indexed by l∈Z/3Zl\in\mathbb Z/3\mathbb Zl∈Z/3Z, by

Ey,l={1/3,y1=y0+l and y2=y0+2l,0,otherwise.E_{y,l}= \begin{cases} 1/\sqrt3,&y_1=y_0+l\text{ and }y_2=y_0+2l,\\ 0,&\text{otherwise}. \end{cases}Ey,l​={1/3​,0,​y1​=y0​+l and y2​=y0​+2l,otherwise.​

The coordinate equations are modulo 333; equivalently, the column indexed by lll is 13∑t∈Z/3Z∣t,t+l,t+2l⟩\frac1{\sqrt3}\sum_{t\in\mathbb Z/3\mathbb Z}|t,t+l,t+2l\rangle3​1​∑t∈Z/3Z​∣t,t+l,t+2l⟩.

QAlgorithms.Papers.Independent.Intakenext100.P95.qutritWeyl

For every natural number mmm, including m=0m=0m=0, and every pair a,b∈(Z/3Z)ma,b\in(\mathbb Z/3\mathbb Z)^ma,b∈(Z/3Z)m, this defines a complex matrix Wm(a,b)W_m(a,b)Wm​(a,b) whose rows and columns are indexed by mmm-tuples of trits. With ω=e2πi/3\omega=e^{2\pi i/3}ω=e2πi/3, its entries are

Wm(a,b)y,x={ω rep⁡(∑i=0m−1bixi),yi=xi−ai for every i,0,otherwise,W_m(a,b)_{y,x}= \begin{cases} \omega^{\,\operatorname{rep}(\sum_{i=0}^{m-1}b_i x_i)},& y_i=x_i-a_i\text{ for every }i,\\ 0,&\text{otherwise}, \end{cases}Wm​(a,b)y,x​={ωrep(∑i=0m−1​bi​xi​),0,​yi​=xi​−ai​ for every i,otherwise,​

where the sum and coordinate equations are in Z/3Z\mathbb Z/3\mathbb ZZ/3Z, and rep⁡\operatorname{rep}rep takes the representative in {0,1,2}\{0,1,2\}{0,1,2}. For m=0m=0m=0, there is one empty tuple, the condition is vacuous, the sum is zero, and the resulting 1×11\times11×1 matrix has entry 111.

QAlgorithms.Papers.Independent.Intakenext100.P95.sixGenerator

For each integer j∈{0,…,5}j\in\{0,\ldots,5\}j∈{0,…,5}, this defines a complex matrix GjG_jGj​ on six-bit strings. Writing I,X,Y,ZI,X,Y,ZI,X,Y,Z for the identity and the standard Pauli matrices, with tensor factors ordered by bit positions 0,…,50,\ldots,50,…,5, the six matrices are

G0=X⊗Z⊗Z⊗X⊗I⊗I,G1=I⊗X⊗Z⊗Z⊗X⊗I,G2=X⊗I⊗X⊗Z⊗Z⊗I,G3=Z⊗X⊗I⊗X⊗Z⊗I,G4=X⊗6,G5=Z⊗6.\begin{aligned} G_0&=X\otimes Z\otimes Z\otimes X\otimes I\otimes I,\\ G_1&=I\otimes X\otimes Z\otimes Z\otimes X\otimes I,\\ G_2&=X\otimes I\otimes X\otimes Z\otimes Z\otimes I,\\ G_3&=Z\otimes X\otimes I\otimes X\otimes Z\otimes I,\\ G_4&=X^{\otimes6},\\ G_5&=Z^{\otimes6}. \end{aligned}G0​G1​G2​G3​G4​G5​​=X⊗Z⊗Z⊗X⊗I⊗I,=I⊗X⊗Z⊗Z⊗X⊗I,=X⊗I⊗X⊗Z⊗Z⊗I,=Z⊗X⊗I⊗X⊗Z⊗I,=X⊗6,=Z⊗6.​

Each tensor product has matrix entry equal to the product of its six single-bit matrix entries, with no additional phase.

QAlgorithms.Papers.Independent.Intakenext100.P95.sixQubitState

This defines a complex Euclidean vector Ψ\PsiΨ indexed by six-bit strings. For such a string zzz, let x=(z0,z1,z2,z3,z4)x=(z_0,z_1,z_2,z_3,z_4)x=(z0​,z1​,z2​,z3​,z4​) and let b=z5b=z_5b=z5​. Its amplitude is

Ψ(z)={42(Pe00000)(x),b=false,42(X⊗5Pe00000)(x),b=true.\Psi(z)= \begin{cases} \dfrac{4}{\sqrt2}(Pe_{00000})(x),&b=\mathrm{false},\\[2pt] \dfrac{4}{\sqrt2}(X^{\otimes5}Pe_{00000})(x),&b=\mathrm{true}. \end{cases}Ψ(z)=⎩⎨⎧​2​4​(Pe00000​)(x),2​4​(X⊗5Pe00000​)(x),​b=false,b=true.​

Here e00000e_{00000}e00000​ has amplitude one at the all-false five-bit string and zero elsewhere, P=I32+G02I32+G12I32+G22I32+G32P=\frac{I_{32}+G_0}{2}\frac{I_{32}+G_1}{2}\frac{I_{32}+G_2}{2}\frac{I_{32}+G_3}{2}P=2I32​+G0​​2I32​+G1​​2I32​+G2​​2I32​+G3​​, and (G0,G1,G2,G3)=(X⊗Z⊗Z⊗X⊗I2, I2⊗X⊗Z⊗Z⊗X, X⊗I2⊗X⊗Z⊗Z, Z⊗X⊗I2⊗X⊗Z)(G_0,G_1,G_2,G_3)=(X\otimes Z\otimes Z\otimes X\otimes I_2,\ I_2\otimes X\otimes Z\otimes Z\otimes X,\ X\otimes I_2\otimes X\otimes Z\otimes Z,\ Z\otimes X\otimes I_2\otimes X\otimes Z)(G0​,G1​,G2​,G3​)=(X⊗Z⊗Z⊗X⊗I2​, I2​⊗X⊗Z⊗Z⊗X, X⊗I2​⊗X⊗Z⊗Z, Z⊗X⊗I2​⊗X⊗Z). The matrices I32I_{32}I32​ and I2I_2I2​ are identities, X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​), and Z=diag⁡(1,−1)Z=\operatorname{diag}(1,-1)Z=diag(1,−1), using false, true as the single-bit basis order.

QAlgorithms.Papers.Independent.Intakenext100.P95.subsetDensity

For finite types L,VL,VL,V, with decidable equality on LLL, a finite subset A⊆LA\subseteq LA⊆L, and any complex matrix ρ\rhoρ indexed by configurations L→VL\to VL→V, this definition gives the matrix indexed by configurations a,a′:A→Va,a':A\to Va,a′:A→V with entries

ρA(a,a′)=∑b:(L∖A)→Vρ(merge⁡A(a,b),merge⁡A(a′,b)),\rho_A(a,a') = \sum_{b:(L\setminus A)\to V} \rho\bigl(\operatorname{merge}_A(a,b),\operatorname{merge}_A(a',b)\bigr),ρA​(a,a′)=b:(L∖A)→V∑​ρ(mergeA​(a,b),mergeA​(a′,b)),

where each merged configuration uses its first argument on AAA and bbb outside AAA. No positivity, Hermiticity, or trace condition on ρ\rhoρ is assumed. For A=∅A=\varnothingA=∅, this is a one-by-one matrix whose entry is tr⁡ρ\operatorname{tr}\rhotrρ; for A=LA=LA=L, it is ρ\rhoρ with its indices restricted to the equivalent configuration type on LLL.

QAlgorithms.Papers.Independent.Intakenext100.P95.supportSpace

For every natural number nnn and every finite subset A⊆{0,…,n−1}A\subseteq\{0,\ldots,n-1\}A⊆{0,…,n−1}, this definition gives the subspace

HA=span⁡F2{(u,v)∈F2n×F2n:∀j∉A, uj=0 and vj=0},F2=Z/2Z.H_A=\operatorname{span}_{\mathbb F_2} \left\{(u,v)\in\mathbb F_2^n\times\mathbb F_2^n: \forall j\notin A,\ u_j=0\ \text{and}\ v_j=0 \right\}, \qquad \mathbb F_2=\mathbb Z/2\mathbb Z.HA​=spanF2​​{(u,v)∈F2n​×F2n​:∀j∈/A, uj​=0 and vj​=0},F2​=Z/2Z.

Thus the spanning vectors have both coordinates zero outside AAA. The empty set is allowed and gives H∅={0}H_\varnothing=\{0\}H∅​={0}; taking AAA to be the entire index set gives the whole space. For n=0n=0n=0, that whole space is zero-dimensional.

QAlgorithms.Papers.Independent.Intakenext100.P95.tripartiteInfo

For finite types L,VL,VL,V, both with decidable equality, any complex vector ψ\psiψ indexed by configurations L→VL\to VL→V, and any finite subsets A,B,C⊆LA,B,C\subseteq LA,B,C⊆L, this quantity is

Sψ(A)+Sψ(B)+Sψ(C)−Sψ(A∪B)−Sψ(A∪C)−Sψ(B∪C)+Sψ(A∪B∪C).S_\psi(A)+S_\psi(B)+S_\psi(C) -S_\psi(A\cup B)-S_\psi(A\cup C)-S_\psi(B\cup C) +S_\psi(A\cup B\cup C).Sψ​(A)+Sψ​(B)+Sψ​(C)−Sψ​(A∪B)−Sψ​(A∪C)−Sψ​(B∪C)+Sψ​(A∪B∪C).

For each subset D⊆LD\subseteq LD⊆L, the notation here means

Sψ(D)=−Re⁡tr⁡(f(σD))log⁡2∣V∣,f(t)=tlog⁡2t,σD(a,a′)=∑b:(L∖D)→Vψ(a∪b)ψ(a′∪b)‾,S_\psi(D)= \frac{-\operatorname{Re}\operatorname{tr}\bigl(f(\sigma_D)\bigr)} {\log_2|V|}, \qquad f(t)=t\log_2t,\qquad \sigma_D(a,a')= \sum_{b:(L\setminus D)\to V} \psi(a\cup b)\overline{\psi(a'\cup b)},Sψ​(D)=log2​∣V∣−Retr(f(σD​))​,f(t)=tlog2​t,σD​(a,a′)=b:(L∖D)→V∑​ψ(a∪b)ψ(a′∪b)​,

where a,a′:D→Va,a':D\to Va,a′:D→V, a∪ba\cup ba∪b denotes the function using aaa on DDD and bbb outside DDD, and f(σD)f(\sigma_D)f(σD​) uses continuous functional calculus. The vector need not be normalized, and A,B,CA,B,CA,B,C need not be disjoint or nonempty. Total logarithm and division conventions make the entire quantity zero when ∣V∣=0|V|=0∣V∣=0 or 111.

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