Encoded queries , consistency with a gap, , and deciding infinitely often (§6.6, §7)
DefinitionQuantumKtSoI_Supplement_querycomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
For let . For and an integer the encoded query is
where is the binary expansion of padded with leading zeros to length ; its length depends only on .
For a measure of strings and :
- a language is consistent with the gap if for all , and , whenever and whenever ;
- ;
- a machine decides infinitely often in time if there are infinitely many such that on every input with it halts within steps and outputs with probability at least if and at most otherwise;
- solves the gap- promise problem at length in time if on every such input it halts within steps and outputs with probability at least when and at most when .
With these are the paper's definitions; Appendix F uses them with .
Formalization Note is computed at , . Halting is on every branch and real deadlines are floors (p.22). "Infinitely many " is: for every some .
Definition code
import Mathlib
import Definitions.Def_QuantumKtSoI_pair
import Definitions.Def_QuantumKtSoI_CodedMachine
open Classical
noncomputable section
namespace QuantumKtSoI.Supplement
/-- The threshold width `wd(λ) = ⌈log(4λ + 40)⌉` (§6.6, p.96 of Myrisiotis, STOC 2027 submission,
held version sha256 6616571c…). -/
def wd (lam : ℕ) : ℕ := Nat.clog 2 (4 * lam + 40)
/-- `bin_k(s)`: the binary expansion of `s`, padded with leading zeros to length `k` (p.96). -/
def binPad (k s : ℕ) : List Bool := List.replicate (k - (bin s).length) false ++ bin s
/-- The **encoded query** `q(x, s) = ⟨x, bin_{wd(λ)}(s)⟩` for `x ∈ {0,1}^λ` (p.96). -/
def query (x : List Bool) (s : ℕ) : List Bool := pair x (binPad (wd x.length) s)
/-- The query length `ν(λ) = |q(x, s)|`, which depends only on `λ` (p.96); computed at
`x = 0^λ`, `s = 0`. -/
def nu (lam : ℕ) : ℕ := (query (List.replicate lam false) 0).length
/-- A language `L` is **consistent with the gap** `g` for a measure `µ` of strings (p.96; p.229 for
`qKt^{(c)}`): for all `λ ≥ 1`, `x ∈ {0,1}^λ` and `0 ≤ s < 2^{wd(λ)}`, `q(x, s) ∈ L` whenever
`µ(x) ≤ s`, and `q(x, s) ∉ L` whenever `µ(x) > s + g(λ)`. -/
def ConsistentGap (μ : List Bool → ℝ) (g : ℕ → ℕ) (L : Set (List Bool)) : Prop :=
∀ x : List Bool, 1 ≤ x.length → ∀ s : ℕ, s < 2 ^ wd x.length →
(μ x ≤ s → query x s ∈ L) ∧ ((s : ℝ) + g x.length < μ x → query x s ∉ L)
/-- `L_thr = {q(x, s) : µ(x) ≤ s}` (p.98), over valid queries (`|x| ≥ 1`, `s < 2^{wd(|x|)}`). -/
def Lthr (μ : List Bool → ℝ) : Set (List Bool) :=
{q | ∃ x : List Bool, ∃ s : ℕ, 1 ≤ x.length ∧ s < 2 ^ wd x.length ∧ q = query x s ∧ μ x ≤ s}
/-- A machine `A` **decides `L` infinitely often in time `2^{εν}`** (p.98): there are infinitely many
`λ` such that, on every input `q(x, s)` with `x ∈ {0,1}^λ` (and `0 ≤ s < 2^{wd(λ)}`), `A` halts within
`2^{εν(λ)}` steps on every branch and outputs `1` with probability at least `2/3` if `q(x, s) ∈ L`
and at most `1/3` otherwise.
**Formalization Note** The real deadline is `⌊2^{εν(λ)}⌋` (p.22); "infinitely many `λ`" is
`∀ N, ∃ λ ≥ N` with `λ ≥ 1`. -/
def DecidesIO (A : CodedMachine) (L : Set (List Bool)) (ε : ℝ) : Prop :=
∀ N : ℕ, ∃ lam : ℕ, N ≤ lam ∧ 1 ≤ lam ∧ ∀ x : List Bool, x.length = lam → ∀ s : ℕ,
s < 2 ^ wd lam →
A.toMachine.HaltsWithin (query x s) ⌊(2 : ℝ) ^ (ε * nu lam)⌋₊ ∧
(query x s ∈ L → (2 / 3 : ℝ) ≤ A.toMachine.outputProb (query x s) ⌊(2 : ℝ) ^ (ε * nu lam)⌋₊ [true]) ∧
(query x s ∉ L → A.toMachine.outputProb (query x s) ⌊(2 : ℝ) ^ (ε * nu lam)⌋₊ [true] ≤ 1 / 3)
/-- `A` **solves the gap-`g` promise problem at length `λ` in time `T`** (p.96): on every input
`q(x, s)` with `x ∈ {0,1}^λ` and `0 ≤ s < 2^{wd(λ)}` it halts within `T` steps on every branch,
outputs `1` with probability at least `2/3` when `µ(x) ≤ s` and at most `1/3` when
`µ(x) > s + g(λ)`. No condition is imposed when `s < µ(x) ≤ s + g(λ)`. The real deadline is
`⌊T⌋`. -/
def SolvesGapAt (μ : List Bool → ℝ) (A : CodedMachine) (g : ℕ → ℕ) (lam : ℕ) (T : ℝ) : Prop :=
∀ x : List Bool, x.length = lam → ∀ s : ℕ, s < 2 ^ wd lam →
A.toMachine.HaltsWithin (query x s) ⌊T⌋₊ ∧
(μ x ≤ s → (2 / 3 : ℝ) ≤ A.toMachine.outputProb (query x s) ⌊T⌋₊ [true]) ∧
((s : ℝ) + g lam < μ x → A.toMachine.outputProb (query x s) ⌊T⌋₊ [true] ≤ 1 / 3)
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), §6.6, p.96; §7, p.98; p.229 (for qKt^{(c)})