Definitions for Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
DefinitionQAlgorithms_Papers_Independent_Support50_P30The objects the formalized statements of Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks (arXiv:2210.09974) are stated in. Each was checked against the paper by a blind read-back and a moderator.
QnnOperatorQnnDensityqubitPermutationMatrix: PDF p.4, Eq.(8): inverse permutation on tensor positions.PermutationEquivariant: PDF pp.3-4: the commutant of the actual permutation action.unitaryFamily: PDF p.15: the full commuting unitary family, including block phases.pauliString: PDF pp.4,27: place a fixed Pauli on each site of a subset.collective: PDF p.29, Eq.(61): sum over each k-element subset once.qnnGenerator: PDF p.4, Eq.(9); used only for n at least two.qnnMeasurementFamily: PDF p.4, Eq.(10), with an unscaled n-body product.qnnLayer: PDF p.2, Eq.(1): exp(-i t H).circuit: PDF p.2, Eq.(1): the last layer acts on the left.circuitHalf: PDF p.23, Eq.(18): false gives U_A; true gives U_B, including mu.qnnLoss: PDF p.2, Eq.(2): real Hermitian expectation.dataOperator: PDF pp.2,6: arbitrary real weights; sigma need not be a density matrix.empiricalLoss: PDF p.2, Eq.(3).partialLoss: PDF pp.6,23: actual coordinate derivative of the empirical loss.SectorblockDim: PDF p.4, Eq.(12): dimension of the U(2) block.qnnSectorMultiplicity: PDF p.4, Eq.(12): number of copies, with the predecessor zero at m=0.QnnSchurIndexqnnSchurBlockDiagonal: PDF p.4, Eq.(13): identical blocks in all multiplicity copies.spinCasimir: PDF pp.13,28: four times the total-spin Casimir.SchurFrame: PDF pp.4,6,23,28: fixed orthonormal Schur coordinates. The commutant condition specifies Schur coordinates, without assuming variance or spectra. The Casimir pins spin (n-2m)/2, preventing sector relabelling.rowMap: PDF p.23, Eq.(10): row coisometry for a copy.schurCompression: PDF p.6, Eq.(15): unnormalized compression.aggregate: PDF p.6, Eq.(16): sum of data compressions, not their average.commonBlock: PDF p.4, Eq.(13): the common equivariant block; averaging identical copies avoids a distinguished copy. Data use aggregate instead.deltaPair: PDF p.26, Eq.(38): centered trace pairing, real on Hermitian inputs.centeredDelta: PDF p.6: unnormalized centered squared Hilbert-Schmidt statistic.DesignKeyconjugationMonomial: Balanced entry monomial of conjugation degree r.IndependentBlockTwoDesign: PDF pp.14,24-26: joint exact conjugation 2-design moments for both halves and all blocks, including cross-sector products. No depth-convergence claim.variance: PDF p.24, Eq.(23): variance. Used on bounded measurable circuit losses.tangentCommutant: PDF pp.5,22: real tangent commutant, including the scalar phase direction.stateDerivative: PDF p.9: derivative of the actual output state.qfi: PDF p.9: pure-state QFIM, removing the global phase direction.qnnPopulationRisk: PDF pp.3,15: a is the composed measurable label weight a(f(rho)).empiricalRisk: PDF pp.2-3,15: empirical coefficients a(f(rho_i))/M.generalizationEvent: PDF pp.7,15: one event controls every possible trained unitary.dynamicalLie: PDF p.13, Definition 5: use -i times Hermitian generators, as Eq.(1) requires. This is the actual Lie closure rather than the whole commutant.krawtchouk: PDF p.29, Eq.(62): binary Krawtchouk value in signed real arithmetic.symmetricSector: PDF pp.4,29: the symmetric spin sector.haarQubitUnitary: PDF pp.15,31: transfer Haar U(2^n) to the fixed bit ordering.haarPureInput: PDF p.31: one seed fixed before Haar V.classifierFamily: PDF pp.32-33: a fixed architecture and real threshold.uniformParameters: PDF pp.13,33-34: uniform sampling of the parameter box.InversePolynomialLower: PDF p.34, Eq.(96): eventual inverse-polynomial lower bound.HasNarrowGorge: PDF pp.33-34: below-mean point condition AND exponential tail envelope, with constants before size and tail threshold.
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Gates
import Definitions.Def_QAlgorithms_Defs_Information
import Definitions.Def_QAlgorithms_Defs_PACSampleComplexity
import Definitions.Def_QAlgorithms_Defs_SchurUnitaryEnsembles
/-! Statements from arXiv:2210.09974v3. All citations are PDF pages.
Schur coordinates are fixed before data and parameters. No state compression
is renormalized. Local definitions belong to this paper only. -/
noncomputable section
open MeasureTheory
open scoped BigOperators ComplexConjugate Matrix.Norms.L2Operator NNReal ENNReal
namespace QAlgorithms.Papers.Independent.Support50.P30
abbrev QnnOperator (n : ℕ) := Matrix (Qubits n) (Qubits n) ℂ
abbrev QnnDensity (n : ℕ) := {rho : QnnOperator n // IsDensityMatrix rho}
instance densityMeasurable (n : ℕ) : MeasurableSpace (QnnDensity n) := borel _
instance densityBorel (n : ℕ) : BorelSpace (QnnDensity n) := ⟨rfl⟩
/-- PDF p.4, Eq.(8): inverse permutation on tensor positions. -/
def qubitPermutationMatrix (n : ℕ) (p : Equiv.Perm (Fin n)) : QnnOperator n :=
fun x y => if x = (fun j => y (p.symm j)) then 1 else 0
/-- PDF pp.3-4: the commutant of the actual permutation action. -/
def PermutationEquivariant {n : ℕ} (A : QnnOperator n) : Prop :=
∀ p : Equiv.Perm (Fin n), A * qubitPermutationMatrix n p = qubitPermutationMatrix n p * A
/-- PDF p.15: the full commuting unitary family, including block phases. -/
def unitaryFamily (n : ℕ) : Set (QnnOperator n) :=
{U | U ∈ Matrix.unitaryGroup (Qubits n) ℂ ∧ PermutationEquivariant U}
/-- PDF pp.4,27: place a fixed Pauli on each site of a subset. -/
def pauliString (n : ℕ) (chi : Matrix Bool Bool ℂ) (s : Finset (Fin n)) : QnnOperator n :=
fun x y => ∏ j : Fin n, if j ∈ s then chi (x j) (y j) else if x j = y j then 1 else 0
/-- PDF p.29, Eq.(61): sum over each k-element subset once. -/
def collective (n : ℕ) (chi : Matrix Bool Bool ℂ) (k : ℕ) : QnnOperator n :=
∑ s ∈ (Finset.univ : Finset (Fin n)).powersetCard k, pauliString n chi s
/-- PDF p.4, Eq.(9); used only for n at least two. -/
def qnnGenerator (n : ℕ) (j : Fin 3) : QnnOperator n :=
if j.val = 0 then (1 / (n : ℂ)) • collective n pauliX 1
else if j.val = 1 then (1 / (n : ℂ)) • collective n pauliY 1
else (2 / ((n : ℂ) * ((n : ℂ) - 1))) • collective n pauliZ 2
/-- PDF p.4, Eq.(10), with an unscaled n-body product. -/
def qnnMeasurementFamily (n : ℕ) : Set (QnnOperator n) :=
{O | ∃ chi ∈ ({pauliX, pauliY, pauliZ} : Set (Matrix Bool Bool ℂ)),
O = (1 / (n : ℂ)) • collective n chi 1 ∨
O = (2 / ((n : ℂ) * ((n : ℂ) - 1))) • collective n chi 2 ∨
O = collective n chi n}
/-- PDF p.2, Eq.(1): exp(-i t H). -/
def qnnLayer {n : ℕ} (H : QnnOperator n) (t : ℝ) : QnnOperator n :=
NormedSpace.exp ((-Complex.I * (t : ℂ)) • H)
/-- PDF p.2, Eq.(1): the last layer acts on the left. -/
def circuit {n L : ℕ} (H : Fin L → QnnOperator n) (theta : Fin L → ℝ) : QnnOperator n :=
orderedProd (fun j => qnnLayer (H j) (theta j))
/-- PDF p.23, Eq.(18): false gives U_A; true gives U_B, including mu. -/
def circuitHalf {n L : ℕ} (H : Fin L → QnnOperator n) (theta : Fin L → ℝ)
(mu : Fin L) (before : Bool) : QnnOperator n :=
let gates := List.ofFn (fun j => qnnLayer (H j) (theta j))
(if before then gates.take (mu.val + 1) else gates.drop (mu.val + 1)).reverse.prod
/-- PDF p.2, Eq.(2): real Hermitian expectation. -/
def qnnLoss {n : ℕ} (U rho O : QnnOperator n) : ℝ := (U * rho * U.conjTranspose * O).trace.re
/-- PDF pp.2,6: arbitrary real weights; sigma need not be a density matrix. -/
def dataOperator {n M : ℕ} (c : Fin M → ℝ) (rho : Fin M → QnnDensity n) : QnnOperator n :=
∑ i, (c i : ℂ) • (rho i).val
/-- PDF p.2, Eq.(3). -/
def empiricalLoss {n L M : ℕ} (H : Fin L → QnnOperator n) (theta : Fin L → ℝ)
(c : Fin M → ℝ) (rho : Fin M → QnnDensity n) (O : QnnOperator n) : ℝ :=
∑ i, c i * qnnLoss (circuit H theta) (rho i).val O
/-- PDF pp.6,23: actual coordinate derivative of the empirical loss. -/
def partialLoss {n L M : ℕ} (H : Fin L → QnnOperator n) (mu : Fin L)
(c : Fin M → ℝ) (rho : Fin M → QnnDensity n) (O : QnnOperator n) (theta : Fin L → ℝ) : ℝ :=
deriv (fun t => empiricalLoss H (Function.update theta mu t) c rho O) (theta mu)
abbrev Sector (n : ℕ) := Fin (n / 2 + 1)
/-- PDF p.4, Eq.(12): dimension of the U(2) block. -/
def blockDim (n : ℕ) (m : Sector n) : ℕ := n - 2 * m.val + 1
/-- PDF p.4, Eq.(12): number of copies, with the predecessor zero at m=0. -/
def qnnSectorMultiplicity (n : ℕ) (m : Sector n) : ℕ :=
n.choose m.val - if m.val = 0 then 0 else n.choose (m.val - 1)
abbrev QnnSchurIndex (n : ℕ) :=
(m : Sector n) × (Fin (qnnSectorMultiplicity n m) × Fin (blockDim n m))
/-- PDF p.4, Eq.(13): identical blocks in all multiplicity copies. -/
def qnnSchurBlockDiagonal {n : ℕ} (B : (m : Sector n) → Matrix (Fin (blockDim n m))
(Fin (blockDim n m)) ℂ) : Matrix (QnnSchurIndex n) (QnnSchurIndex n) ℂ :=
fun x y => if h : x.1 = y.1 then
if x.2.1.val = y.2.1.val then B x.1 x.2.2 (h.symm ▸ y.2.2) else 0 else 0
/-- PDF pp.13,28: four times the total-spin Casimir. -/
def spinCasimir (n : ℕ) : QnnOperator n :=
collective n pauliX 1 ^ 2 + collective n pauliY 1 ^ 2 + collective n pauliZ 1 ^ 2
/-- PDF pp.4,6,23,28: fixed orthonormal Schur coordinates. The commutant
condition specifies Schur coordinates, without assuming variance or spectra.
The Casimir pins spin (n-2m)/2, preventing sector relabelling. -/
structure SchurFrame (n : ℕ) where
matrix : Matrix (QnnSchurIndex n) (Qubits n) ℂ
rows : matrix * matrix.conjTranspose = 1
columns : matrix.conjTranspose * matrix = 1
commutant : ∀ A : QnnOperator n, PermutationEquivariant A →
∃ B : (m : Sector n) → Matrix (Fin (blockDim n m)) (Fin (blockDim n m)) ℂ,
matrix * A * matrix.conjTranspose = qnnSchurBlockDiagonal B
spin : matrix * spinCasimir n * matrix.conjTranspose =
qnnSchurBlockDiagonal (fun m =>
(((n - 2 * m.val : ℕ) : ℂ) * (((n - 2 * m.val : ℕ) : ℂ) + 2)) • 1)
/-- PDF p.23, Eq.(10): row coisometry for a copy. -/
def rowMap {n : ℕ} (S : SchurFrame n) (m : Sector n) (nu : Fin (qnnSectorMultiplicity n m)) :
Matrix (Fin (blockDim n m)) (Qubits n) ℂ :=
fun j x => S.matrix ⟨m, (nu, j)⟩ x
/-- PDF p.6, Eq.(15): unnormalized compression. -/
def schurCompression {n : ℕ} (S : SchurFrame n) (m : Sector n)
(nu : Fin (qnnSectorMultiplicity n m)) (A : QnnOperator n) :
Matrix (Fin (blockDim n m)) (Fin (blockDim n m)) ℂ :=
rowMap S m nu * A * (rowMap S m nu).conjTranspose
/-- PDF p.6, Eq.(16): sum of data compressions, not their average. -/
def aggregate {n : ℕ} (S : SchurFrame n) (m : Sector n) (A : QnnOperator n) :
Matrix (Fin (blockDim n m)) (Fin (blockDim n m)) ℂ :=
∑ nu, schurCompression S m nu A
/-- PDF p.4, Eq.(13): the common equivariant block; averaging identical
copies avoids a distinguished copy. Data use aggregate instead. -/
def commonBlock {n : ℕ} (S : SchurFrame n) (m : Sector n) (A : QnnOperator n) :
Matrix (Fin (blockDim n m)) (Fin (blockDim n m)) ℂ :=
(1 / (qnnSectorMultiplicity n m : ℂ)) • aggregate S m A
/-- PDF p.26, Eq.(38): centered trace pairing, real on Hermitian inputs. -/
def deltaPair {d : ℕ} (A B : Matrix (Fin d) (Fin d) ℂ) : ℝ :=
((A * B).trace - A.trace * B.trace / (d : ℂ)).re
/-- PDF p.6: unnormalized centered squared Hilbert-Schmidt statistic. -/
def centeredDelta {d : ℕ} (A : Matrix (Fin d) (Fin d) ℂ) : ℝ := deltaPair A A
abbrev DesignKey (n : ℕ) := Bool × Sector n
/-- Balanced entry monomial of conjugation degree r. -/
def conjugationMonomial {d : ℕ} (U : Matrix (Fin d) (Fin d) ℂ) (r : ℕ)
(a b c e : Fin r → Fin d) : ℂ :=
(∏ t, U (a t) (b t)) * ∏ t, conj (U (c t) (e t))
/-- PDF pp.14,24-26: joint exact conjugation 2-design moments for both halves
and all blocks, including cross-sector products. No depth-convergence claim. -/
def IndependentBlockTwoDesign {n L : ℕ} (S : SchurFrame n)
(H : Fin L → QnnOperator n) (mu : Fin L) (P : Measure (Fin L → ℝ)) : Prop :=
∀ r : DesignKey n → Fin 3,
∀ a b c e : (k : DesignKey n) → Fin (r k).val → Fin (blockDim n k.2),
(∫ theta, ∏ k : DesignKey n,
conjugationMonomial (commonBlock S k.2 (circuitHalf H theta mu k.1))
(r k).val (a k) (b k) (c k) (e k) ∂P) =
∏ k : DesignKey n, ∫ V : Matrix.unitaryGroup (Fin (blockDim n k.2)) ℂ,
conjugationMonomial V.val (r k).val (a k) (b k) (c k) (e k)
∂(QAlgorithms.Schur.unitaryHaar (blockDim n k.2))
/-- PDF p.24, Eq.(23): variance. Used on bounded measurable circuit losses. -/
def variance {X : Type*} [MeasurableSpace X] (P : Measure X) (f : X → ℝ) : ℝ :=
(∫ x, f x ^ 2 ∂P) - (∫ x, f x ∂P) ^ 2
/-- PDF pp.5,22: real tangent commutant, including the scalar phase direction. -/
def tangentCommutant (n : ℕ) : Submodule ℝ (QnnOperator n) :=
Submodule.span ℝ {A | A.conjTranspose = -A ∧ PermutationEquivariant A}
/-- PDF p.9: derivative of the actual output state. -/
def stateDerivative {n L : ℕ} (H : Fin L → QnnOperator n) (theta : Fin L → ℝ)
(psi : EuclideanSpace ℂ (Qubits n)) (mu : Fin L) : EuclideanSpace ℂ (Qubits n) :=
fderiv ℝ (fun t : Fin L → ℝ => act (circuit H t) psi) theta (Pi.single mu 1)
/-- PDF p.9: pure-state QFIM, removing the global phase direction. -/
def qfi {n L : ℕ} (H : Fin L → QnnOperator n) (theta : Fin L → ℝ)
(psi : EuclideanSpace ℂ (Qubits n)) : Matrix (Fin L) (Fin L) ℝ :=
fun j k => 4 * (inner ℂ (stateDerivative H theta psi j) (stateDerivative H theta psi k) -
inner ℂ (stateDerivative H theta psi j) (act (circuit H theta) psi) *
inner ℂ (act (circuit H theta) psi) (stateDerivative H theta psi k)).re
/-- PDF pp.3,15: a is the composed measurable label weight a(f(rho)). -/
def qnnPopulationRisk {n : ℕ} (P : Measure (QnnDensity n)) (a : QnnDensity n → ℝ)
(O U : QnnOperator n) : ℝ := ∫ rho, a rho * qnnLoss U rho.val O ∂P
/-- PDF pp.2-3,15: empirical coefficients a(f(rho_i))/M. -/
def empiricalRisk {n M : ℕ} (a : QnnDensity n → ℝ) (O U : QnnOperator n)
(xs : Fin M → QnnDensity n) : ℝ :=
(1 / (M : ℝ)) * ∑ i, a (xs i) * qnnLoss U (xs i).val O
/-- PDF pp.7,15: one event controls every possible trained unitary. -/
def generalizationEvent {n M : ℕ} (P : Measure (QnnDensity n)) (a : QnnDensity n → ℝ)
(O : QnnOperator n) (bound : ℝ) : Set (Fin M → QnnDensity n) :=
{xs | ∀ U ∈ unitaryFamily n,
|qnnPopulationRisk P a O U - empiricalRisk a O U xs| ≤ bound}
attribute [local instance] LieRing.ofAssociativeRing
/-- PDF p.13, Definition 5: use -i times Hermitian generators, as Eq.(1)
requires. This is the actual Lie closure rather than the whole commutant. -/
def dynamicalLie (n : ℕ) : LieSubalgebra ℝ (QnnOperator n) :=
LieSubalgebra.lieSpan ℝ (QnnOperator n) (Set.range (fun j : Fin 3 => (-Complex.I) • qnnGenerator n j))
/-- PDF p.29, Eq.(62): binary Krawtchouk value in signed real arithmetic. -/
def krawtchouk (n k w : ℕ) : ℝ :=
∑ l ∈ Finset.range (k + 1), ((n - w).choose (k - l) : ℝ) *
(w.choose l : ℝ) * (-1 : ℝ) ^ l
/-- PDF pp.4,29: the symmetric spin sector. -/
def symmetricSector (n : ℕ) : Sector n := ⟨0, by omega⟩
/-- PDF pp.15,31: transfer Haar U(2^n) to the fixed bit ordering. -/
def haarQubitUnitary {n : ℕ} (V : Matrix.unitaryGroup (Fin (2 ^ n)) ℂ) : QnnOperator n :=
fun x y => V.val (bitsEquivFin n x) (bitsEquivFin n y)
/-- PDF p.31: one seed fixed before Haar V. -/
def haarPureInput {n : ℕ} (psi : EuclideanSpace ℂ (Qubits n))
(V : Matrix.unitaryGroup (Fin (2 ^ n)) ℂ) : QnnOperator n :=
pureDensity (act (haarQubitUnitary V) psi)
/-- PDF pp.32-33: a fixed architecture and real threshold. -/
def classifierFamily {n L : ℕ} (word : Fin L → Fin 3) (O : QnnOperator n) (b : ℝ) :
Set (QnnDensity n → Bool) :=
Set.range (fun theta : Fin L → ℝ => fun rho : QnnDensity n =>
decide (b ≤ qnnLoss (circuit (fun j => qnnGenerator n (word j)) theta) rho.val O))
/-- PDF pp.13,33-34: uniform sampling of the parameter box. -/
def uniformParameters (L : ℕ) : Measure (Fin L → ℝ) :=
Measure.pi (fun _ : Fin L =>
(ENNReal.ofReal (1 / (2 * Real.pi))) • volume.restrict (Set.Icc 0 (2 * Real.pi)))
/-- PDF p.34, Eq.(96): eventual inverse-polynomial lower bound. -/
def InversePolynomialLower (f : ℕ → ℝ) : Prop :=
∃ c : ℝ, 0 < c ∧ ∃ k N : ℕ, ∀ n ≥ N, c / (n : ℝ) ^ k ≤ f n
/-- PDF pp.33-34: below-mean point condition AND exponential tail envelope,
with constants before size and tail threshold. -/
def HasNarrowGorge (L : ℕ → ℕ) (f : (n : ℕ) → (Fin (L n) → ℝ) → ℝ) : Prop :=
(∃ gap : ℕ → ℝ, InversePolynomialLower gap ∧ ∃ N : ℕ, ∀ n ≥ N,
∃ theta, f n theta ≤ (∫ t, f n t ∂(uniformParameters (L n))) - gap n) ∧
∃ C b : ℝ, 0 < C ∧ 1 < b ∧ ∃ N : ℕ, ∀ n ≥ N, ∀ d : ℝ, 0 < d →
((uniformParameters (L n))
{theta | d ≤ |f n theta - (∫ t, f n t ∂(uniformParameters (L n)))|}).toReal ≤
C / (b ^ n * d ^ 2)
section SanityChecks
/-! Small checks for definition conventions; source results remain unproved. -/
example (n : ℕ) (A B : QnnOperator n) : ⁅A, B⁆ = A * B - B * A := by
rfl
example (n : ℕ) : blockDim n (symmetricSector n) = n + 1 := by
simp [blockDim, symmetricSector]
example (n : ℕ) : qnnSectorMultiplicity n (symmetricSector n) = 1 := by
simp [qnnSectorMultiplicity, symmetricSector]
example {n : ℕ} (S : SchurFrame n) (m : Sector n) (nu : Fin (qnnSectorMultiplicity n m)) :
schurCompression S m nu 0 = 0 := by simp [schurCompression]
example : centeredDelta (0 : Matrix (Fin 1) (Fin 1) ℂ) = 0 := by simp [centeredDelta, deltaPair]
example {n : ℕ} (rho : Fin 0 → QnnDensity n) (c : Fin 0 → ℝ) :
dataOperator c rho = 0 := by simp [dataOperator]
example {n : ℕ} (H : Fin 0 → QnnOperator n) (theta : Fin 0 → ℝ) : circuit H theta = 1 := by
simp [circuit, orderedProd]
example (U : Matrix (Fin 1) (Fin 1) ℂ) (a b c e : Fin 0 → Fin 1) :
conjugationMonomial U 0 a b c e = 1 := by simp [conjugationMonomial]
example (n : ℕ) : (1 : QnnOperator n) ∈ unitaryFamily n := by
simp [unitaryFamily, PermutationEquivariant]
example : collective 0 pauliZ 1 = 0 := by
simp [collective, Finset.powersetCard_one]
example : krawtchouk 0 0 0 = 1 := by
norm_num [krawtchouk]
example : centeredDelta (1 : Matrix (Fin 1) (Fin 1) ℂ) = 0 := by
simp [centeredDelta, deltaPair]
example {n L : ℕ} (H : Fin L → QnnOperator n) (theta : Fin L → ℝ) (O : QnnOperator n)
(rho : Fin 0 → QnnDensity n) (c : Fin 0 → ℝ) : empiricalLoss H theta c rho O = 0 := by
simp [empiricalLoss]
example {n : ℕ} (P : Measure (QnnDensity n)) (O U : QnnOperator n) :
qnnPopulationRisk P (fun _ => 0) O U = 0 := by simp [qnnPopulationRisk]
example {n : ℕ} (a : QnnDensity n → ℝ) (O U : QnnOperator n) (xs : Fin 0 → QnnDensity n) :
empiricalRisk a O U xs = 0 := by simp [empiricalRisk]
example {n : ℕ} (H : Fin 0 → QnnOperator n) (theta : Fin 0 → ℝ)
(psi : EuclideanSpace ℂ (Qubits n)) : qfi H theta psi = 0 := by
ext i j
exact Fin.elim0 i
end SanityChecks
end QAlgorithms.Papers.Independent.Support50.P30
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
QAlgorithms.Papers.Independent.Support50.P30.DesignKey
For every natural number , including , the defined index type consists of all pairs , where is either false or true and is an integer satisfying . Thus it has elements, and for it still has the two elements and .
QAlgorithms.Papers.Independent.Support50.P30.HasNarrowGorge
For any function and any family of real-valued functions , let be the product of copies of normalized Lebesgue measure on , and put . This predicate is the conjunction of two assertions: there exist a function , a real , and natural numbers such that for every and, for every , there exists a parameter vector with ; and there exist real constants , , and a natural number such that
The witness in the first assertion is not required to lie in . No measurability or integrability hypotheses on are included; the integrals use the total integral convention, which returns zero when the function is not integrable, and the measure of the displayed set is defined even if that set is not measurable. The measure is converted from an extended nonnegative real to a real in the code; it is finite here. Zero-dimensional parameter spaces are allowed and carry mass on the empty vector, and the inverse-polynomial bound uses and division by zero equal to zero.
QAlgorithms.Papers.Independent.Support50.P30.IndependentBlockTwoDesign
For natural numbers , let be the length- bit strings, with sectors , dimensions , and multiplicities , for . Let be a Schur frame with matrix , rows , , , and columns in . Its requirements are both unitary identities; transformation of every matrix commuting with all bit-coordinate permutations into blocks repeated over , with zero entries between different ; and transformation of , for the usual one-coordinate Pauli operators, into this pattern with block . Given arbitrary complex matrices on , an index , and a measure on , define ,
where , and an empty matrix product is the identity. The defined property says that for every choice and every four lists for each key ,
where is Haar measure normalized to total mass . Empty scalar products are . No probability, measurability, integrability, or Hermitian hypotheses are separately imposed here; the integrals use the convention that a nonintegrable function has integral zero. The index rules out , while is allowed.
QAlgorithms.Papers.Independent.Support50.P30.InversePolynomialLower
For any function , this predicate means that there exist a real number and natural numbers such that
The exponent may be zero, in which case the lower bound is the constant . Values below are unrestricted. The threshold may also be zero: at , the quotient is when , since , and is zero when , since division by zero is defined to be zero.
QAlgorithms.Papers.Independent.Support50.P30.PermutationEquivariant
For every natural number and every complex matrix indexed by Boolean strings of length , this property means that for every permutation of the coordinate positions, where if for every , and is zero otherwise. No other condition on is imposed. For , the permutation matrix is the identity, so every such satisfies the property.
QAlgorithms.Papers.Independent.Support50.P30.QnnDensity
For every natural number , this abbreviation denotes the subtype of complex matrices , indexed by Boolean strings of length , satisfying both and , where the trace equality is an equality in . Each element includes its matrix and evidence of these conditions. When , the only such matrix is the matrix .
QAlgorithms.Papers.Independent.Support50.P30.QnnOperator
For every natural number , this abbreviation denotes the space of complex matrices whose rows and columns are indexed by all Boolean strings . These are matrices, with no Hermiticity, positivity, or unitarity requirement. When , the index set contains the unique empty string, so these are matrices.
QAlgorithms.Papers.Independent.Support50.P30.QnnSchurIndex
For every natural number , is the type of triples with , , and , where and when , while when . All indices are natural numbers, and the subtraction defining is also natural-number subtraction. When , the only triple is .
QAlgorithms.Papers.Independent.Support50.P30.SchurFrame
For any natural number , including , put , let sectors be integers , and set , , and for . A Schur frame consists of a complex matrix whose rows are indexed by triples , with and , and whose columns are indexed by , together with the following requirements. Both and hold. For every complex matrix on commuting with every permutation matrix , where precisely when for every coordinate , there exist complex matrices such that
Finally, writing for the operators applying, respectively, , , and to coordinate and the identity to every other coordinate, transforms
into the same block pattern, with . The definition specifies data and requirements; it does not assert existence or uniqueness. When , the bit-string set and row-index set are both singletons, and the displayed sum of squared operators is zero.
QAlgorithms.Papers.Independent.Support50.P30.Sector
For every natural number , is the finite index type consisting of the integers satisfying , equivalently . In particular, contains exactly the index .
QAlgorithms.Papers.Independent.Support50.P30.aggregate
For any natural number , let be the length- bit strings, with sectors , dimensions , and multiplicities , for . Let be a Schur frame with matrix , indexed by rows , , , and columns : both unitary identities hold; every matrix commuting with all permutations of bit coordinates becomes blocks , identical across and zero between different ; and the sum of squares of collective Pauli operators becomes this block pattern with block . For every sector and arbitrary complex matrix on , the defined matrix is
This is a sum over multiplicity indices without a normalizing factor; the definition includes .
QAlgorithms.Papers.Independent.Support50.P30.blockDim
For any natural number and any sector index satisfying , is the natural number . The subtraction is natural-number subtraction, truncated at zero, although the bound on ensures that . In particular, .
QAlgorithms.Papers.Independent.Support50.P30.centeredDelta
For every natural number , including , and every complex matrix , the defined real number is
There are no Hermitian, positivity, or normalization assumptions. Both squares are ordinary algebraic squares, with no complex conjugation. Complex division by zero is zero, and for this quantity is zero.
QAlgorithms.Papers.Independent.Support50.P30.circuit
For any natural numbers , let , let be arbitrary complex matrices indexed by , and let be real numbers. Define using the matrix exponential. Then is the matrix . When , this is the identity matrix. The case is included, with matrices indexed by the single empty bit string. No Hermitian assumption on the is imposed.
QAlgorithms.Papers.Independent.Support50.P30.circuitHalf
For any natural numbers , arbitrary complex matrices indexed by , real parameters for , an index with , and a Boolean value , put . The matrix is when is true, and when it is false. Thus the true branch includes the layer at . An empty product is the identity, so the false branch is the identity when . There is no admissible when ; is allowed. No Hermitian assumption on the is imposed.
QAlgorithms.Papers.Independent.Support50.P30.classifierFamily
For arbitrary natural numbers , a word with each , an arbitrary complex matrix indexed by length- Boolean strings, and a real threshold , this definition gives the set of all Boolean functions on positive semidefinite matrices of trace obtained as follows. For a Pauli matrix , let be the sum over all -element subsets of the qubits of the operator acting as on that subset and as the identity elsewhere, and put
The scalars here are interpreted in , with division by zero equal to zero. For every real parameter vector , form
The defined set is precisely , with equality at the threshold assigned and with no Hermiticity assumption on . When , the product is the identity and the set contains the single resulting function; and are allowed, so the displayed zero-denominator conventions apply.
QAlgorithms.Papers.Independent.Support50.P30.collective
For every pair of natural numbers and every complex matrix indexed by Boolean values, this defines
The resulting matrix is indexed by Boolean strings of length . There is no assumption on or restriction : for the sum is empty and equals zero, while for it equals the identity. In particular, for it is the identity when and zero otherwise.
QAlgorithms.Papers.Independent.Support50.P30.commonBlock
For any natural number , let denote the length- bit strings, and for set , , and for . Let be a Schur frame whose matrix has rows , , , and columns in , satisfies both unitary identities, and transforms every matrix commuting with all coordinate permutations into blocks repeated over with zero entries between different . Its further required transformation sends , using one-coordinate Pauli operators, into this block pattern with block . For every sector and arbitrary complex matrix on , the defined matrix is
The scalar division is in . The definition applies to arbitrary , without assuming that its individual compressed matrices coincide, and includes .
QAlgorithms.Papers.Independent.Support50.P30.conjugationMonomial
For any natural numbers , any complex matrix , and any four indexed lists , the defined complex number is
No unitarity assumption is made on , and the lists may repeat indices. When , both products are empty and the result is . When and , no such four lists exist; when , the result is .
QAlgorithms.Papers.Independent.Support50.P30.dataOperator
For any natural numbers , real coefficients for , and complex matrices indexed by that are each positive semidefinite with trace , the matrix is , with the real coefficients regarded as complex scalars. The coefficients need not be nonnegative or sum to . When , the result is the zero matrix; is also included.
QAlgorithms.Papers.Independent.Support50.P30.deltaPair
For every natural number , including , and every pair of complex matrices , the defined real number is
No Hermitian, positivity, or normalization assumptions are imposed, and the matrix product contains no conjugate transpose. Division is complex division, with division by zero defined to be zero; consequently, for , the empty traces and this quantity are all zero.
QAlgorithms.Papers.Independent.Support50.P30.densityBorel
For every natural number , this instance records that the measurable structure on the subtype of positive semidefinite complex matrices of trace one, indexed by Boolean strings of length , is exactly the Borel -algebra of its inherited topology. The statement also applies when .
QAlgorithms.Papers.Independent.Support50.P30.densityMeasurable
For every natural number , this instance equips the set of positive semidefinite complex matrices of trace one, indexed by Boolean strings of length , with its Borel measurable structure: the -algebra generated by the open sets of the subtype topology inherited from the matrix space. This includes , when the set consists of the single matrix .
QAlgorithms.Papers.Independent.Support50.P30.dynamicalLie
For every natural number , this defines a real Lie subalgebra of the complex matrices indexed by -bit strings. Write
and, for a matrix , put
The defined Lie algebra is the smallest real vector subspace closed under the commutator that contains
where the coefficients are computed in . This definition includes and , with division by zero defined to be zero; all three generators are zero for , and the third generator is zero for .
QAlgorithms.Papers.Independent.Support50.P30.empiricalLoss
For any natural numbers , arbitrary complex matrices indexed by and real parameters for , real coefficients and positive semidefinite trace- matrices indexed by for , and an arbitrary complex matrix indexed by , put , taking to be the identity when . Then is . There is no division by and no restriction on the coefficients. When , the result is ; is allowed.
QAlgorithms.Papers.Independent.Support50.P30.empiricalRisk
For any natural numbers , any function , any complex matrices on , and any indexed collection of positive semidefinite matrices with trace , this defines
There are no Hermiticity, unitarity, measurability, or bounds assumed for , and repetitions among the samples are allowed. The case is included. When , the sum is empty and real division by zero is defined as zero, so the empirical risk is zero.
QAlgorithms.Papers.Independent.Support50.P30.generalizationEvent
For any natural numbers , let be the Borel space of positive semidefinite complex matrices on with trace . Given any measure on , any function , any complex matrix on this space, and any real number , this defines the set of sample collections such that
for every unitary commuting with every permutation matrix , where precisely when for every position , and is zero otherwise. No assumptions on beyond their stated types are required to define this set. The integral is the total Bochner integral, equal to zero for a nonintegrable integrand. Both and are included; at , the empirical term is zero by the empty-sum and division-by-zero conventions.
QAlgorithms.Papers.Independent.Support50.P30.haarPureInput
For every natural number , every complex vector indexed by -bit strings, and every unitary complex matrix indexed by , let and define
This definition returns the matrix with entries
There is no assumption that has norm , so is included and returns the zero matrix. The definition includes , and it imposes no randomness or distribution on .
QAlgorithms.Papers.Independent.Support50.P30.haarQubitUnitary
For every natural number and every unitary complex matrix indexed by the integers , this defines a complex matrix indexed by -bit strings through
Thus the indices use the binary value with the first bit most significant. For , the empty string has value and is . The definition takes an arbitrary unitary matrix as input and imposes no randomness or distribution on it.
QAlgorithms.Papers.Independent.Support50.P30.krawtchouk
For arbitrary natural numbers , this defines the real number
The subtractions inside the binomial coefficients are natural-number subtractions, truncated at zero; in particular, when . Binomial coefficients are zero when their lower argument exceeds their upper argument. There are no assumptions that or , and gives .
QAlgorithms.Papers.Independent.Support50.P30.partialLoss
For any natural numbers , arbitrary complex matrices indexed by , an index with , real coefficients , positive semidefinite trace- matrices indexed by , an arbitrary complex matrix indexed by , and real parameters , define and for , and let . Then is the ordinary real derivative, evaluated at , of . The derivative operation is total, returning if a derivative does not exist. There is no admissible when ; gives the derivative of the zero function, and is allowed.
QAlgorithms.Papers.Independent.Support50.P30.pauliString
For every natural number , every arbitrary complex matrix indexed by the two Boolean values, and every subset of , this defines the matrix indexed by Boolean strings of length through
Thus it is the tensor product with factor at positions in and the two-dimensional identity elsewhere; need not be a Pauli matrix. For the result is the identity, including , when the empty product is one.
QAlgorithms.Papers.Independent.Support50.P30.qfi
For any natural numbers , any family of complex matrices on , any , and any vector , define
This declaration defines the real matrix
where the complex Euclidean inner product is conjugate linear in its first argument and linear in its second, and is the -th coordinate vector in . No Hermiticity or vector normalization is assumed. The case is allowed; for , the circuit product is the identity and this is the empty matrix.
QAlgorithms.Papers.Independent.Support50.P30.qnnGenerator
For every natural number and every index , this defines the complex matrix
where, in the Boolean order , , , and , and a subscript means that matrix acts on the indicated tensor factor with identities elsewhere. The coefficients use complex arithmetic, so is complex subtraction and division by zero equals zero. Consequently all three matrices are zero for , and the matrix is zero for .
QAlgorithms.Papers.Independent.Support50.P30.qnnLayer
For every natural number , every arbitrary complex matrix indexed by Boolean strings of length , and every real number , this defines the matrix exponential
There is no Hermiticity assumption on or sign restriction on . The definition includes , when it is the ordinary complex exponential of the single matrix entry multiplied by .
QAlgorithms.Papers.Independent.Support50.P30.qnnLoss
For any natural number and any three complex matrices indexed by the bit strings , the real number is , where is the conjugate transpose. No unitarity, positivity, trace, or Hermitian assumptions are imposed on these matrices. The case , where the matrices are , is included.
QAlgorithms.Papers.Independent.Support50.P30.qnnMeasurementFamily
For every natural number , this defines the set of complex matrices indexed by Boolean strings of length for which there exists a single choice among
such that at least one of the following equalities holds:
Here the matrices use Boolean order , and acts as at position and as the identity elsewhere. The coefficients use complex arithmetic with division by zero equal to zero. Empty sums equal zero and the empty tensor product is the identity, so for this set is ; for it is .
QAlgorithms.Papers.Independent.Support50.P30.qnnPopulationRisk
For every natural number , including zero, let be the set of positive semidefinite complex matrices on with trace , equipped with its inherited Borel measurable structure. For any measure on , any function , and any complex matrices on this space, this defines
No probability-measure, measurability, integrability, Hermiticity, or unitarity assumptions are imposed. The integral is the total real Bochner integral, which is defined to be zero when its integrand is not integrable.
QAlgorithms.Papers.Independent.Support50.P30.qnnSchurBlockDiagonal
For any natural number and any family of complex matrices of size , indexed by , define and for , or for . The matrix has row and column indices with and , and its entry at row and column is if and , and otherwise. Thus the same matrix occurs for every multiplicity index in sector . No assumptions on the matrices are imposed. When , the result is the single block .
QAlgorithms.Papers.Independent.Support50.P30.qnnSectorMultiplicity
For any natural number and any sector index satisfying , is minus when , and minus when . This subtraction takes place in the natural numbers and is truncated at zero. In particular, the value at is , including when .
QAlgorithms.Papers.Independent.Support50.P30.qubitPermutationMatrix
For every natural number and every permutation of , this defines a complex matrix , indexed by Boolean strings of length , by
When , the coordinate condition is vacuous and is the identity matrix.
QAlgorithms.Papers.Independent.Support50.P30.rowMap
For any natural number , let be the set of length- bit strings, let , and define , , and for . Let be a Schur frame with matrix : its rows have indices , where and ; it satisfies and ; it transforms every matrix commuting with all permutations of bit coordinates into blocks repeated identically over , with zero entries between different sectors or multiplicity indices; and it transforms , for the usual one-coordinate Pauli operators, into this block pattern with block . For every such sector and every multiplicity index , the defined matrix is the indicated group of rows of :
This includes , when all these index sets are singletons.
QAlgorithms.Papers.Independent.Support50.P30.schurCompression
For any natural number , write for the length- bit strings, and for put , , and when . Let have Schur-frame matrix , with row indices , , , and columns in . The frame requirements are , transformation of every matrix commuting with coordinate permutations into blocks repeated over and zero between different , and transformation of , using the usual one-coordinate Pauli operators, into this pattern with block . For every sector , every , and every complex matrix on , the defined matrix is
Thus its entry is . There is no additional restriction on , and is included.
QAlgorithms.Papers.Independent.Support50.P30.spinCasimir
For every natural number , let , and let be the matrices on that act respectively by , , and on coordinate , in the basis ordered as false, true, and by the identity on every other coordinate. Then is the complex matrix , where each square is a matrix product. When , all three sums are zero, so the result is the zero matrix.
QAlgorithms.Papers.Independent.Support50.P30.stateDerivative
For any natural numbers , any family of complex matrices on , any , any vector , and any index , this defines
where is the real Fréchet derivative and has coordinate at and zero elsewhere. No Hermiticity condition on the matrices or normalization condition on is imposed. The case is included; when , there is no index for which this definition can be instantiated.
QAlgorithms.Papers.Independent.Support50.P30.symmetricSector
For every natural number , the sectors are the integers satisfying , where is integer division. This definition selects the sector . It is defined also for .
QAlgorithms.Papers.Independent.Support50.P30.tangentCommutant
For every natural number , including zero, this defines a real vector subspace of the complex matrices indexed by -bit strings: it is the real linear span of all matrices such that and for every permutation of the positions, where
Thus the span uses real coefficients, although its elements are complex matrices; for , the matrices are .
QAlgorithms.Papers.Independent.Support50.P30.uniformParameters
For every natural number , this definition gives the product measure on whose measure in each coordinate is Lebesgue measure restricted to the closed interval and multiplied by :
Thus the coordinates have independent uniform distributions on that interval. For , the parameter space consists of the unique empty vector, and the measure assigns it mass .
QAlgorithms.Papers.Independent.Support50.P30.unitaryFamily
For every natural number , this defines the set of complex matrices indexed by Boolean strings of length such that and for every permutation of the coordinate positions, where exactly when for every , and is zero otherwise. When , this is the set of matrices whose single entry has modulus one.
QAlgorithms.Papers.Independent.Support50.P30.variance
For every type equipped with a measurable space, every measure on , and every function , the defined real number is
There is no assumption that is a probability measure or that is measurable or integrable. Each integral separately uses the convention that the integral of a nonintegrable function is zero.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.