Theorem D.30, p.181 — a quasi-linear interpreter of descriptions
OpenQuantumKtSoI.Supplement.theorem_D_30complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
There are a machine of Definition 3.1 and a polynomial with nonnegative coefficients such that, for every description , all strings and every integer ,
The interpreter simulates every description with an overhead that is linear in the running time up to a factor polynomial in the description length and the logarithm of the time.
Formalization Note is a real polynomial evaluated at a real argument and the deadline is a floor.
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_Supplement_qKtU open Classical
Formal statement
namespace QuantumKtSoI.Supplement
/-- **Theorem D.30** (Quasi-linear interpreter; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.181). There are a machine `I` of
Definition 3.1 and a polynomial `p_I` with nonnegative coefficients such that, for every description
`e`, all strings `x, y` and every integer `t ≥ 1`,
`P_I(⟨e, x⟩; p_I(|e| + log(t + |x| + 2))(t + |x| + |e| + 1), y) ≥ P_e(x; t, y)`.
**Formalization Note** `InterpreterProp`: `I` is a valid coded machine, `p_I` a real polynomial
with nonnegative coefficients, the deadline is read as `⌊·⌋` (p.22), and `⟨e, x⟩` pairs the bit
string of `e`. Descriptions and `P_e` are those of the admissible glue routine set `G` (p.24). -/
theorem theorem_D_30 (G : GlueRoutines) (hG : G.Admissible) :
∃ I : CodedMachine, ∃ pI : Polynomial ℝ, InterpreterProp G I pI := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem D.30, p.181