The statement of Theorem 5.25 for a conditional measure
DefinitionQuantumKtSoI_Supplement_Thm525Forcomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
For a real-valued conditional measure , reals , an integer and , the excluded separator is a machine with an integer such that for every pair of strings with : halts on within
steps, accepts with probability at least if , and rejects with probability at least if . Theorem 5.25 for says: for all and there is for which no such separator exists.
Theorems D.40 and F.3 assert this for measures other than .
Formalization Note Accepting is outputting the string and rejecting is outputting any other string; since has halted on every branch by the deadline, rejecting with probability at least is accepting with probability at most . The real deadline is a floor.
Definition code
import Mathlib
import Definitions.Def_QuantumKtSoI_pair
import Definitions.Def_QuantumKtSoI_CodedMachine
open Classical
noncomputable section
namespace QuantumKtSoI.Supplement
/-- The separator excluded by **Theorem 5.25** (p.75 of Myrisiotis, STOC 2027 submission, held
version sha256 6616571c…), for a conditional measure `µ` (`µ x w` is `µ(x | w)`): there is no machine
`A` with an integer `n_A` such that for every pair of strings `x, w` with `|x| ≥ n_A`, `A` halts on
`⟨x, w⟩` within `2^{η|x|}(|x|+|w|+2)^{c_A}` steps on every branch, accepts (outputs the string `1`)
with probability at least `2/3` if `µ(x|w) ≥ β|x|`, and rejects (outputs any other string) with
probability at least `2/3` if `µ(x|w) ≤ α|x|`.
**Formalization Note** The real deadline is read as `⌊·⌋` (p.22). Since `A` halts on every branch by
the deadline, its output probabilities there sum to one (Lemma 3.3(ii)), so rejecting with
probability at least `2/3` is accepting with probability at most `1/3`. -/
def NoSep (μ : List Bool → List Bool → ℝ) (α β : ℝ) (cA : ℕ) (η : ℝ) : Prop :=
¬∃ A : CodedMachine, A.Valid ∧ ∃ nA : ℕ, ∀ x w : List Bool, nA ≤ x.length →
A.toMachine.HaltsWithin (pair x w)
⌊(2 : ℝ) ^ (η * x.length) * ((x.length : ℝ) + w.length + 2) ^ cA⌋₊ ∧
(β * x.length ≤ μ x w → (2 / 3 : ℝ) ≤ A.toMachine.outputProb (pair x w)
⌊(2 : ℝ) ^ (η * x.length) * ((x.length : ℝ) + w.length + 2) ^ cA⌋₊ [true]) ∧
(μ x w ≤ α * x.length → A.toMachine.outputProb (pair x w)
⌊(2 : ℝ) ^ (η * x.length) * ((x.length : ℝ) + w.length + 2) ^ cA⌋₊ [true] ≤ 1 / 3)
/-- **Theorem 5.25** for `µ` (p.75): for all reals `0 < α < β < 1` and every integer `c_A ≥ 1` there
is `η > 0` with `NoSep µ α β c_A η`. -/
def Thm525For (μ : List Bool → List Bool → ℝ) : Prop :=
∀ α β : ℝ, 0 < α → α < β → β < 1 → ∀ cA : ℕ, 1 ≤ cA → ∃ η : ℝ, 0 < η ∧ NoSep μ α β cA η
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem 5.25, p.75