Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability

1 Introduction

• The introduction frames directed-cycle coloring as a basic symmetry-breaking problem and notes that bounded-dependence arguments alone cannot establish the desired quantum lower bound.Proper 1-dependent 4-colorings exist, while existing quantum-LOCAL lower bounds relied on stronger causality-based models.Source: §1 · p. 2

1.1 Our Results

• One-way one-round quantum-LOCAL algorithms cannot 4-color directed cycles with high probability, despite proper 1-dependent 4-colorings existing in the bounded-dependence model.The proof is designed to use quantum-algorithm structure beyond bounded-dependence constraints.Source: §1 · p. 2, §1.1 · p. 3

1.2 Matrix-Space Stability

• The lower bound uses a matrix-space stability theorem: maximal spaces with nearly zero energy are close to maximal spaces with exactly zero energy.Matrix-space energy captures collision probability for quantum coloring, and the theorem yields a dimension-independent lower bound on total energy for four subspaces.Source: §1.2 · pp. 3–4

1.3 Related Work

• Earlier quantum lower bounds for cycle coloring rule out one-way one-round 3-coloring [LGR22], while finitely dependent proper 1-dependent 4-colorings are known [HHL18].The paper presents its high-probability separation as complementary to a probability-1 lower bound for anonymous algorithms using finitely many qubits.Source: §1.3 · p. 5

1.4 Open Problems

• The smallest feasible number of colors for one-way one-round quantum-LOCAL algorithms remains open, as does whether any graph problem has an asymptotic locality gap over bounded dependence.The paper reports that 4 colors are ruled out and follow-up work shows 2 · 104 colors suffice.Source: §1.4 · p. 5

2.1 Recasting the Classical Lower Bound

• For q≤4, the classical proof combines supersaturation for q≤3 with stability at q=4: a near-extremal color class rounds to a directed cut, leaving three colors on one side that force Ω(N^3) monochromatic 2-walks.The stability statement says a graph with (1/4 + o(1))N^2 edges and o(N^3) directed 2-walks is close to a balanced complete directed cut.Source: §2.1 · pp. 7–8

2.2.1 The Uniform Case

• In the uniform quantum case, measurement projectors correspond to orthogonal matrix spaces whose energy is the noncommutative analogue of directed 2-walk energy.A zero-energy space has extremal dimension threshold N^2/4; equality holds for the full cut space L(U⊥, U) under a balanced orthogonal decomposition.Source: §2.2.1 · pp. 9–10
• For q≤4 uniform quantum colorings, the argument yields Ω(N^3) total energy by combining supersaturation and stability, then rounding a near-cut space and applying the three-color bound within a diagonal block.The rounded first color vanishes on L(U, U), where the remaining three colors must contribute Ω(dim(U)^3) = Ω(N^3) energy.Source: §2.2.1 · pp. 12–13

2.2.2 The General Case

• General quantum messages can have nonuniform Schmidt coefficients, so Λ need not be the identity and the analysis must use Λ-energy.The weight matrix Λ encodes the message’s Schmidt coefficients.Source: §2.2.2 · p. 13
• If a matrix space has zero Λ-energy, its Λ-mass is at most 1/4; in the equality case, a structured orthogonal decomposition exists after restricting to Λ’s support.The extremal structure is a cut space L(U⊥, U), with the two subspaces carrying equal weight and invariant under Λ.Source: §2.2.2 · p. 14
• Mass 1/4 + η forces Ω(η) energy by bounded-dependence inequality, where mass is a color’s marginal probability and energy is its adjacent-node coincidence probability.The inequality supplies the weighted supersaturation step.Source: §2.2.2 · p. 14
• If a matrix space has Λ-mass 1/4 and Λ-energy o(1), it is close to a zero-energy cut space under a nearby PSD weight matrix.The nearby pair has mass exactly 1/4 and energy exactly zero.Source: §2.2.2 · p. 14
• The stability proof uses a spectral source–sink decomposition, then state discrimination to show that small energy makes Λ approximately preserve the candidate subspaces.A measurement with O(√ε) error and the pretty-good-measurement bound give off-diagonal error O(√ε); deleting off-diagonal blocks and rescaling yields a nearby exact zero-energy pair.Source: §2.2.2 · p. 15
• The weighted stability theorem yields a constant lower bound on local collision probability for arbitrary quantum messages, proving Theorem 1.1.It implies that the sum of the four color energies is Ω(1).Source: §2.2.2 · p. 15

3.1 Matrix Norms

• Matrix preliminaries cover standard norms, vectorization, and the Λ-norm, a trace-norm seminorm weighted by a PSD matrix.The Λ-norm becomes a proper norm when Λ is positive definite.Source: §3.1 · pp. 15–16

3.2 Quantum Information

