Theorem 1.6 — strong matrix sampling
OpenMatrixQuantumSampler595.Correspondence.Supplement.strong_matrix_samplingFix . There are positive constants depending only on and a uniform explicit family such that, for every pair of integers and real , a strong -dimensional matrix sampler exists with and, putting ,
Each sample is computable in time polynomial in , by one finite machine and polynomial chosen for this . The tests are arbitrary position-dependent complex matrices of operator norm at most one, as in the published strong sampler predicate. This companion records the simultaneous randomness and sample guarantees.
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(t) sample 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.6, pp.5–6: both resource bounds and uniform polynomial-time per-sample evaluation. -/
theorem strong_matrix_sampling (alpha : ℝ) (halpha : 0 < alpha) :
∃ (Cr Ct : ℝ) (E : Controls → FiniteSeededMap),
0 < Cr ∧ 0 < Ct ∧ IsUniformExplicit E ∧
∀ (m D : ℕ), 1 ≤ m → 1 ≤ D → ∀ (delta epsilon : ℝ),
0 < delta → delta ≤ epsilon → epsilon ≤ 1 / 2 →
let L := logTwo (2 * (D : ℝ) / delta)
let F := E ⟨m, upperControl L, accuracyControl epsilon, 0⟩
F.outputLength = m ∧ 1 ≤ F.samples ∧
|(F.sourceLength : ℝ) - m| ≤ Cr * L ∧
(F.samples : ℝ) ≤ Ct * L ^ (1 + alpha) * epsilon ^ (-2 - alpha) /
logTwo (L / epsilon) ∧
IsStrongMatrixSampler F.apply D delta epsilon := by sorry
end MatrixQuantumSampler595.Correspondence.Supplement