Theorem B.1: total -energy of - and -outcome POVMs is at least and
OpenQuantumCycleColoring.FourColor.Supplement.theorem_B_1distributed-computingmatrix-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be PSD with , and write for the -energy of a PSD operator on , with , . Fix . For every POVM on ,
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)