Theorem 6.4 — seed length versus output loss
OpenMatrixQuantumSampler595.Correspondence.Supplement.seed_output_tradeoffThere are an absolute constant and one uniform explicit family such that, for every integer , every real , every and every integer , there is a strong conditional-min-entropy quantum-proof extractor with source length , seed length and output length . Write and use the deficiency convention . Then
Here is the actual logarithm, equal to zero at . One finite deterministic evaluator runs in time polynomial in . The loss constant and runtime polynomial are uniform in all parameters. Both conclusions include the empty-output branch and there is no upper bound on . This companion records the full seed/output tradeoff.
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 6.4, p.29: the loss constant is absolute; exact seed bound (6.3), including +5. -/
theorem seed_output_tradeoff :
∃ (C : ℝ) (E : Controls → FiniteSeededMap), 0 < C ∧ IsUniformExplicit E ∧
∀ N : ℕ, 1 ≤ N → ∀ (k eta : ℝ), 0 ≤ k → k ≤ N →
0 < eta → eta < 1 / 4 → ∀ ell : ℕ, 1 ≤ ell →
let a := (N : ℝ) - k
let F := E ⟨N, entropyControl k, accuracyControl eta, ell⟩
F.sourceLength = N ∧ ∃ d : ℕ, F.samples = 2 ^ d ∧
(d : ℝ) ≤ 2 * logTwo (1 / eta) + logTwo ell + a / ell + 5 ∧
(N : ℝ) - C * (a + logTwo (1 / eta) +
ell * (deficiencyLog a + logTwo (1 / eta) + logTwo ell)) ≤ F.outputLength ∧
IsStrongConditionalExtractor F.apply k eta := by sorry
end MatrixQuantumSampler595.Correspondence.Supplement