Theorem 4.13, p.50 — no machine decides in time , nor in time
OpenQuantumKtSoI.Supplement.theorem_4_13complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
Let be an integer and , and let satisfy for all large . Write for the promise problem with
where and , and let with .
- No machine decides in time .
- Consequently, for every fixed real , no machine decides it in time .
A machine decides a promise problem in time if, from some length on, it halts within steps on every branch, accepts YES instances with probability at least and NO instances with probability at most .
This is the unconditional lower bound for minimizing quantum Kt complexity beyond every quasipolynomial time bound; it is the engine of the worst-case symmetry failure.
Formalization Note is the published measure of the base mission, read in ; logarithms are base .
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)
Preamble
import Mathlib import Definitions.Def_QuantumKtSoI_qKt import Definitions.Def_QuantumKtSoI_Supplement_Ha import Definitions.Def_QuantumKtSoI_Supplement_DecidesPromise import Definitions.Def_QuantumKtSoI_Supplement_GapMqKtP open Classical
Formal statement
namespace QuantumKtSoI.Supplement
/-- **Theorem 4.13** (Gap minimization lower bound; restatement of Theorem 1.6; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.50). Let
`a ≥ 1` be an integer and `γ ∈ (0,1)`. Let `c : ℕ → ℕ` satisfy `⌊N^γ⌋ ≤ c(N) ≤ N − 2` for all
large `N`. No machine decides `Gap-MqKtP[c, N − 2]` in time `H_a(N)`. Consequently, for every fixed
real `b ≥ 1`, no machine decides `Gap-MqKtP[c, N − 2]` in time `2^{(log N)^b}`.
**Formalization Note** The glue routines `G` are any admissible set (p.24), as in the base mission.
`Gap-MqKtP[c, N − 2]` uses the clipped thresholds of p.49 (`GapMqKtPClip`); "decides in time `T`"
is the convention of p.49 (`DecidesPromise`: all-branch halting by `⌊T(n)⌋`, from some length on);
a machine is a valid coded machine. Logarithms are base 2. -/
theorem theorem_4_13 (G : GlueRoutines) (hG : G.Admissible) (a : ℕ) (ha : 1 ≤ a) (γ : ℝ)
(hγ0 : 0 < γ) (hγ1 : γ < 1) (c : ℕ → ℕ)
(hc : ∃ N₀ : ℕ, ∀ N ≥ N₀, ⌊(N : ℝ) ^ γ⌋₊ ≤ c N ∧ c N ≤ N - 2) :
(¬∃ B : CodedMachine, B.Valid ∧
DecidesPromise B (GapMqKtPClip (fun x => (qKt G x [] : ℝ)) c).1
(GapMqKtPClip (fun x => (qKt G x [] : ℝ)) c).2 (fun N => (Ha a N : ℝ))) ∧
∀ b : ℝ, 1 ≤ b → ¬∃ B : CodedMachine, B.Valid ∧
DecidesPromise B (GapMqKtPClip (fun x => (qKt G x [] : ℝ)) c).1
(GapMqKtPClip (fun x => (qKt G x [] : ℝ)) c).2
(fun N => (2 : ℝ) ^ (Real.logb 2 (N : ℝ)) ^ b) := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem 4.13, p.50; Definition 4.12 and conventions, p.49; clocks, p.48