The gap problem (Definition 4.12) and its clipped thresholds
DefinitionQuantumKtSoI_Supplement_GapMqKtPcomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
For a measure of strings and , the promise problem has, on inputs of length ,
With this is Definition 4.12. Whenever a statement writes , the thresholds are the globally defined
which satisfy at every length.
The measure is a parameter because Appendix F uses the same definition with in place of .
Formalization Note The problem is returned as the pair of sets ; is real valued; truncated natural subtraction is .
Definition code
import Mathlib
namespace QuantumKtSoI.Supplement
/-- **Definition 4.12** (Gap problem, p.49), for a measure `µ` of strings: `Gap-MqKtP[c, s]` has
`YES_N = {x ∈ {0,1}^N : µ(x) ≤ c(N)}` and `NO_N = {x ∈ {0,1}^N : µ(x) > s(N)}`; the pair
`(YES, NO)` is returned. With `µ(x) = qKt(x)` this is the paper's problem; Appendix F uses the same
definition with `qKt^{(c)}` in place of `qKt`. -/
def GapMqKtP (μ : List Bool → ℝ) (c s : ℕ → ℕ) : Set (List Bool) × Set (List Bool) :=
({x | μ x ≤ c x.length}, {x | (s x.length : ℝ) < μ x})
/-- The clipped thresholds of p.49 used whenever a statement writes `Gap-MqKtP[c, N − 2]`:
`s_clip(N) = max(N − 2, 0)` and `c_clip(N) = min(c(N), s_clip(N))`; the problem
`Gap-MqKtP[c_clip, s_clip]` is returned.
**Formalization Note** `N - 2` is truncated natural subtraction, which is `max(N − 2, 0)`. -/
def GapMqKtPClip (μ : List Bool → ℝ) (c : ℕ → ℕ) : Set (List Bool) × Set (List Bool) :=
GapMqKtP μ (fun N => min (c N) (N - 2)) (fun N => N - 2)
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Definition 4.12 and the clipped thresholds, p.49