The charged measure at a general threshold (Definition 4.2)
DefinitionQuantumKtSoI_Supplement_qKtChargeRhocomplexity-theorykolmogorov-complexityp2o-gran-per-chapterp2o-plan-bookp2o-v1quantum-computing
For a real , a real and strings ,
with . The minimum exists, since below any feasible cost the costs take finitely many values.
The threshold form is needed for Definition 4.11 with in place of , which Theorem F.3(a) uses through Corollary 4.15.
Formalization Note The base mission publishes the case as qKtCharge; this is the same infimum with the threshold as a parameter, and the two agree at by definition.
Definition code
import Mathlib
import Definitions.Def_QuantumKtSoI_qKt
open Classical
noncomputable section
namespace QuantumKtSoI.Supplement
/-- **Definition 4.2** (Charge `c`, p.41 of Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…) at a general threshold `ϱ ∈ (0, 1]`:
`qKt^{(c)}_ϱ(y | x) = min_{e,t} { |e| + c⌈log t⌉ : e ∈ E, t ≥ 1, P_e(x; t, y) ≥ ϱ }` for real `c > 0`.
The published `qKtCharge G c` is the case `ϱ = 2/3`.
**Formalization Note** As for the published `qKtCharge`: the minimum is the `sInf` of a set of reals
that is nonempty (by `LIT(y)`) and bounded below by `0`, and it is attained (p.41). -/
def qKtChargeRho (G : GlueRoutines) (c ϱ : ℝ) (y x : List Bool) : ℝ :=
sInf {v : ℝ | ∃ e : Desc, ∃ t : ℕ, 1 ≤ t ∧ ϱ ≤ e.prob G x t y ∧
v = (e.bits.length : ℝ) + c * (Nat.clog 2 t : ℝ)}
end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Definition 4.2, p.41