Cycle-length families of one-way one-round quantum algorithms and success with high probability
DefinitionQuantumCycleColoring_FourColor_Supplement_AlgorithmFamilydistributed-computingp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Fix a number of colours . In a one-way one-round anonymous quantum algorithm on the directed -cycle (), every node prepares the same state on a kept register and a message register , sends to its successor, and measures the same -outcome POVM on the received register and its own, , outputting a colour . Since every node knows , the algorithm may choose its data as a function of .
- An algorithm family assigns to every cycle length finite registers , , a density matrix (PSD, trace one) on , and a POVM on . Private randomness, workspace and intermediate measurements are absorbed into the mixed state and the final POVM.
- Its success probability on the -cycle, , is the Born-rule probability that the outputs form a proper -colouring, computed from the published output law of the mission.
- The family succeeds with high probability if there are constants and and a threshold such that
i.e. it fails with probability at most .
This is the solvability notion in statement (Q2) of Theorem 6.1: (Q2) says that no family succeeds with high probability.
Formalization Note Cycle lengths are written , so the threshold is . The data for are present in the structure but never used. The exponent is a positive real number, and is the real power.
Definition code
import Mathlib
import Definitions.Def_FuchsVdGraaf_IsPOVM
import Definitions.Def_QuantumCycleColoring_FourColor_MatrixAnalysis
import Definitions.Def_QuantumCycleColoring_FourColor_CycleAlgorithm
open scoped ComplexOrder
/-!
# Cycle-length families of one-way one-round algorithms and high-probability success
Tom Gur, Longcheng Li, *Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space
Stability*, STOC 2027 submission #515 (October 2026), Definitions 3.8–3.10 (pp.19–20) and
Theorem 6.1 (Q2), pp.40–42 with footnote 10.
Every node knows the cycle length `n` (Definition 3.8), so an algorithm may choose its finite
kept register `a n`, message register `b n`, prepared state `ρ n` and `q`-outcome POVM `P n` as a
function of `n`. Its output law on the directed `n`-cycle is the published Born-rule law
`properColoringProb`. Success with high probability (p.19) means success probability at least
`1 − 1/poly(n)`: here, at least `1 − A / n^k` for fixed `A > 0`, `k > 0` and all large `n`.
-/
namespace QuantumCycleColoring.FourColor.Supplement
open QuantumCycleColoring.FourColor Matrix
/-- Definitions 3.8–3.10, pp.19–20: a one-way one-round anonymous quantum algorithm for
`q`-colouring directed cycles, given for every cycle length `n` (the nodes know `n`): finite kept
and message registers `a n`, `b n`, a density matrix `ρ n` on `a n × b n` prepared by every node,
and a `q`-outcome POVM `P n` on `b n × a n` (received message register first) measured by every
node. The data for `n < 3` are present but never used. -/
structure AlgorithmFamily (q : ℕ) where
/-- the kept register at cycle length `n` -/
a : ℕ → Type
/-- the message register at cycle length `n` -/
b : ℕ → Type
[fa : ∀ n, Fintype (a n)]
[da : ∀ n, DecidableEq (a n)]
[fb : ∀ n, Fintype (b n)]
[db : ∀ n, DecidableEq (b n)]
/-- the state every node prepares on `A_ℓ B_ℓ` -/
ρ : ∀ n, Matrix (a n × b n) (a n × b n) ℂ
/-- the POVM every node measures on `B_{ℓ-1} A_ℓ` -/
P : ∀ n, Fin q → Matrix (b n × a n) (b n × a n) ℂ
isDensity : ∀ n, IsDensityMatrix (ρ n)
isPOVM : ∀ n, FuchsVdGraaf.IsPOVM (P n)
attribute [instance] AlgorithmFamily.fa AlgorithmFamily.da AlgorithmFamily.fb AlgorithmFamily.db
/-- The probability that the algorithm properly `q`-colours the directed cycle of length `m + 3`
(cycle lengths `n ≥ 3` are written `n = m + 3`). -/
noncomputable def AlgorithmFamily.successProb {q : ℕ} (F : AlgorithmFamily q) (m : ℕ) : ℝ :=
properColoringProb (m + 3) (F.ρ (m + 3)) (F.P (m + 3))
/-- Definition 3.8, p.19: the algorithm succeeds with high probability, i.e. with probability
at least `1 − 1/poly(n)` on the directed `n`-cycle: there are constants `A > 0` and `k > 0`
(fixed before `n`) and a threshold such that for every cycle length `n = m + 3 ≥ m₀ + 3`,
`Pr[proper q-colouring] ≥ 1 − A / n^k`. -/
def AlgorithmFamily.SolvesWHP {q : ℕ} (F : AlgorithmFamily q) : Prop :=
∃ A k : ℝ, 0 < A ∧ 0 < k ∧ ∃ m₀ : ℕ, ∀ m : ℕ, m₀ ≤ m →
1 - A / ((m + 3 : ℕ) : ℝ) ^ k ≤ F.successProb m
end QuantumCycleColoring.FourColor.Supplement
Source
Tom Gur, Longcheng Li, STOC 2027 submission #515 (October 2026), Definitions 3.8–3.10, pp.19–20 (high probability: Definition 3.8, p.19); Theorem 6.1 (Q2) and its proof, pp.40–42, footnote 10, p.42