Lemma 6 — global rank benchmark
ProvedSpaceReset.Hardness.lemma_6p2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let have full row rank, and let a Definition 4 implementation with memory budget , discard budget and initial memory rank realize either output contract within error . Then
For this gives for any (mixed) initialization and for pure initialization.
This is the output-rank inequality behind the third term of the initial-rank frontier.
Differences from the source:
- encoding: Definition 4 online circuit: memory of dimension at most 2^q, fresh pure ancillas, a unitary and discarded systems of total dimension at most 2^g → DiscardDevice: one memory type M with |M| ≤ 2^q, a Stinespring isometry V_j : carrier⊗M → carrier⊗M⊗E_j per slot, and ∏_j |E_j| ≤ 2^g; reason: an isometry is exactly pure ancilla + unitary + discard; a memory of smaller dimension at some cut embeds isometrically into M with no extra discard; same class of realizations
- encoding: d_op = sup over adaptive testers with a quantum reference of the trace distance of final states (5); code state: trace distance of the joint returned state → ErrorLE: for every valid tester (one reference system R, initial state, a channel after each slot) the trace distance is ≤ ε; code state via the blank-input experiment that stores every returned carrier; reason: 'sup ≤ ε' is the same as 'every tester ≤ ε'; references of varying dimension embed into one R isometrically; the blank tester returns exactly the joint emitted state
Preamble
import Mathlib import Definitions.Def_SpaceReset_Hardness_DiscardDevice set_option autoImplicit false
Formal statement
namespace SpaceReset.Hardness
/-- Lemma 6 (Global rank benchmark), p. 13. -/
theorem lemma_6 {k n : ℕ} (G : Matrix (Fin k) (Fin n) F2) (hG : FullRowRank G)
(q g : ℕ) (D : DiscardDevice n q g) (c : Contract) (ε : ℝ)
(hD : ErrorLE G c D.toProcess ε) :
(2 : ℝ) ^ (q + g) * (D.σ.rank : ℝ) ≥ (1 - ε) * (2 : ℝ) ^ k ∧
(ε < 1 / 2 → k ≤ 2 * q + g) ∧
(ε < 1 / 2 → D.PureInit → k ≤ q + g) := by sorry
end SpaceReset.Hardness
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), Lemma 6, §2.2, p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.