Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6 — global rank benchmark

Proved
SpaceReset.Hardness.lemma_6

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information

Let G∈F2k×nG\in\mathbb F_2^{k\times n}G∈F2k×n​ have full row rank, and let a Definition 4 implementation with memory budget qqq, discard budget ggg and initial memory rank rrr realize either output contract within error ε\varepsilonε. Then

2q+g r ≥ (1−ε) 2k.2^{q+g}\,r\ \ge\ (1-\varepsilon)\,2^k .2q+gr ≥ (1−ε)2k.

For ε<1/2\varepsilon<1/2ε<1/2 this gives 2q+g≥k2q+g\ge k2q+g≥k for any (mixed) initialization and q+g≥kq+g\ge kq+g≥k 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
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

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