Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem F.3, p.231 — robustness of the time charge: the main results hold for qKt(c)\mathrm{qKt}^{(c)}qKt(c)

Open
QuantumKtSoI.Supplement.theorem_F_3

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

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

Let c>0c>0c>0 be real, and let qKtϱ(c)(y∣x)=min⁡{∣e∣+c⌈log⁡t⌉:Pe(x;t,y)≥ϱ}\mathrm{qKt}^{(c)}_\varrho(y|x)=\min\{|e|+c\lceil\log t\rceil : P_e(x;t,y)\ge\varrho\}qKtϱ(c)​(y∣x)=min{∣e∣+c⌈logt⌉:Pe​(x;t,y)≥ϱ} with qKt(c)=qKt2/3(c)\mathrm{qKt}^{(c)}=\mathrm{qKt}^{(c)}_{2/3}qKt(c)=qKt2/3(c)​. The following results hold with qKt(c)\mathrm{qKt}^{(c)}qKt(c) in place of qKt\mathrm{qKt}qKt in their statements and in the definitions they use. The error scales, the clock family and the polynomial p(n)=8000n2p(n)=8000n^2p(n)=8000n2 of Theorem 5.16 are unchanged; every constant and every machine asserted to exist may depend on ccc.

  1. (a) Theorem 4.13 and Corollaries 4.14 and 4.15, with the lower threshold function written s0s_0s0​.
  2. (b), for rational ccc: Theorem 5.10 and Corollary 5.13.
  3. (c), for rational ccc: Theorem 5.16.
  4. (d), for rational ccc: Theorems 5.22 and 5.25 and Corollary 5.24.
  5. (e) Theorems A.1 and 8.3 and Propositions A.2 and 8.4.
  6. (f), for rational ccc: Theorem 6.14 and Corollary 6.15, with the absolute constant csymc_{\mathrm{sym}}csym​ replaced by a constant that depends only on ccc.
  7. For rational c<2c<2c<2: Theorem 7.3 holds for qKt(c)\mathrm{qKt}^{(c)}qKt(c) with the gap ⌊(1−c/2−η)λ⌋\lfloor(1-c/2-\eta)\lambda\rfloor⌊(1−c/2−η)λ⌋ for rational η∈(0,1−c/2)\eta\in(0,1-c/2)η∈(0,1−c/2) and the time bound 2εν2^{\varepsilon\nu}2εν, ε=η/(40max⁡(c,1))\varepsilon=\eta/(40\max(c,1))ε=η/(40max(c,1)) (Proposition G.1).

So the coefficient one of ⌈log⁡t⌉\lceil\log t\rceil⌈logt⌉ in the definition of qKt\mathrm{qKt}qKt is not essential to the main results.

Formalization Note Each restated result is a measure-parameterized proposition of the definition modules, instantiated at qKt(c)\mathrm{qKt}^{(c)}qKt(c) (and at qKtϱ(c)\mathrm{qKt}^{(c)}_\varrhoqKtϱ(c)​ for Corollary 4.15); at qKt\mathrm{qKt}qKt it is the paper's statement. "ccc rational" is c=qc=qc=q for a rational qqq.

Differences from the source:

  • generalization: the glue routines are fixed once and for all by their p.24 properties → every admissible glue routine set G (hypothesis G.Admissible); descriptions, P_e and qKt are those of G; reason: the proofs use only the p.24 properties and the paper's routines are one admissible set; same as the published base items
  • encoding: a machine of Definition 3.1 → a valid coded machine of the base mission (CodedMachine with Valid), halting on every branch by the floor of the stated deadline; reason: the base mission's representation of machines; halting within a time bound is all-branch and real deadlines are floors (p.22)
  • reading: the classical polynomial-time samplers of Theorems A.1, 8.3 and Propositions A.2, 8.4 → probabilistic Turing machines with an all-branch polynomial deadline (PolySampler, GSampler); reason: the reading of the published goal of the base mission
  • reading: Promise-BQTIME[n^{polylog(n)}] in Corollary 4.15 → for every integer a₀ ≥ 1 and constant C, no machine decides the problem in time C·n^{(log(n+2))^{a₀}}; reason: p.22: the family is {n^{(log(n+2))^a}} and deciding within O(T) is deciding within cT for a constant c
  • reading: Proposition G.1 for every g computable in time polynomial in the value of its argument; "an encoding", "decidable in time polynomial in N" and the oracle-free conventions of the restated results → the same pinned readings as in the items for Theorems 7.3, 8.3 and A.1 (PolyInValue, injective Enc, decision on input b(N)); reason: one reading per notion across the mission
  • encoding: E[T_x] and "halts with output 1 with probability" in Corollary 4.14 → E[T_x] = Σ_t (1 − Pr[T_x ≤ t]) in [0,∞] with Pr[T_x ≤ t] the weight of the halted branches; the halting probability is sup_t P_A(x; t, 1); reason: the paper's definitions on p.50 (a nondecreasing bounded sequence converges to its supremum)
