Theorem 1.5 — -uniform Clifford+T strategies give
OpenFRouting.Supplement.theorem_1_5f-routingp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-position-verification
There are universal constants and with the following property. Let be nondecreasing and time-constructible with , let be arbitrary, and let with . If some -uniform Clifford+T -routing strategy on qubits is -correct on every input at every input length , for one with , then the language satisfies
the bound at input length being .
Correctness is measured by the root fidelity of the verifier's tested qubits with the EPR pair. Compared with the general goal (Theorem 5.2, ), the Clifford+T restriction gives a deterministic bound that is exponential only in the number of magic gates.
Differences from the source:
- reading: a (𝒯, t)-uniform Clifford+T strategy (stated in the overview) → qubit strategies, d = 2; reason: p.5: "we focus on d = 2 in this overview"; the general-d form is Corollary 6.4, which is not a theorem of the paper
- reading: Clifford+T circuits and magic gates (no gate list) → gates {H, S, CNOT, T}, magic count = number of T gates; reason: the standard Clifford+T set; T† = S³T costs one magic gate as usual
- generalization: five fixed uniform generator machines, including unrestricted-time post-communication generators → the resource and pre-communication generators are machines while the post-communication channels are arbitrary; reason: the proof never runs the post generators, and every source strategy specializes by forgetting them
- encoding: DTIME and circuit-running time (standard models left implicit) → the published binary-string machine model with exact output bits, explicit circuit size and width bounds, and budget max(1, 𝒯(n)); reason: fixed standard models and the length-zero convention, changing no positive-time instance
- encoding: f ∈ DTIME((𝒯2^t)^c), 𝒯 and t functions of n = |x| → L_f ∈ DTIME(m ↦ (𝒯(⌊m/2⌋)·2^{t(⌊m/2⌋)})^c) on input length m; reason: |x ∘ y| = 2n; the base mission's convention (theorem_5_2), with the time budget max(1, ·)
- encoding: c ≥ 1 a real constant → c a natural number ≥ 1; reason: the base 𝒯·2^t is 0 or ≥ 1, so a real exponent can be replaced by its ceiling
Preamble
import Definitions.Def_FRouting_Supplement_UniformCTStrategy import Definitions.Def_FRouting_Supplement_InDTIME set_option autoImplicit false
Formal statement
namespace FRouting.Supplement
/-- **Theorem 1.5 — security against `(𝒯, t)`-uniform Clifford+T strategies.** Renard, *Computational
Bounds for f-Routing*, arXiv:2609.40278 (held copy, sha256 4a327f29…), Theorem 1.5, p.5: "There exist
universal constants ε₀ > 0 and c ≥ 1 such that if a (𝒯, t)-uniform Clifford+T f-routing strategy is
(1 − ε)-correct on every input at every input length for some 0 ≤ ε ≤ ε₀, then f ∈ DTIME((𝒯2ᵗ)ᶜ)."
**Formalization Note** Qubit strategies (`d = 2`): p.5 says "we focus on d = 2 in this overview".
`c` and `ε₀` come before `𝒯, t, f` and the strategy; `ε` is one number for all `n`. `𝒯` is as in
Definition 1.2 (time-constructible, nondecreasing, `𝒯(n) ≥ n`), exactly as in the published goal
`FRouting.theorem_5_2`; `t` has no hypothesis. `f ∈ DTIME(B)` means `L_f ∈ DTIME(B)`, and on input length
`m` of `L_f` the bound is taken at `n = m/2` (`|x ∘ y| = 2n`), the base mission's convention. -/
theorem theorem_1_5 :
∃ (c : ℕ) (ε₀ : ℝ), 1 ≤ c ∧ 0 < ε₀ ∧
∀ (T t : ℕ → ℕ), IsTimeConstructible T → Monotone T → (∀ n, n ≤ T n) →
∀ (f : ∀ n, (Fin n → Bool) → (Fin n → Bool) → Bool) (S : UniformCTStrategy T t) (ε : ℝ),
0 ≤ ε → ε ≤ ε₀ → (∀ n x y, (S.toRouting n).IsCorrectOn (f n) ε x y) →
InDTIME (languageOf f) (fun m => (T (m / 2) * 2 ^ t (m / 2)) ^ c) := by sorry
end FRouting.Supplement
Source
Renard, Computational Bounds for f-Routing, arXiv:2609.40278 (held copy, sha256 4a327f29…), Theorem 1.5, p.5 (Definition 6.1, p.23)