Theorem 5.16, p.65 — for every a quantum polynomial-time sampler violates symmetry with error with probability above
OpenQuantumKtSoI.Supplement.theorem_5_16complexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1quantum-computing
For every constant there are a positive integer , depending only on , and a quantum polynomial-time sampler such that:
- for infinitely many , with probability greater than the output of is a pair of strings of length with
- every output of is either or for strings with and , where .
So symmetry of information for does not hold on average with error , with the same polynomial for every .
A quantum polynomial-time sampler is a machine with a polynomial all-branch deadline on ; an output that is not a pair of -bit strings is outside the event.
Formalization Note "Every output" is every string of positive output probability at the deadline.
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 quantum polynomial-time sampler: a machine S and a polynomial q_S → a valid coded machine with all-branch deadline c(n+2)^k on 1ⁿ (QSampler); reason: every polynomial is bounded by one of this form and the output law does not change after all branches have halted
- encoding: "a polynomial p positive for all large n … One may take p(n) = 8000n² for every C" → stated with p(n) = 8000n²; reason: the paper's own strongest form; it implies the existence of p
Preamble
import Mathlib import Definitions.Def_QuantumKtSoI_qKt import Definitions.Def_QuantumKtSoI_Supplement_QSampler open Classical
Formal statement
namespace QuantumKtSoI.Supplement
/-- **Theorem 5.16** (Failure of symmetry of information on average; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.65). For every
constant `C ≥ 1`, symmetry of information for qKt does not hold on average with error `C log`: there
are a quantum polynomial-time sampler `S` and the polynomial `p(n) = 8000n²` (the same for every
`C`) such that, for infinitely many `n`, with probability greater than `1/p(n)` the output of
`S(1ⁿ)` is a pair `⟨x, y⟩` of strings of length `n` with
`qKt(y|x) > qKt(⟨x,y⟩) − qKt(x) + C log(|x|+|y|+2)`. Moreover `S` is chosen together with a positive
integer `β` depending only on `C` so that every output of `S(1ⁿ)` is either `⟨0ⁿ, 0ⁿ⟩` or
`⟨pad_n(P), pad_n(b)⟩` for strings `P, b` with `|P|, |b| < n` and `|b| ≤ β⌈log(n+2)⌉`.
**Formalization Note** `G` is any admissible glue routine set (p.24). The sampler is a `QSampler`
(valid coded machine with an all-branch deadline `c(n+2)^k` on `1ⁿ`, p.51); `S.pairProb` is the
probability that the output is `⟨x,y⟩ = xy` with `x, y ∈ {0,1}ⁿ` and the event; "every output" is
every `w` with `P_S(1ⁿ; q_S(n), w) > 0`. Quantifier order: `∀ C, ∃ β, ∃ S`. -/
theorem theorem_5_16 (G : GlueRoutines) (hG : G.Admissible) :
∀ C : ℝ, 1 ≤ C → ∃ β : ℕ, 0 < β ∧ ∃ S : QSampler,
(∀ N : ℕ, ∃ n ≥ N, 1 / (8000 * (n : ℝ) ^ 2) <
S.pairProb n fun x y =>
(qKt G (pair x y) [] : ℝ) - qKt G x [] + C * Real.logb 2 ((x.length : ℝ) + y.length + 2) <
qKt G 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) := by sorry
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem 5.16, p.65; samplers and Definition 5.1, p.51; pad, p.60