Theorem F.4, p.235 — a positive linear gap for every rational charge
OpenQuantumKtSoI.Supplement.theorem_F_4complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
For every rational there are rational constants such that the following holds. For every function computable in time polynomial in the value of its argument with for all large , no machine decides a language consistent with the gap for infinitely often in time . In particular, the conclusion holds for exact threshold decision, that is, for the gap , and for every polynomial-time computable gap .
Here a language is consistent with the gap for if it contains the query whenever and excludes it whenever .
So an exponential lower bound for threshold decision holds at some linear gap for every charge, not only for .
Formalization Note is the published qKtCharge.
Differences from the source:
- generalization: the glue routines are fixed once and for all by their p.24 properties → every admissible glue routine set G (hypothesis G.Admissible); descriptions, P_e and qKt are those of G; reason: the proofs use only the p.24 properties and the paper's routines are one admissible set; same as the published base items
- encoding: a machine of Definition 3.1 → a valid coded machine of the base mission (CodedMachine with Valid), halting on every branch by the floor of the stated deadline; reason: the base mission's representation of machines; halting within a time bound is all-branch and real deadlines are floors (p.22)
- reading: g computable in time polynomial in the value of its argument (no input format named) → a deterministic coded machine on input b(λ) halts within c(λ+2)^k steps with output b(g(λ)); reason: with a bound polynomial in the value λ, unary and binary inputs give the same class
- reading: every polynomial-time computable gap g(λ) = o(λ) → g computable in time polynomial in the value of its argument with: for every δ > 0, eventually g(λ) ≤ δλ; reason: the same computability notion as in the main clause; the usual meaning of little-o
Preamble
import Mathlib import Definitions.Def_QuantumKtSoI_qKt import Definitions.Def_QuantumKtSoI_Supplement_query import Definitions.Def_QuantumKtSoI_Supplement_PolyInValue open Classical
Formal statement
namespace QuantumKtSoI.Supplement
/-- **Theorem F.4** (A positive linear gap for every charge; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.235). For every rational `c > 0`
there are rational constants `γ_c, ε_c > 0` such that, for every `g : ℕ → ℕ` computable in time
polynomial in the value of its argument with `g(λ) ≤ γ_c λ` for all large `λ`, no machine decides a
language consistent with the gap `g` for `qKt^{(c)}` infinitely often in time `2^{ε_c ν}`. In
particular, the conclusion holds for exact threshold decision, that is, for the gap `g = 0`, and for
every polynomial-time computable gap `g(λ) = o(λ)`.
**Formalization Note** `qKt^{(c)}` is the published `qKtCharge G c` (Definition 4.2, threshold
`2/3`); consistency with a gap for `qKt^{(c)}` (p.229) and the queries are those of §6.6 with
`µ(x) = qKt^{(c)}(x)`. "Polynomial-time computable" in the last clause is read as in the main
clause (`PolyInValue`), and `g(λ) = o(λ)` as: for every `δ > 0`, eventually `g(λ) ≤ δλ`. `G` is any
admissible glue routine set (p.24). -/
theorem theorem_F_4 (G : GlueRoutines) (hG : G.Admissible) :
∀ c : ℚ, 0 < c → ∃ γc εc : ℚ, 0 < γc ∧ 0 < εc ∧
(∀ g : ℕ → ℕ, PolyInValue g →
(∃ l₀ : ℕ, ∀ lam ≥ l₀, (g lam : ℝ) ≤ (γc : ℝ) * lam) →
∀ L : Set (List Bool), ConsistentGap (fun x => qKtCharge G c x []) g L →
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A L εc) ∧
(∀ L : Set (List Bool), ConsistentGap (fun x => qKtCharge G c x []) (fun _ => 0) L →
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A L εc) ∧
∀ g : ℕ → ℕ, PolyInValue g →
(∀ δ : ℝ, 0 < δ → ∃ l₀ : ℕ, ∀ lam ≥ l₀, (g lam : ℝ) ≤ δ * lam) →
∀ L : Set (List Bool), ConsistentGap (fun x => qKtCharge G c x []) g L →
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A L εc := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem F.4, p.235; consistency for qKt^{(c)}, p.229