Theorem D.40, p.187 — Theorem 5.25 for every measure within of , in particular for
OpenQuantumKtSoI.Supplement.theorem_D_40complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
Let assign a real number to every pair of strings, and suppose that there is a constant with
Then Theorem 5.25 holds with in place of , with an that depends only on and : for all reals and integers there is such that no machine, from some length on, halts on within steps, accepts with probability at least if and rejects with probability at least if .
In particular this holds for for every quasi-linear universal machine , and for every machine that satisfies Equation (36).
This extends the exponential hardness of conditional estimation to every measure logarithmically close to .
Formalization Note Quantifier order: for all there is that works for every .
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)
- generalization: Equation (36) refers to the machine I of Theorem D.30 → the Equation (36) clause is stated for every machine I with the Theorem D.30 property; reason: Corollary D.39 uses only that property of I; the paper's I has it
- encoding: qKt_U, with the minimum of the empty set equal to +∞ → qKt_U is ℕ∞-valued; the statement first asserts that it is finite everywhere and then reads its values as reals; reason: the restated results are inequalities between finite values; finiteness holds for every polynomially universal machine (p.118)
Preamble
import Mathlib import Definitions.Def_QuantumKtSoI_qKt import Definitions.Def_QuantumKtSoI_Supplement_qKtU import Definitions.Def_QuantumKtSoI_Supplement_Thm525For open Classical
Formal statement
namespace QuantumKtSoI.Supplement
/-- **Theorem D.40** (Hardness of estimating a comparable measure; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.187). Let `µ` assign a real
number `µ(y|x)` to every pair of strings, write `µ(y) = µ(y|ε)`, and suppose that there is a constant
`B ≥ 1` with `|µ(y|x) − qKt(y|x)| ≤ B log(|x|+|y|+2) + B` for all strings `x, y`. Then Theorem 5.25
holds with `µ` in place of `qKt`, with an `η` that depends on `α, β, c_A` and `B`. In particular, it
holds for `µ = qKt_U` for every quasi-linear universal machine `U`, and for every machine `U` that
satisfies Equation (36).
**Formalization Note** Quantifier order: `∀ α β c_A B, ∃ η, ∀ µ` (`η` does not depend on `µ`).
`NoSep µ α β c_A η` is the conclusion of Theorem 5.25 for `µ` at that `η`, and `Thm525For µ` is
Theorem 5.25 for `µ` (module `Thm525For`). The `qKt_U` clauses first assert that `qKt_U`
(`ℕ∞`-valued, p.117) is finite, then read its values in `ℝ`. Equation (36) refers to "the machine
`I` of Theorem D.30"; that clause is stated for every machine `I` with the Theorem D.30 property
(`InterpreterProp`), as in Theorem D.34: the proof (Corollary D.39, through Lemma D.33) uses only
that property of `I`, and the paper's `I` has it.
`G` is any admissible glue routine set (p.24). -/
theorem theorem_D_40 (G : GlueRoutines) (hG : G.Admissible) :
(∀ α β : ℝ, 0 < α → α < β → β < 1 → ∀ cA : ℕ, 1 ≤ cA → ∀ B : ℝ, 1 ≤ B →
∃ η : ℝ, 0 < η ∧ ∀ μ : List Bool → List Bool → ℝ,
(∀ x y : List Bool,
|μ y x - qKt G y x| ≤ B * Real.logb 2 ((x.length : ℝ) + y.length + 2) + B) →
NoSep μ α β cA η) ∧
(∀ U : CodedMachine, QuasiLinUniversal U →
(∀ y x : List Bool, qKtU U y x ≠ ⊤) ∧ Thm525For fun y x => ((qKtU U y x).toNat : ℝ)) ∧
∀ I : CodedMachine, ∀ pI : Polynomial ℝ, InterpreterProp G I pI →
∀ U : CodedMachine, Eq36 I U →
(∀ y x : List Bool, qKtU U y x ≠ ⊤) ∧ Thm525For fun y x => ((qKtU U y x).toNat : ℝ) := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem D.40, p.187; Theorem 5.25, p.75; Equation (36), p.186