• Quantum-information preliminaries introduce the Pretty Good Measurement and a four-outcome POVM perturbation lemma used in the final rounding step.The perturbation lemma measures distances in the Λ-norm.Source: §3.2 · p. 17

3.3 Models in Distributed Computing

• The model section defines directed-cycle coloring and anonymous one-way one-round algorithms, with identical nodes sending quantum messages to successors and receiving from predecessors.Local computation and message length are unbounded but finite, and nodes have no shared randomness or prior entanglement.Source: §3.3 · pp. 17–18
• Every such anonymous quantum algorithm produces stationary, 1-dependent outputs; in the high-probability setting, anonymity is equivalent to quantum-LOCAL algorithms.Stationarity follows from identical node procedures, while 1-dependence follows from disjoint light cones beyond distance 1.Source: §3.3 · p. 18

4 Energy Formulation

• Λ-mass and Λ-energy are defined for PSD operators and weights, including POVM elements and matrix-space projectors under vectorization.The formulation uses partial traces to define associated operators.Source: §4 · p. 18

4.1 Spectral Formula

• A spectral expression for Λ-energy connects it to the multiplicative structure of a matrix space, using a matrix family obtainable from a spectral decomposition.A related formula expresses Λ-mass in the same setting.Source: §4.1 · pp. 19–20

4.2 Examples

• For an unweighted matrix space, energy measures multiplicative energy and is zero exactly when the span of products of pairs of its matrices is {0}.With Λ = I, mass equals the space's dimension.Source: §4.2 · p. 20
• For a graph-encoded matrix space, energy counts directed 2-walks and is zero exactly when the graph is contained in a directed cut; a further example extends this encoding to weighted graphs.The unweighted space has mass equal to the number of edges.Source: §4.2 · pp. 20–21

4.3 The Operational Interpretation

• Λ-mass is the marginal probability of outcome P, while Λ-energy is the probability of obtaining the corresponding outcomes for P ⊗ P on a quantum state specified by Λ.The operational interpretation is established for PSD P bounded by I and normalized PSD Λ.Source: §4.3 · pp. 21–22

4.4 Useful Properties

• Energy is monotone under PSD ordering and, for fixed P, Lipschitz continuous in Λ with respect to the Frobenius norm.The Lipschitz property applies to PSD weights under the stated normalization conditions.Source: §4.4 · pp. 22–23

5.1 Structure of Zero-Energy Operators

• At zero energy, a POVM operator has Λ-mass at most 1/4; equality requires an off-diagonal matrix-space projector associated with a balanced Λ-invariant decomposition.The exact characterization assumes Λ is strictly positive, and its Λ-invariance condition has no classical analogue.Source: §5.1 · pp. 23, 24, 26, 27, §5 · p. 23

5.2 Approximation of Zero-Energy Operators

• For maximal-mass operators with small energy, Theorem 5.6 approximates both the operator and its weight matrix by an exact zero-energy extremizer, with error O(ε^1/4).This robust result does not require Λ to be strictly positive.Source: §5.2.1 · p. 27, §5.2 · p. 27

5.2.1 Candidate Construction

• The candidate pair uses an off-diagonal-space projector and a block-diagonal weight matrix to achieve maximal mass and exactly zero energy.The projector is onto the matrix space L(U⊥, U), with the weight matrix block diagonal relative to U ⊕ U⊥.Source: §5.2.1 · p. 28

5.2.2 Approximate Λ-Invariance of U

• When the energy is ε, the constructed subspace U is approximately invariant under Λ, with non-invariance measure δ = O(√ε).The proof relates δ to the pretty-good measurement’s testing error for two subnormalized states, then constructs a measurement with small error.Source: §5.2.2 · p. 28

5.2.3 Proof of Theorem 5.6

• The proof controls leakage of the weighted operator outside the candidate projector’s matrix space, bounding it by O(√ε).The weighted operator’s trace equals the weighted mass, and its partial traces are the weighted marginals.Source: §5.2.3 · pp. 32–33
• Lemma 5.17 bounds the weighted distance between P and P′ by O(ε^1/4).Source: §5.2.3 · p. 35
• The proof handles ε = 0 by taking P′ = P and Λ′ = Λ, and for ε ≥ 1/16 it takes any valid pair with zero energy and m_Λ′(P′) = 1/4.Source: §5.2.3 · p. 37
• For 0 < ε < 1/16, the threshold t = max{j : ρ_j ≥ √ε} is well defined and satisfies 1 ≤ t < N.Source: §5.2.3 · pp. 37–38
• The constructed pair is well defined in the intermediate-error case because both normalization factors Tr(X²) and Tr(Y²) are positive.If either factor were zero, the resulting bound would contradict ε < 1/16; the proof then concludes using Fact 5.7 and Lemmas 5.16 and 5.17.Source: §5.2.3 · p. 38