Preamble
import Mathlib
import Definitions.Def_QuantumKtSoI_qKt
import Definitions.Def_QuantumKtSoI_Supplement_qKtChargeRho
import Definitions.Def_QuantumKtSoI_Supplement_Thm413For
import Definitions.Def_QuantumKtSoI_Supplement_SoIFailures
import Definitions.Def_QuantumKtSoI_Supplement_Thm525For
import Definitions.Def_QuantumKtSoI_Supplement_Thm83For
import Definitions.Def_QuantumKtSoI_Supplement_Thm614For

open Classical
Formal statement
namespace QuantumKtSoI.Supplement

/-- **Theorem F.3** (Robustness of the time charge; Myrisiotis, *Failure of Symmetry of Information for Quantum Computations*, STOC 2027 submission, held version sha256 6616571c…, p.231). Let `c > 0` be real; parts (b),
(c), (d) and (f) assume moreover that `c` is rational. The following results hold with `qKt^{(c)}`
in place of `qKt` in their statements and in the definitions they use; the error scales, the clock
family and the polynomial `p(n) = 8000n²` of Theorem 5.16 are unchanged, and every constant and
machine asserted to exist may depend on `c`.
(a) Theorem 4.13 and Corollaries 4.14 and 4.15 (lower threshold written `s₀`).
(b) Theorem 5.10 and Corollary 5.13.
(c) Theorem 5.16.
(d) Theorems 5.22 and 5.25 and Corollary 5.24.
(e) Theorems A.1 and 8.3 and Propositions A.2 and 8.4.
(f) Theorem 6.14 and Corollary 6.15, with `c_sym` replaced by a constant that depends only on `c`.
Theorem 7.3 holds for `qKt^{(c)}` whenever `c < 2` is rational, with the gap `⌊(1 − c/2 − η)λ⌋` for
rational `η ∈ (0, 1 − c/2)` and the time bound `2^{εν}`, `ε = η/(40 max(c,1))` (Proposition G.1).

**Formalization Note** `qKt^{(c)}` is the published `qKtCharge G c` (Definition 4.2, threshold
`2/3`), and `qKt^{(c)}_ϱ` is `qKtChargeRho G c ϱ` (used by Corollary 4.15 through Definition 4.11).
Each restated result is the measure-parameterized proposition of the definition modules (`…For`),
which at `µ = qKt` is the paper's statement. "`c` rational" is `c = q` for a rational `q`. The
constants of each restated result are quantified inside it, after `c` (and after the admissible
glue routine set `G`, p.24, fixed first as in the base mission). -/
theorem theorem_F_3 (G : GlueRoutines) (hG : G.Admissible) (c : ℝ) (hc : 0 < c) :
    (Thm413For (fun x => qKtCharge G c x []) ∧ Cor414For (fun x => qKtCharge G c x []) ∧
      Cor415For (fun ϱ w => qKtChargeRho G c ϱ w [])) ∧
    (ThmA1For (qKtCharge G c) ∧ Thm83For (qKtCharge G c) ∧ PropA2For (qKtCharge G c) ∧
      Prop84For (qKtCharge G c)) ∧
    ((∃ q : ℚ, c = (q : ℝ)) →
      (Thm510For (qKtCharge G c) ∧ Cor513For (qKtCharge G c)) ∧
      Thm516For (qKtCharge G c) ∧
      (Thm522For (qKtCharge G c) ∧ Thm525For (qKtCharge G c) ∧ Cor524For (qKtCharge G c)) ∧
      (Thm614For (qKtCharge G c) ∧ Cor615For (qKtCharge G c))) ∧
    ∀ q : ℚ, c = (q : ℝ) → c < 2 → PropG1For q (fun x => qKtCharge G c x []) := by sorry

end QuantumKtSoI.Supplement
Source
Myrisiotis, Failure of Symmetry of Information for Quantum Computations, STOC 2027 submission (held version, sha256 6616571c…), Theorem F.3, p.231; Definition 4.2, p.41; conventions for qKt^{(c)}, p.229; Proposition G.1, p.245

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