Theorem 29 (companion theorem; not used in the proof of the goal) — DQI quantum streaming algorithm
OpenRandomStreamCI.CodeIntersection.Supplement.opi_quantum_upper_boundFor Problem 2 let be any admissible degree family with and . Put
There are , a threshold and nonnegative errors such that, for every admissible , every characteristic-two field of size and every enumeration of its nonzero points, there is one legal polynomial-output quantum streaming program satisfying
The program and common error bound precede the order quantifier. The output is an actual polynomial of degree below , including zero, or failure; abort probability is retained in the unconditional success law. All persistent classical and quantum registers, reusable channel environments, decoding scratch and final coefficient readout are charged. No polynomial-time claim is made. This companion theorem has the full quantum degree regime, independently of Theorem 27's stronger classical assumptions.
Differences from the source:
- encoding: coordinates, times and symbols as finite labelled sets → Fin indices numbered from zero and finite alphabet types; reason: bijections of labels preserve every source instance
- encoding: q any power of two, n=q-1 and distinct nonzero evaluation points → every finite field of characteristic two with cardinality n+1 and every nonzero embedding Fin n into it; reason: all finite fields and evaluation enumerations in Problem 2 are covered, including non-prime fields
- encoding: asymptotics along source-admissible n and unspecified eventual constants → the filter atTop restricted to all n+1=2^e, and explicit positive constants and thresholds; reason: expands the asymptotic quantifiers without selecting a smaller subsequence
- reading: one-pass quantum streaming with bounded space and unrestricted computation time → fixed finite-dimensional current-item-controlled CPTP channels and an input-independent normalized coefficient-output POVM; reason: the source specifies no uniform circuit convention; all persistent registers, recycled dilation environments, preparation and output workspace are charged, and arbitrary fixed operations require no extra input access
- encoding: output a polynomial in P_d with unconditional success probability → a normalized POVM over d coefficient values or an explicit abort, averaged over the uniform oracle at each fixed order; reason: the published coefficient polynomial bijects d coefficients with P_d, and aborts are never postselected away
- encoding: O(d log n) total quantum workspace → 3q persistent-and-dilation space plus twice the ceiling of log_2(1+|F|^d) and one flag, bounded by Kdlog_2 n; reason: this charges every register and uses coefficient outputs; the constant-factor overhead preserves the full asymptotic bound
import Definitions.Def_RandomStreamCI_CodeIntersection_Supplement_Asymptotics import Definitions.Def_RandomStreamCI_CodeIntersection_Supplement_Quantum
namespace RandomStreamCI.CodeIntersection.Supplement
open Filter Topology
/-- Theorem 29, pp. 28--30. The quantum degree regime is deliberately distinct from
Theorem 27's. One actual polynomial-output program serves every stream order. -/
theorem opi_quantum_upper_bound (d : ℕ → ℕ) (hd : DegreeFamily d)
(hlarge : Tendsto (fun n => (d n : ℝ)) opiAtTop Filter.atTop)
(hsmall : Tendsto (fun n => (d n : ℝ) / (n : ℝ)) opiAtTop (𝓝 0)) :
∃ K : ℝ, 0 < K ∧ ∃ N : ℕ, ∃ ε : ℕ → ℝ,
(∀ n, 0 ≤ ε n) ∧ Tendsto ε opiAtTop (𝓝 0) ∧
∀ n : ℕ, N ≤ n → ∀ hn : AdmissibleLength n,
∀ (F : Type) [Field F] [Fintype F] [DecidableEq F] [CharP F 2],
Fintype.card F = n + 1 → ∀ α : Fin n ↪ F, (∀ i, α i ≠ 0) →
∃ Q : PolynomialProgram n (d n) F,
(Q.memoryBits : ℝ) ≤ K * (d n : ℝ) * log₂ (n : ℝ) ∧
∀ π : Order n F, 1 - ε n ≤ Q.successAtOrder α (target n (d n)) π := by sorry
end RandomStreamCI.CodeIntersection.Supplement