Theorem 6.1: a uniform -energy bound for -outcome POVMs is equivalent to the impossibility of -colouring cycles
OpenQuantumCycleColoring.FourColor.Supplement.theorem_6_1distributed-computingmatrix-analysisp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Fix an integer . For a PSD matrix and a PSD operator on , write for the -energy, where and . The following two statements are equivalent.
- (Q1) There is a constant such that for every local dimension , every PSD with and every -outcome POVM on ,
- (Q2) No one-way one-round anonymous quantum algorithm -colours directed cycles with high probability: for every algorithm family (a state on finite registers and a -outcome POVM on for each cycle length , the same at every node), there are no constants and with for all .
The constant depends on alone. The success probability in (Q2) is the Born-rule probability of the -node experiment, defined independently of the energy. The theorem reduces the distributed impossibility question for every number of colours to a single inequality about POVMs, the form in which the four-colour case is attacked.
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, colours [q] → vectors indexed by an arbitrary finite type d (N = card d), matrices indexed by d × d with the Kronecker product for ⊗, colours Fin q; reason: relabelling of bases and colours; the same instances
- reading: "succeeds with high probability", i.e. with probability at least 1 − 1/poly(n) (Definition 3.8, p.19) → there are real A > 0, k > 0 and a threshold n₀ ≥ 3 with success probability ≥ 1 − A/n^k for every n ≥ n₀; reason: 1/poly(n) read as an inverse-polynomial failure bound fixed before n; the proof's construction (success ≥ 1 − 1/n, p.42) meets it and the forward bound (1 − C_q)^⌊n/3⌋ → 0 (p.41) excludes it
- reading: a one-way one-round anonymous quantum algorithm (Definition 3.10; nodes know n, unbounded finite local computation) → a family giving, for each cycle length n, finite kept and message registers, a density matrix on them and a q-outcome POVM on (received message, kept register), identical at every node, with no computability requirement on n ↦ data; reason: this is the general finite-dimensional form used in the proof on p.41 (randomness and workspace absorbed), and n-dependence is allowed because nodes know n; footnote 10 shows the converse algorithm can be taken uniform, so the equivalence holds under either reading of uniformity
- encoding: cycle lengths n ≥ 3 → n = m + 3 with m : ℕ; reason: the same lengths, and ZMod (m + 3) needs no nonzero side condition
Preamble
import Mathlib import Definitions.Def_FuchsVdGraaf_IsPOVM import Definitions.Def_QuantumCycleColoring_FourColor_MatrixAnalysis import Definitions.Def_QuantumCycleColoring_FourColor_CycleAlgorithm import Definitions.Def_QuantumCycleColoring_FourColor_Supplement_AlgorithmFamily open scoped Kronecker ComplexOrder
Formal statement
namespace QuantumCycleColoring.FourColor.Supplement
open QuantumCycleColoring.FourColor Matrix
/-- Theorem 6.1, pp.40–41 (Gur–Li, STOC 2027 #515). For every fixed integer `q ≥ 2` the
following are equivalent:
(Q1) there is a constant `C_q > 0` such that for every finite local dimension, every PSD `Λ`
with `‖Λ‖_F = 1` and every `q`-outcome POVM `{P_i}` on `ℂ^N ⊗ ℂ^N`, `∑_i E_Λ(P_i) ≥ C_q`;
(Q2) no one-way one-round anonymous quantum algorithm `q`-colours directed cycles with high
probability (success probability `≥ 1 − A/n^k` for some `A, k > 0` and all large `n`). -/
theorem theorem_6_1 (q : ℕ) (hq : 2 ≤ q) :
(∃ C : ℝ, 0 < C ∧
∀ (d : Type) [Fintype d] [DecidableEq d] (Λ : Matrix d d ℂ), Λ.PosSemidef →
frobNorm Λ = 1 →
∀ (P : Fin q → Matrix (d × d) (d × d) ℂ), FuchsVdGraaf.IsPOVM P →
C ≤ ∑ i, energy Λ (P i)) ↔
(∀ F : AlgorithmFamily q, ¬ F.SolvesWHP) := by sorry
end QuantumCycleColoring.FourColor.Supplement
Source
Tom Gur, Longcheng Li, STOC 2027 submission #515 (October 2026), Theorem 6.1, pp.40–41 (proof pp.41–42, footnote 10 p.42); model: Definitions 3.8–3.10, pp.19–20