Theorem 7.3, p.100 — no machine decides a language consistent with a gap infinitely often in time
OpenQuantumKtSoI.Supplement.theorem_7_3complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
Let be a rational number with and put . With the encoded queries of length :
- for every that is computable in time polynomial in the value of its argument and satisfies for all large , no machine decides a language consistent with the gap infinitely often in time ;
- the conclusion holds for ;
- it also holds for with any constant ;
- in particular, no machine decides infinitely often in time .
A language is consistent with the gap if it contains whenever and excludes it whenever .
This is the exponential lower bound for deciding threshold languages of quantum Kt complexity.
Formalization Note Clauses 2 and 3 are stated without a computability hypothesis on the gap, as in the paper.
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
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 7.3** (Consistent threshold-language decision takes exponential time; restatement of
Theorem 1.4; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.100). Let `η` be rational with `0 < η < 1/2` and put `ε = η/40`. For every
`g : ℕ → ℕ` computable in time polynomial in the value of its argument with `g(λ) ≤ (1/2 − η)λ` for
all large `λ`, no machine decides a language consistent with the gap `g` infinitely often in time
`2^{εν}`. The conclusion holds for `g(λ) = ⌊(1/2 − η)λ⌋` and also for `g(λ) = ⌈c log(λ+2)⌉` with any
constant `c ≥ 0`; in particular no machine decides `L_thr` infinitely often in time `2^{εν}`.
**Formalization Note** The queries `q(x, s)`, `wd`, `ν`, consistency with a gap and `L_thr` are
those of §6.6 and p.98 (module `query`) for `µ(x) = qKt(x)`; "decides infinitely often in time
`2^{εν}`" is `DecidesIO`. The two special gaps are stated without a computability hypothesis, as
in the paper (`c` need not be computable). `G` is any admissible glue routine set (p.24). -/
theorem theorem_7_3 (G : GlueRoutines) (hG : G.Admissible) (η : ℚ) (hη0 : 0 < η) (hη1 : η < 1 / 2) :
(∀ g : ℕ → ℕ, PolyInValue g →
(∃ l₀ : ℕ, ∀ lam ≥ l₀, (g lam : ℝ) ≤ (1 / 2 - (η : ℝ)) * lam) →
∀ L : Set (List Bool), ConsistentGap (fun x => (qKt G x [] : ℝ)) g L →
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A L ((η : ℝ) / 40)) ∧
(∀ L : Set (List Bool),
ConsistentGap (fun x => (qKt G x [] : ℝ)) (fun lam => ⌊(1 / 2 - (η : ℝ)) * lam⌋₊) L →
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A L ((η : ℝ) / 40)) ∧
(∀ c : ℝ, 0 ≤ c → ∀ L : Set (List Bool),
ConsistentGap (fun x => (qKt G x [] : ℝ))
(fun lam => ⌈c * Real.logb 2 ((lam : ℝ) + 2)⌉₊) L →
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A L ((η : ℝ) / 40)) ∧
¬∃ A : CodedMachine, A.Valid ∧ DecidesIO A (Lthr fun x => (qKt G x [] : ℝ)) ((η : ℝ) / 40) := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem 7.3, p.100; queries and consistency, p.96; L_thr and deciding infinitely often, p.98