Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Encoded queries q(x,s)q(x,s)q(x,s), consistency with a gap, LthrL_{\mathrm{thr}}Lthr​, and deciding infinitely often (§6.6, §7)

Definition
QuantumKtSoI_Supplement_query

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

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

For λ≥1\lambda\ge1λ≥1 let wd(λ)=⌈log⁡(4λ+40)⌉\mathrm{wd}(\lambda)=\lceil\log(4\lambda+40)\rceilwd(λ)=⌈log(4λ+40)⌉. For x∈{0,1}λx\in\{0,1\}^\lambdax∈{0,1}λ and an integer 0≤s<2wd(λ)0\le s<2^{\mathrm{wd}(\lambda)}0≤s<2wd(λ) the encoded query is

q(x,s)=⟨x,binwd(λ)(s)⟩,q(x,s)=\langle x,\mathrm{bin}_{\mathrm{wd}(\lambda)}(s)\rangle ,q(x,s)=⟨x,binwd(λ)​(s)⟩,

where bink(s)\mathrm{bin}_k(s)bink​(s) is the binary expansion of sss padded with leading zeros to length kkk; its length ν(λ)\nu(\lambda)ν(λ) depends only on λ\lambdaλ.

For a measure μ\muμ of strings and g:N→Ng:\mathbb N\to\mathbb Ng:N→N:

  1. a language LLL is consistent with the gap ggg if for all λ≥1\lambda\ge1λ≥1, x∈{0,1}λx\in\{0,1\}^\lambdax∈{0,1}λ and 0≤s<2wd(λ)0\le s<2^{\mathrm{wd}(\lambda)}0≤s<2wd(λ), q(x,s)∈Lq(x,s)\in Lq(x,s)∈L whenever μ(x)≤s\mu(x)\le sμ(x)≤s and q(x,s)∉Lq(x,s)\notin Lq(x,s)∈/L whenever μ(x)>s+g(λ)\mu(x)>s+g(\lambda)μ(x)>s+g(λ);
  2. Lthr={q(x,s):μ(x)≤s}L_{\mathrm{thr}}=\{q(x,s):\mu(x)\le s\}Lthr​={q(x,s):μ(x)≤s};
  3. a machine AAA decides LLL infinitely often in time 2εν2^{\varepsilon\nu}2εν if there are infinitely many λ\lambdaλ such that on every input q(x,s)q(x,s)q(x,s) with x∈{0,1}λx\in\{0,1\}^\lambdax∈{0,1}λ it halts within 2εν(λ)2^{\varepsilon\nu(\lambda)}2εν(λ) steps and outputs 111 with probability at least 2/32/32/3 if q(x,s)∈Lq(x,s)\in Lq(x,s)∈L and at most 1/31/31/3 otherwise;
  4. AAA solves the gap-ggg promise problem at length λ\lambdaλ in time TTT if on every such input it halts within TTT steps and outputs 111 with probability at least 2/32/32/3 when μ(x)≤s\mu(x)\le sμ(x)≤s and at most 1/31/31/3 when μ(x)>s+g(λ)\mu(x)>s+g(\lambda)μ(x)>s+g(λ).

With μ=qKt\mu=\mathrm{qKt}μ=qKt these are the paper's definitions; Appendix F uses them with qKt(c)\mathrm{qKt}^{(c)}qKt(c).

Formalization Note ν(λ)\nu(\lambda)ν(λ) is computed at x=0λx=0^\lambdax=0λ, s=0s=0s=0. Halting is on every branch and real deadlines are floors (p.22). "Infinitely many λ\lambdaλ" is: for every NNN some λ≥N\lambda\ge Nλ≥N.

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)})

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