Theorem 7 — two endpoints with different decoded labels
ProvedSpaceReset.Hardness.theorem_7dimension-boundsp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be finite-dimensional, . Let () act on with , and let be an isometry. Let have exactly preimages of every element, and let , be POVMs on , . Put
Let be states on with , and
Then
No relation between and and no rank or spectral assumption on the initializer is required. This robust two-time dimension bound is the converse engine of the space–discard frontier.
Differences from the source:
- encoding: ‖ρ_x‖_∞ ≤ 1/M → ρ_x ≤ (1/M)·I in the Loewner order, with 0 < M; reason: for positive semidefinite ρ_x the two are equivalent; 1/M presupposes M > 0
- encoding: f has exactly C = A/B preimages of every element → every fibre of f has size c with c·B = A; reason: same condition, stated without natural division
Preamble
import Mathlib import Definitions.Def_WildeQIT_traceNorm import Definitions.Def_SpaceReset_Hardness_Quantum set_option autoImplicit false open Matrix open scoped MatrixOrder ComplexOrder Kronecker
Formal statement
namespace SpaceReset.Hardness
/-- Theorem 7 (Two endpoints with different decoded labels), §2.3, pp. 13–14, eq. (6). -/
theorem theorem_7 {E₀ E₁ Y : Type} [Fintype E₀] [DecidableEq E₀] [Fintype E₁] [DecidableEq E₁]
[Fintype Y] [DecidableEq Y] (A B : ℕ) (M : ℝ) (hM : 0 < M)
(ξ : Fin A → Matrix E₀ E₀ ℂ) (hξ : ∀ x, (ξ x).PosSemidef) (hξ1 : ∑ x, (ξ x).trace = 1)
(V : Matrix (Y × E₁) E₀ ℂ) (hV : Vᴴ * V = 1)
(f : Fin A → Fin B) (hf : ∀ z : Fin B, (Finset.univ.filter (fun x => f x = z)).card * B = A)
(Ex : Fin A → Matrix E₀ E₀ ℂ) (hEx : IsPOVM Ex)
(Fz : Fin B → Matrix E₁ E₁ ℂ) (hFz : IsPOVM Fz)
(ρ : Fin A → Matrix Y Y ℂ) (hρ : ∀ x, IsDensity (ρ x))
(hρM : ∀ x, ρ x ≤ ((1 / M : ℝ) : ℂ) • (1 : Matrix Y Y ℂ)) :
let e₀ : ℝ := 1 - (∑ x, (Ex x * ξ x).trace).re
let e₁ : ℝ := 1 - (∑ x, (((1 : Matrix Y Y ℂ) ⊗ₖ Fz (f x)) * (V * ξ x * Vᴴ)).trace).re
let Ω : Matrix (Fin A × Y) (Fin A × Y) ℂ :=
fun p p' => if p.1 = p'.1 then ptraceRight (V * ξ p.1 * Vᴴ) p.2 p'.2 else 0
let τ : Matrix (Fin A × Y) (Fin A × Y) ℂ :=
fun p p' => if p.1 = p'.1 then ((1 : ℂ) / (A : ℂ)) * ρ p.1 p.2 p'.2 else 0
let δ : ℝ := WildeQIT.traceNorm (Ω - τ) / 2
Real.sqrt (Fintype.card E₀ * Fintype.card E₁) ≥
Real.sqrt (A * B * M) * max 0 (1 - (3 / 2) * δ - Real.sqrt e₀ - Real.sqrt e₁) := by sorry
end SpaceReset.Hardness
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), Theorem 7, §2.3, pp. 13–14 (eq. (6))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.