Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem B.1: total Λ\LambdaΛ-energy of 222- and 333-outcome POVMs is at least 1/81/81/8 and 1/29161/29161/2916

Open
QuantumCycleColoring.FourColor.Supplement.theorem_B_1

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

distributed-computingmatrix-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information

Let Λ∈CN×N\Lambda\in\mathbb C^{N\times N}Λ∈CN×N be PSD with ∥Λ∥F=1\|\Lambda\|_F=1∥Λ∥F​=1, and write EΛ(P)=Tr(ΛAΛB)\mathcal E_\Lambda(P)=\mathrm{Tr}(\Lambda A\Lambda B)EΛ​(P)=Tr(ΛAΛB) for the Λ\LambdaΛ-energy of a PSD operator PPP on CN⊗CN\mathbb C^N\otimes\mathbb C^NCN⊗CN, with A=TrA((Λ2⊗I)P)⊤A=\mathrm{Tr}_{\mathcal A}((\Lambda^2\otimes I)P)^\topA=TrA​((Λ2⊗I)P)⊤, B=TrB((I⊗Λˉ2)P)B=\mathrm{Tr}_{\mathcal B}((I\otimes\bar\Lambda^2)P)B=TrB​((I⊗Λˉ2)P). Fix q∈{2,3}q\in\{2,3\}q∈{2,3}. For every POVM {Pi}i∈[q]\{P_i\}_{i\in[q]}{Pi​}i∈[q]​ on CN⊗CN\mathbb C^N\otimes\mathbb C^NCN⊗CN,

∑i=1qEΛ(Pi) ≥ Cq,Cq={1/8,q=2,1/2916,q=3.\sum_{i=1}^{q}\mathcal E_\Lambda(P_i)\ \ge\ C_q,\qquad C_q=\begin{cases}1/8,& q=2,\\ 1/2916,& q=3.\end{cases}i=1∑q​EΛ​(Pi​) ≥ Cq​,Cq​={1/8,1/2916,​q=2,q=3.​

This is statement (Q1) of Theorem 6.1 for two and three colours with explicit constants, so one-way one-round quantum algorithms cannot colour directed cycles with at most three colours with high probability. The proof is operator-theoretic and independent of the bounded-dependence argument of §6.2.

Differences from the source:

  • encoding: Λ-energy E_Λ(P) = Tr(ΛAΛB), a complex trace that is real for PSD P, Λ → energy Λ P is the real part of this trace; reason: the trace is real for PSD P and Λ, so the values are the same
  • encoding: ℂ^N with its standard basis, operators on ℂ^N ⊗ ℂ^N → vectors indexed by an arbitrary finite type d (N = card d), operators are matrices indexed by d × d with the Kronecker product for ⊗; reason: relabelling the standard basis; the same instances
  • encoding: fix q ∈ {2, 3}, outcomes i = 1, …, q, constant C_q by cases → a conjunction of the q = 2 statement with constant 1/8 and the q = 3 statement with constant 1/2916, outcomes Fin q; reason: the two cases of the source, stated separately; the same instances
Preamble
import Mathlib
import Definitions.Def_FuchsVdGraaf_IsPOVM
import Definitions.Def_QuantumCycleColoring_FourColor_MatrixAnalysis

open scoped Kronecker ComplexOrder
Formal statement
namespace QuantumCycleColoring.FourColor.Supplement

open QuantumCycleColoring.FourColor Matrix

/-- Theorem B.1, p.53 (Gur–Li, STOC 2027 #515). Fix `q ∈ {2, 3}`. For every POVM `{P_i}_{i∈[q]}`
on `ℂ^N ⊗ ℂ^N` and every PSD `Λ` with `‖Λ‖_F = 1`, `∑_{i=1}^q E_Λ(P_i) ≥ C_q`, where
`C_2 = 1/8` and `C_3 = 1/2916`. -/
theorem theorem_B_1 {d : Type} [Fintype d] [DecidableEq d]
    (Λ : Matrix d d ℂ) (hΛ : Λ.PosSemidef) (hΛF : frobNorm Λ = 1) :
    (∀ P : Fin 2 → Matrix (d × d) (d × d) ℂ, FuchsVdGraaf.IsPOVM P →
      (1 / 8 : ℝ) ≤ ∑ i, energy Λ (P i)) ∧
    (∀ P : Fin 3 → Matrix (d × d) (d × d) ℂ, FuchsVdGraaf.IsPOVM P →
      (1 / 2916 : ℝ) ≤ ∑ i, energy Λ (P i)) := by sorry

end QuantumCycleColoring.FourColor.Supplement
Source
Tom Gur, Longcheng Li, STOC 2027 submission #515 (October 2026), Theorem B.1, p.53 (proof pp.53–54)

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