, and of §7.2 and §7.4
DefinitionQuantumKtSoI_Supplement_budcomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
For put
an upper bound on for . For a gap function ,
where is the length of the encoded queries with .
These are the budgets in the time and advice bounds of Theorem 7.10.
Formalization Note Truncated subtraction is the maximum with ; the maximum over the compatible lengths is a finite supremum, which is on the empty set.
Definition code
import Mathlib
import Definitions.Def_QuantumKtSoI_Supplement_query
namespace QuantumKtSoI.Supplement
/-- `B(λ) = λ + ⌊2 log(λ+1)⌋ + 7 + ⌈log(λ+1)⌉` (§7.2, p.104 of Myrisiotis, STOC 2027 submission,
held version sha256 6616571c…), an upper bound on `qKt(x)` for `x ∈ {0,1}^λ`. -/
noncomputable def Bnd (lam : ℕ) : ℕ :=
lam + ⌊2 * Real.logb 2 ((lam : ℝ) + 1)⌋₊ + 7 + Nat.clog 2 (lam + 1)
/-- `bud(λ) = max{0, B(λ) − g(λ)}` (p.110). Truncated subtraction is this maximum. -/
noncomputable def bud (g : ℕ → ℕ) (lam : ℕ) : ℕ := Bnd lam - g lam
/-- `b̂ud(N) = max({bud(ℓ) : ℓ ∈ ℕ, 1 ≤ ℓ ≤ N, ν(ℓ) = N} ∪ {0})` (p.110). -/
noncomputable def budHat (g : ℕ → ℕ) (N : ℕ) : ℕ :=
((Finset.Icc 1 N).filter fun l => nu l = N).sup (bud g)
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), p.104 (B); p.110 (bud, b̂ud)