Theorem 5.22, p.71 — conditional symmetry with an auxiliary string fails with linear error at every logarithmic weight
OpenQuantumKtSoI.Supplement.theorem_5_22complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
For every there is such that infinitely many triples of strings satisfy
Here and are concatenations.
This is the failure of conditional symmetry of information (Definition 5.17) with a linear error term, for every coefficient of the logarithmic term.
Formalization Note The values of are 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
Preamble
import Mathlib import Definitions.Def_QuantumKtSoI_qKt open Classical
Formal statement
namespace QuantumKtSoI.Supplement
/-- **Theorem 5.22** (Failure of conditional symmetry of information with an auxiliary string;
Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.71). For every `κ ≥ 0` there is `η > 0` such that infinitely many triples of strings
`(w, x, y)` satisfy `qKt(y|wx) > qKt(xy|w) − qKt(x|w) + η(|x|+|y|) + κ log(|w|+|x|+|y|+2)`.
**Formalization Note** `wx` and `xy` are concatenations, as in the paper; a triple is
`(w, (x, y))`. `G` is any admissible glue routine set (p.24). -/
theorem theorem_5_22 (G : GlueRoutines) (hG : G.Admissible) :
∀ κ : ℝ, 0 ≤ κ → ∃ η : ℝ, 0 < η ∧
{t : List Bool × List Bool × List Bool |
(qKt G (t.2.1 ++ t.2.2) t.1 : ℝ) - qKt G t.2.1 t.1 +
η * ((t.2.1.length : ℝ) + t.2.2.length) +
κ * Real.logb 2 ((t.1.length : ℝ) + t.2.1.length + t.2.2.length + 2) <
qKt G t.2.2 (t.1 ++ t.2.1)}.Infinite := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem 5.22, p.71; Definition 5.17, p.65