Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The symmetry-failure statements of §5 for a conditional measure μ\muμ

Definition
QuantumKtSoI_Supplement_SoIFailures

by iris · Nov 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing

For a real-valued conditional measure μ(y∣x)\mu(y|x)μ(y∣x) with μ(y)=μ(y∣ϵ)\mu(y)=\mu(y|\epsilon)μ(y)=μ(y∣ϵ), this module states, with μ\muμ in place of qKt\mathrm{qKt}qKt:

  1. Theorem 5.10: for every real a≥1a\ge1a≥1, infinitely many pairs satisfy μ(y∣x)−μ(⟨x,y⟩)+μ(x)>2(log⁡log⁡(∣x∣+∣y∣+4))a\mu(y|x)-\mu(\langle x,y\rangle)+\mu(x)>2^{(\log\log(|x|+|y|+4))^a}μ(y∣x)−μ(⟨x,y⟩)+μ(x)>2(loglog(∣x∣+∣y∣+4))a, and symmetry fails with every fixed polylogarithmic error;
  2. Corollary 5.13: for every real a≥1a\ge1a≥1, infinitely many nnn admit x,y∈{0,1}nx,y\in\{0,1\}^nx,y∈{0,1}n with μ(y∣x)−μ(⟨x,y⟩)+μ(x)>2(log⁡log⁡(2n+4))a\mu(y|x)-\mu(\langle x,y\rangle)+\mu(x)>2^{(\log\log(2n+4))^a}μ(y∣x)−μ(⟨x,y⟩)+μ(x)>2(loglog(2n+4))a;
  3. Corollary 5.15(ii),(iii): the same two statements with the error Fa[j](∣x∣+∣y∣)F^{[j]}_a(|x|+|y|)Fa[j]​(∣x∣+∣y∣), respectively Fa[j](2n)F^{[j]}_a(2n)Fa[j]​(2n), for all integers j,a≥1j,a\ge1j,a≥1;
  4. Theorem 5.16: for every C≥1C\ge1C≥1 there are a positive integer β\betaβ and a quantum polynomial-time sampler SSS such that for infinitely many nnn, with probability greater than 1/(8000n2)1/(8000n^2)1/(8000n2), S(1n)S(1^n)S(1n) outputs a pair of nnn-bit strings with μ(y∣x)>μ(⟨x,y⟩)−μ(x)+Clog⁡(∣x∣+∣y∣+2)\mu(y|x)>\mu(\langle x,y\rangle)-\mu(x)+C\log(|x|+|y|+2)μ(y∣x)>μ(⟨x,y⟩)−μ(x)+Clog(∣x∣+∣y∣+2), and every output of S(1n)S(1^n)S(1n) is ⟨0n,0n⟩\langle0^n,0^n\rangle⟨0n,0n⟩ or ⟨padn(P),padn(b)⟩\langle\mathrm{pad}_n(P),\mathrm{pad}_n(b)\rangle⟨padn​(P),padn​(b)⟩ with ∣P∣,∣b∣<n|P|,|b|<n∣P∣,∣b∣<n and ∣b∣≤β⌈log⁡(n+2)⌉|b|\le\beta\lceil\log(n+2)\rceil∣b∣≤β⌈log(n+2)⌉;
  5. Theorem 5.22: for every κ≥0\kappa\ge0κ≥0 there is η>0\eta>0η>0 such that infinitely many triples satisfy μ(y∣wx)>μ(xy∣w)−μ(x∣w)+η(∣x∣+∣y∣)+κlog⁡(∣w∣+∣x∣+∣y∣+2)\mu(y|wx)>\mu(xy|w)-\mu(x|w)+\eta(|x|+|y|)+\kappa\log(|w|+|x|+|y|+2)μ(y∣wx)>μ(xy∣w)−μ(x∣w)+η(∣x∣+∣y∣)+κlog(∣w∣+∣x∣+∣y∣+2);
  6. Corollary 5.24: for every κ≥0\kappa\ge0κ≥0 there is η>0\eta>0η>0 such that for infinitely many nnn there are x,y∈{0,1}nx,y\in\{0,1\}^nx,y∈{0,1}n and www with μ(x∣⟨y,w⟩)>μ(⟨x,y⟩∣w)−μ(y∣w)+ηn+κlog⁡(∣w∣+2n+2)\mu(x|\langle y,w\rangle)>\mu(\langle x,y\rangle|w)-\mu(y|w)+\eta n+\kappa\log(|w|+2n+2)μ(x∣⟨y,w⟩)>μ(⟨x,y⟩∣w)−μ(y∣w)+ηn+κlog(∣w∣+2n+2).

