Unnumbered generalization sample sufficiency
OpenQAlgorithms.Papers.Independent.Support50.P30.generalization_sample_sufficiencyUnder the bounded measurable loss and i.i.d. sampling assumptions of Theorem 4 with , there is a universal such that, for and , every positive integer sample budget satisfying
ensures simultaneously for all commuting unitaries with probability at least . For fixed accuracy and confidence this supplies a sufficient budget of order . The threshold is a sufficiency condition and does not treat an arbitrarily small upper-bounded sample count as sufficient.
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: a sufficient sample threshold. For fixed epsilon and delta
this threshold grows as O(n^3); a tiny M is not an accuracy hypothesis. -/
theorem generalization_sample_sufficiency :
∃ C : ℝ, 0 < C ∧ ∀ (n M : ℕ), 2 ≤ n → 1 ≤ M →
∀ (epsilon deltaConf : ℝ), 0 < epsilon → epsilon < 1 →
0 < deltaConf → deltaConf < 1 →
C * (((n + 3).choose 3 : ℝ) + Real.log (1 / deltaConf)) / epsilon ^ 2 ≤ (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 →
(Measure.pi (fun _ : Fin M => P)) (generalizationEvent P a O epsilon) ≥
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, for every pair of natural numbers , , and every pair of real numbers , satisfying
the following holds. Let be the Borel space of positive semidefinite complex matrices on with trace . For every probability measure on , every measurable satisfying for every , and every Hermitian matrix of Euclidean operator norm at most that commutes with every permutation of the qubit positions, the product measure assigns measure at least , viewed as an extended nonnegative real number, to the sample collections satisfying, simultaneously for every unitary commuting with every qubit-position permutation,
A position permutation is represented by the matrix whose entry is exactly when for every , and zero otherwise; is the natural logarithm. The constant is independent of all subsequent choices.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.