Theorem 7 (VC dimension for the unitary Sn model)
ProvedQAlgorithms.Papers.Independent.Support50.P30.unitaryModel_vcDimensionLet and fix a layered generator schedule from Eq. (9), a Hermitian measurement from Eq. (10), and a real threshold . The classifiers act on all -qubit density matrices, including mixed states, by . Their VC dimension satisfies
The bound is independent of depth and is of order . It uses the fixed real Hermitian input commutant feature space; the defective output-commutant statement for arbitrary channels in Theorem 8 is not needed.
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P30
noncomputable section
open MeasureTheory
open scoped BigOperators ComplexConjugate Matrix.Norms.L2Operator NNReal ENNReal
namespace QAlgorithms.Papers.Independent.Support50.P30
attribute [local instance] LieRing.ofAssociativeRing
/-- PDF p.32, Theorem 7: arbitrary mixed-state domain; real Hermitian
commutant dimension, without an extra factor of two. -/
theorem unitaryModel_vcDimension {n L : ℕ} (hn : 2 ≤ n) (word : Fin L → Fin 3)
(O : QnnOperator n) (hO : O ∈ qnnMeasurementFamily n) (hHerm : O.IsHermitian) (b : ℝ) :
QAlgorithms.Learning.vcDimSet (classifierFamily word O b) ≤
((∑ m : Sector n, blockDim n m ^ 2 : ℕ) : ℕ∞) ∧
(∑ m : Sector n, blockDim n m ^ 2) = (n + 3).choose 3 := by sorry
end QAlgorithms.Papers.Independent.Support50.P30
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every pair of natural numbers with , every word , every Hermitian matrix indexed by length- Boolean strings satisfying the measurement-family condition below, and every real threshold , the following holds. For , let denote the sum, over all -element subsets of the qubits, of on those qubits and the identity elsewhere. The measurement-family condition is that, for at least one such , equals one of , , or . Define , , , and let consist of all functions on positive semidefinite trace-one matrices that, for some , return exactly when
Then
Here the VC dimension is the supremum, in , of the cardinalities of finite sets of density matrices on which every Boolean labeling is realized by a member of ; the finite bound is viewed in that same extended number system. There is no lower bound on , and for the product defining is the identity.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.