6.1 General Reduction

• The local collision probability is characterized by measurement energy, and a constant lower bound on edge collisions forces proper-coloring success to be o(1).Distant edge-collision events are independent, so selecting ⌊n/3⌋ separated edges gives the success bound.Source: §6 · p. 38, §6.1 · p. 39
• The energy criterion is equivalent to high-probability coloring impossibility for each fixed q ≥ 2.If the criterion fails, a state vec(Λ̄) and the corresponding POVM yield failure probability at most ε, allowing success probability at least 1 − 1/n.Source: §6.1 · pp. 38–40

6.2 Impossibility of ≤3 Colors

• Under the condition ∥Λ∥F = 1, the three terms EΛ(P_i), for i ∈ [3], sum to Ω(1), establishing a constant-order lower bound on their total Λ-energy.If mΛ(P) = 1/4 + ε for ε ≥ 0, then EΛ(P) ≥ min{2ε/9, 1/54}, also under ∥Λ∥F = 1.Source: §6.2 · pp. 40–41

6.3 Impossibility of 4 Colors

• One-way one-round quantum-LOCAL algorithms cannot 4-color directed cycles with high probability.The proof establishes the four-outcome energy bound and applies the equivalence between energy bounds and coloring impossibility.Source: §6.3 · pp. 41–42, §6.3.2 · p. 45

6.3.1 Warm-Up: One Color with Exact Zero Energy

• When one color has zero energy and maximal mass, its operator is an off-diagonal projector, reducing the other three outcomes to a 3-outcome POVM.The reduction projects the remaining operators onto the diagonal block L(U,U).Source: §6.3.1 · pp. 42–43

6.3.2 General Case: Proof of Theorem 6.5

• In the general four-color case, small energy permits approximation by a zero-energy operator, reducing the proof to the exact-zero-energy case.The approximation theorem supplies nearby operators and weight matrices; the resulting bound establishes the four-outcome energy claim.Source: §6.3.2 · pp. 44–45

• The authors say the main results and proofs were obtained without AI, but AI tools assisted literature review, proofreading, and exposition.Source: AI Disclosure · p. 46

A.1 Proof of Lemma 3.7

• The proof first establishes that matrices with close Gram matrices can be close up to a unitary.This fact is identified as a consequence of Uhlmann’s theorem.Source: §A.1 · p. 48
• Uhlmann’s theorem supplies a unitary alignment through fidelity between the states formed from X†X and Y†Y.The proof normalizes these matrices to define ρ and σ, then uses their fidelity to select the unitary.Source: §A.1 · pp. 48–49
• The alignment is applied to R = I − P1 and S = I − Z to define new POVM elements.The proof defines a unitary using the corresponding matrices X and Y, then uses it in the new elements.Source: §A.1 · pp. 49–50

A.2 Proof of Lemma 4.9

• ∥ΛAΛ − Λ′A′Λ′∥1 ≤ 4∥Δ∥F.The estimate uses contractivity of trace norm under partial trace, the triangle inequality, and Hölder’s inequality.Source: §A.2 · pp. 50–51
• ∥B − B′∥∞ ≤ 2∥Δ∥F, using unit-vector matrix elements and a trace-norm bound.The proof bounds the matrix elements by ∥Λ² − Λ′²∥1 before obtaining the stated estimate.Source: §A.2 · p. 51
• |EΛ(P) − EΛ′(P)| ≤ 6∥Δ∥F, where Δ = Λ − Λ′.The proof combines bounds on the intermediate terms with Hölder’s inequality.Source: §A.2 · pp. 50–51

B An Alternative Proof for ≤3 Colors

• The stated constants for Theorem B.1 are 1/8 for q = 2 and 1/2916 for q = 3.The theorem concerns POVMs with q ∈ {2, 3}.Source: B An Alternative Proof for ≤3 Colors · p. 51
• The proof reduces the POVM analysis to a single element P with mΛ(P) ≥ 1/q, then applies energy bounds for elements with mΛ(P) ≥ 1/3.Averaging over the POVM elements yields an index j with mΛ(Pj) ≥ 1/q.Source: B An Alternative Proof for ≤3 Colors · pp. 51–52
• The proof defines ε = x + y + 2E − 4m² and derives ε ≤ 2E from x + y ≤ m + m².The quantities are defined using traces of R, S, and Λ.Source: B An Alternative Proof for ≤3 Colors · pp. 52, 54
• When m = 1/3, a refined analysis shows that if inequality (30) is almost tight (epsilon close to zero), inequality (32) must have large slack; together, these yield a positive lower bound.Source: B An Alternative Proof for ≤3 Colors · p. 53