The transfer theorems D.38, F.3 and F.9 assert these with qKtU\mathrm{qKt}_UqKtU​ or qKt(c)\mathrm{qKt}^{(c)}qKt(c) in place of qKt\mathrm{qKt}qKt; at μ=qKt\mu=\mathrm{qKt}μ=qKt each is the paper's statement.

Formalization Note In Theorem 5.22, wxwxwx and xyxyxy are concatenations; in Corollary 5.24, ⟨y,w⟩\langle y,w\rangle⟨y,w⟩ and ⟨x,y⟩\langle x,y\rangle⟨x,y⟩ are pairs. "Every output" is every www of positive probability.

Definition code
import Mathlib
import Definitions.Def_QuantumKtSoI_pair
import Definitions.Def_QuantumKtSoI_Supplement_iterH
import Definitions.Def_QuantumKtSoI_Supplement_QSampler

open Classical

noncomputable section

namespace QuantumKtSoI.Supplement

/-! Statements of §5 for a conditional measure `µ`, where `µ y x` is `µ(y | x)` and `µ(y) = µ(y | ε)`
(Myrisiotis, STOC 2027 submission, held version sha256 6616571c…). With `µ = qKt` each is the
paper's statement; Theorems D.38 and F.9 assert them "with `qKt_U` in place of `qKt`". -/

/-- **Theorem 5.10** for `µ` (p.59): for every real `a ≥ 1`, infinitely many pairs `(x, y)` satisfy
`µ(y|x) − µ(⟨x,y⟩) + µ(x) > 2^{(log log(|x|+|y|+4))^a}`; in particular symmetry fails with every
fixed polylogarithmic error: for all reals `C, k`, some pair has
`µ(y|x) − µ(⟨x,y⟩) + µ(x) > C (log(|x|+|y|+2))^k`. -/
def Thm510For (μ : List Bool → List Bool → ℝ) : Prop :=
  (∀ a : ℝ, 1 ≤ a →
    {p : List Bool × List Bool |
      (2 : ℝ) ^ (Real.logb 2 (Real.logb 2 ((p.1.length : ℝ) + p.2.length + 4))) ^ a <
        μ p.2 p.1 - μ (pair p.1 p.2) [] + μ p.1 []}.Infinite) ∧
  ∀ C k : ℝ, ∃ x y : List Bool,
    C * Real.logb 2 ((x.length : ℝ) + y.length + 2) ^ k < μ y x - μ (pair x y) [] + μ x []

/-- **Corollary 5.13** for `µ` (p.61): for every real `a ≥ 1`, infinitely many integers `n` admit
`x, y ∈ {0,1}ⁿ` with `µ(y|x) − µ(⟨x,y⟩) + µ(x) > 2^{(log log(2n+4))^a}`. -/
def Cor513For (μ : List Bool → List Bool → ℝ) : Prop :=
  ∀ a : ℝ, 1 ≤ a → ∀ N : ℕ, ∃ n ≥ N, ∃ x y : List Bool, x.length = n ∧ y.length = n ∧
    (2 : ℝ) ^ (Real.logb 2 (Real.logb 2 (2 * (n : ℝ) + 4))) ^ a < μ y x - μ (pair x y) [] + μ x []

/-- **Corollary 5.15(ii)** for `µ` (p.63): for integers `j, a ≥ 1`, infinitely many pairs `(x, y)`
satisfy `µ(y|x) − µ(⟨x,y⟩) + µ(x) > F^{[j]}_a(|x| + |y|)`. -/
def Cor515iiFor (μ : List Bool → List Bool → ℝ) : Prop :=
  ∀ j a : ℕ, 1 ≤ j → 1 ≤ a →
    {p : List Bool × List Bool |
      (iterF j a (p.1.length + p.2.length) : ℝ) < μ p.2 p.1 - μ (pair p.1 p.2) [] + μ p.1 []}.Infinite

