Theorem 4 (Generalization bound)
OpenQAlgorithms.Papers.Independent.Support50.P30.generalization_boundFix the observable normalization . There is a universal such that the following holds for , , and . Let be a Borel probability measure on -qubit density matrices, let be a measurable label-dependent coefficient with , and let be a Hermitian permutation-equivariant observable. Define and for independent samples from . With probability at least , simultaneously for all commuting unitaries ,
The logarithm is natural. The coefficient denotes the composition of the label weight with the labeling function; the population coefficient is not divided by . The uniform event applies in particular to any trained parameters selected from the data.
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
/-- PDF p.7, Theorem 4, Eq.(20); p.15 fixes bounded measurable losses.
Fix K=1; C is universal and the event is uniform in the trained parameters. -/
theorem generalization_bound :
∃ C : ℝ, 0 < C ∧ ∀ (n M : ℕ), 2 ≤ n → 1 ≤ M →
∀ (P : Measure (QnnDensity n)), IsProbabilityMeasure P →
∀ (a : QnnDensity n → ℝ), Measurable a → (∀ rho, |a rho| ≤ 1) →
∀ (O : QnnOperator n), O.IsHermitian → PermutationEquivariant O → specNorm O ≤ 1 →
∀ deltaConf : ℝ, 0 < deltaConf → deltaConf < 1 →
(Measure.pi (fun _ : Fin M => P))
(generalizationEvent P a O
(C * (Real.sqrt (((n + 3).choose 3 : ℝ) / (M : ℝ)) +
Real.sqrt (Real.log (1 / deltaConf) / (M : ℝ))))) ≥
ENNReal.ofReal (1 - deltaConf) := by sorry
end QAlgorithms.Papers.Independent.Support50.P30
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
There exists a real constant such that the following holds for every pair of natural numbers and . Let be the Borel space of positive semidefinite complex matrices on with trace , let be any probability measure on , let be measurable with for every , and let be Hermitian, have Euclidean operator norm at most , and commute with every permutation of the qubit positions. For every real with , the product measure assigns measure at least , viewed as an extended nonnegative real number, to the sample collections for which, simultaneously for every unitary commuting with every qubit-position permutation,
Here a position permutation acts through the matrix with entry at exactly when for every , and zero otherwise; is the natural logarithm. The same constant applies to all the quantified choices.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.