The clocks , and of §4.5
DefinitionQuantumKtSoI_Supplement_Hacomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
For integers and put
All three are nondecreasing and integer valued, and . For the clock eventually exceeds every fixed quasipolynomial , while .
These are the explicit time bounds at which the gap lower bound (Theorem 4.13) and the worst-case symmetry failure (Theorem 5.10) are stated.
Formalization Note Logarithms are base and is Nat.clog 2 m, exact for integers .
Definition code
import Mathlib
namespace QuantumKtSoI.Supplement
/-- `Λ₂(N) = ⌈log(⌈log(N+4)⌉)⌉` (§4.5, p.48 of Myrisiotis, *Failure of Symmetry of Information
for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…).
**Formalization Note** `⌈log₂ m⌉` is `Nat.clog 2 m`, exact for every integer `m ≥ 1`; both
arguments here are at least `2`. -/
def Lam2 (N : ℕ) : ℕ := Nat.clog 2 (Nat.clog 2 (N + 4))
/-- `F_a(N) = 2^{Λ₂(N)^a}` (§4.5, p.48). -/
def Fa (a N : ℕ) : ℕ := 2 ^ (Lam2 N ^ a)
/-- The clock `H_a(N) = 2^{F_a(N)}` (§4.5, p.48), for integers `N ≥ 0` and `a ≥ 1`. -/
def Ha (a N : ℕ) : ℕ := 2 ^ Fa a N
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), §4.5, p.48