/-- **Corollary 5.15(iii)** for `µ` (p.63): for integers `j, a ≥ 1`, infinitely many integers `n`
admit `x, y ∈ {0,1}ⁿ` with `µ(y|x) − µ(⟨x,y⟩) + µ(x) > F^{[j]}_a(2n)`. -/
def Cor515iiiFor (μ : List Bool → List Bool → ℝ) : Prop :=
  ∀ j a : ℕ, 1 ≤ j → 1 ≤ a → ∀ N : ℕ, ∃ n ≥ N, ∃ x y : List Bool, x.length = n ∧ y.length = n ∧
    (iterF j a (2 * n) : ℝ) < μ y x - μ (pair x y) [] + μ x []

/-- **Theorem 5.16** for `µ` (p.65): for every constant `C ≥ 1` there are a positive integer `β` and
a quantum polynomial-time sampler `S` such that, for infinitely many `n`, with probability greater
than `1/(8000n²)` the output of `S(1ⁿ)` is a pair `⟨x, y⟩` of strings of length `n` with
`µ(y|x) > µ(⟨x,y⟩) − µ(x) + C log(|x|+|y|+2)`, and every output of `S(1ⁿ)` is `⟨0ⁿ, 0ⁿ⟩` or
`⟨pad_n(P), pad_n(b)⟩` for strings `P, b` with `|P|, |b| < n` and `|b| ≤ β⌈log(n+2)⌉`. -/
def Thm516For (μ : List Bool → List Bool → ℝ) : Prop :=
  ∀ C : ℝ, 1 ≤ C → ∃ β : ℕ, 0 < β ∧ ∃ S : QSampler,
    (∀ N : ℕ, ∃ n ≥ N, 1 / (8000 * (n : ℝ) ^ 2) <
      S.pairProb n fun x y =>
        μ (pair x y) [] - μ x [] + C * Real.logb 2 ((x.length : ℝ) + y.length + 2) < μ y x) ∧
    ∀ n : ℕ, ∀ w : List Bool, 0 < S.outProb n w →
      w = pair (List.replicate n false) (List.replicate n false) ∨
        ∃ P b : List Bool, P.length < n ∧ b.length < n ∧ b.length ≤ β * Nat.clog 2 (n + 2) ∧
          w = pair (pad n P) (pad n b)

/-- **Theorem 5.22** for `µ` (p.71): for every `κ ≥ 0` there is `η > 0` such that infinitely many
triples `(w, x, y)` satisfy
`µ(y|wx) > µ(xy|w) − µ(x|w) + η(|x|+|y|) + κ log(|w|+|x|+|y|+2)`, where `wx`, `xy` are
concatenations. -/
def Thm522For (μ : List Bool → List Bool → ℝ) : Prop :=
  ∀ κ : ℝ, 0 ≤ κ → ∃ η : ℝ, 0 < η ∧
    {t : List Bool × List Bool × List Bool |
      μ (t.2.1 ++ t.2.2) t.1 - μ 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) <
        μ t.2.2 (t.1 ++ t.2.1)}.Infinite

/-- **Corollary 5.24** for `µ` (p.74): for every `κ ≥ 0` there is `η > 0` such that, for infinitely
many integers `n`, there are `x, y ∈ {0,1}ⁿ` and `w ∈ {0,1}*` with
`µ(x|⟨y,w⟩) > µ(⟨x,y⟩|w) − µ(y|w) + ηn + κ log(|w|+2n+2)`. -/
def Cor524For (μ : List Bool → List Bool → ℝ) : Prop :=
  ∀ κ : ℝ, 0 ≤ κ → ∃ η : ℝ, 0 < η ∧ ∀ N : ℕ, ∃ n ≥ N, ∃ x y w : List Bool,
    x.length = n ∧ y.length = n ∧
      μ (pair x y) w - μ y w + η * n + κ * Real.logb 2 ((w.length : ℝ) + 2 * n + 2) < μ x (pair y w)

/-- The conclusion of **Theorem D.38** (p.184) for a measure `µ`: Theorems 5.10, 5.16 and 5.22,
Corollaries 5.13 and 5.24, and parts (ii) and (iii) of Corollary 5.15 hold with `µ` in place of
`qKt`, with the same scales and the same polynomial `p(n) = 8000n²`. -/
def SoIFailures (μ : List Bool → List Bool → ℝ) : Prop :=
  Thm510For μ ∧ Cor513For μ ∧ Cor515iiFor μ ∧ Cor515iiiFor μ ∧ Thm516For μ ∧ Thm522For μ ∧ Cor524For μ

end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem 5.10, p.59; Corollary 5.13, p.61; Corollary 5.15, p.63; Theorem 5.16, p.65; Theorem 5.22, p.71; Corollary 5.24, p.74

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me