Theorem 1.7 — high-entropy extraction
OpenMatrixQuantumSampler595.Correspondence.Supplement.high_entropy_extractionFix . There are positive constants , depending only on , and a uniform explicit family such that, for every integer , every real and , it gives a strong conditional-min-entropy quantum-proof extractor with source length , seed length , and output length . Writing and ,
One finite deterministic evaluator runs in time polynomial in for fixed . Security quantifies over every normalized cq source and arbitrary finite-dimensional quantum side information. Empty output is allowed when the loss bound is nonpositive. This companion retains both the exact leading seed coefficients and the entire output-loss guarantee.
Formalization Note Integer accuracy controls round upward (sampling uses ); varying entropy controls round downward. Security and displayed bounds use the original real parameters. Fixed-rate families need no entropy control. Theorem 5.3 supplies its exact requested output length as an integer control, and Theorem 6.4 supplies . The actual machine and its polynomial are part of the uniform explicitness witness.
Differences from the source:
- encoding: binary source, seed and output strings with one-based sample/coordinate labels → Fin-indexed Boolean strings and a uniform Fin(2^d) seed alphabet with zero-based labels; reason: finite relabelling preserves all states, probabilities and maps
- encoding: explicit construction with polynomial-time evaluation for the displayed fixed parameters → one finite TM2 machine computes lengths and samples from the specified integer controls for the entire family; reason: step semantics and canonical rounded numerical inputs express uniform polynomial time without real oracles or advice
- encoding: O and Omega with only the printed fixed-parameter dependencies → positive real resource constants quantified before all varying instances; reason: uniform quantified meaning of the asymptotic resource bounds supported by the construction proofs
import Definitions.Def_MatrixQuantumSampler595_Correspondence_Supplement_ConditionalExtractor import Definitions.Def_MatrixQuantumSampler595_Correspondence_Supplement_UniformConstruction
namespace MatrixQuantumSampler595.Correspondence.Supplement
/-- Theorem 1.7, p.6: exact leading seed coefficients and full output-loss bound. -/
theorem high_entropy_extraction (alpha : ℝ) (halpha : 0 < alpha) :
∃ (Cd Cm : ℝ) (E : Controls → FiniteSeededMap),
0 < Cd ∧ 0 < Cm ∧ IsUniformExplicit E ∧
∀ n : ℕ, 1 ≤ n → ∀ (k eta : ℝ), 0 ≤ k → k ≤ n →
0 < eta → eta ≤ 1 / 2 →
let a := (n : ℝ) - k
let F := E ⟨n, entropyControl k, accuracyControl eta, 0⟩
F.sourceLength = n ∧ ∃ d : ℕ, F.samples = 2 ^ d ∧
(d : ℝ) ≤ (1 + alpha) * deficiencyLog a +
(2 + alpha) * logTwo (1 / eta) + Cd ∧
(n : ℝ) - Cm * (a + logTwo (1 / eta)) ≤ F.outputLength ∧
IsStrongConditionalExtractor F.apply k eta := by sorry
end MatrixQuantumSampler595.Correspondence.Supplement