Conceptio › Archive › arXiv CS

arXiv CSopen access

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

· arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

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

arXiv:2609.09091v1 [quant-ph] 8 Sep 2026

Tom Gur‗

Longcheng Li†

Abstract We show that one-way one-round quantum LOCAL algorithms cannot 4-color directed cycles with high probability, even with unbounded local computation and quantum message length. This is the first lower bound in the high-probability quantum LOCAL setting that goes beyond the non-signaling and bounded-dependence models, exploiting the structure of distributed quantum algorithms. Our proof connects distributed quantum computing with noncommutative extremal combinatorics by identifying local collision probabilities with the weighted multiplicative energy of matrix-space decompositions. We obtain our lower bound by proving a dimension-independent weighted stability theorem for a directed noncommutative analogue of Mantel’s theorem.

Introduction

The LOCAL model [Lin92, Pel00] distills a central question in distributed computing: what can be computed in a network where each processor sees only its local neighborhood? In this model, each processor initially knows only its unique identifier and communicates with its neighbors in synchronous rounds; local computation and message length are unrestricted, and complexity is measured solely by the number of communication rounds, referred to as the locality of the problem. Over the last decades, a wide range of graph problems have been studied in the deterministic and randomized LOCAL models [Suo13]. A central focus has been on problems specified by local constraints, such as graph coloring, and a substantial recent effort has been devoted to understanding the landscape of locality across this class of problems [Cha20, BBCR+ 25]. It is natural to ask whether quantum information changes the landscape of locality. In the quantum LOCAL model, each processor is a quantum computer and each communication link is a quantum channel [GKM09]. The processors initially have unique identifiers and do not share any global randomness or entanglement. They may perform arbitrary local quantum operations and exchange quantum messages of arbitrarily many qubits with their neighbors in each round. A distributed problem admits a quantum advantage in the LOCAL model if it can be solved in fewer rounds by a quantum algorithm than by any classical algorithm. A sequence of works has demonstrated proof-of-concept quantum advantages for several specially constructed problems using quantum nonlocal games [LGNR19, BBCR+ 25, BCd+ 26]. At the ‗ University of Cambridge. Email: [email protected]. Supported by ERC Starting Grant 101163189 and UKRI

Future Leaders Fellowship MR/X023583/1. † University of Cambridge. Email: [email protected]. Supported by ERC Starting Grant 101163189.

same time, other results have ruled out quantum advantages for many natural problems, including maximum independent set and max cut [GKM09], approximate graph coloring [CRdG+ 24] and distributed linear programming [BCC+ 25]. However, the quantum locality of the basic symmetry-breaking problem of coloring a directed 𝑛-cycle with a small number of colors remains poorly understood. The problem of 2-coloring an even cycle is global, which requires Θ(𝑛) rounds in both the classical and quantum settings [GKM09, FMZ26]. For every fixed 𝑞 ≥ 3, the tight locality Θ(log∗ 𝑛) is known in both the deterministic and randomized classical LOCAL models [Lin92, Nao91]. In the quantum LOCAL model, however, the only nontrivial lower bounds for 3-coloring directed cycles rule out one-way one-round algorithms [HSW17, LGR22], where each processor only sends one quantum message to its successor in the directed cycle before computing its color. For more than three colors, even this restricted case remains open, and the only elementary observation is that some communication is necessary. This limited understanding can be partially explained by a fundamental barrier to proving lower bounds in the quantum LOCAL model [ACRd+ 25]. All known quantum LOCAL lower bounds [GKM09, AF14, BCC+ 25, FMZ26] proceed by establishing impossibility in stronger causality-based models, such as the non-signaling and bounded-dependence models. The latter abstracts away the round-based structure of the algorithm and retains only the requirement that the outputs of sufficiently distant processors should be independent, since their light cones do not intersect. Any lower bound in this model also applies to the quantum LOCAL model. In particular, proper 4-colorings of cycles with minimal dependence are known to exist in the bounded-dependence model [HHL18], and hence such arguments cannot rule out the possibility of quantum algorithms. In this work, we study the minimal nontrivial open problem: Can a one-way one-round quantum LOCAL algorithm 4-color directed cycles with high probability? By the discussion above, resolving this problem requires new techniques that specifically exploit the structure of quantum algorithms, rather than bounded dependence alone.

1.1

Our Results

Our main contribution is a negative answer to the question above. More precisely, we show that for any one-way one-round quantum algorithm that 4-colors a directed cycle, the collision probability on each edge, namely the probability of its two endpoints outputting the same color, is at least a universal positive constant, independent of the local dimension, message length, and cycle length. Theorem 1.1. Consider a directed cycle of 𝑛 vertices. For any one-way one-round quantum algorithm that outputs a 4-coloring (𝑐𝑖 ∈ [4])𝑖 ∈ℤ𝑛 of the cycle, we have Pr[𝑐𝑖 = 𝑐𝑖+1 ] ≥ 𝐶

∀𝑖 ∈ ℤ𝑛 ,

where 𝐶 > 0 is a universal constant independent of 𝑛 and the algorithm. Because the algorithm is one-way one-round, its output coloring (𝑐𝑖 )𝑖 ∈ℤ𝑛 is 1-dependent: the colors of two vertex sets 𝑈 and 𝑉 are independent whenever the graph distance between 𝑈 and 𝑉 exceeds 11 . Hence the collision events on a collection of edges are jointly independent if any two 1 To avoid distant correlations caused by the initial identifiers, we use the standard assumption that each processor samples its identifier independently from a sufficiently large polynomial-size set. The sampled identifiers are pairwise distinct with high probability, so this is without loss of generality.

edges are separated by at least one vertex. By choosing ⌊𝑛/3⌋ such edges {(3𝑖, 3𝑖 + 1) : 0 ≤ 𝑖 < ⌊𝑛/3⌋} and applying Theorem 1.1, we find that the probability of producing a proper coloring is at most (1 − 𝐶) ⌊𝑛/3⌋ , which is negligible in 𝑛. Consequently, we obtain the following corollary. Corollary 1.2. No one-way one-round quantum LOCAL algorithm can 4-color directed cycles with high probability, even with unbounded local computation and quantum message length. Combined with the construction of 1-dependent proper 4-colorings of cycles [HHL18], our lower bound gives the first natural separation between the bounded-dependence model and oneway one-round quantum LOCAL algorithms for a local symmetry-breaking problem.

1.2

Matrix-Space Stability

The proof of Theorem 1.1 utilizes a more general characterization of one-way one-round quantum 𝑞-coloring in terms of a noncommutative extremal-combinatorial problem. We first define the weighted multiplicative energy of a matrix space. Definition 1.3 (Λ-energy of a matrix space). Let 𝑊 ⊆ ℂ𝑁 ×𝑁 be a matrix space and let Λ ∈ ℂ𝑁 ×𝑁 be a PSD weight matrix with ∥Λ∥ 𝐹 = 1. For any Frobenius-orthonormal basis {𝑀𝑘 }𝑘 of 𝑊 , define the Λ-energy of 𝑊 by ∑︁ EΛ (𝑊 ) := ∥Λ𝑀𝑘 Λ𝑀ℓ Λ∥ 2𝐹 . 𝑘,ℓ

This definition is independent of the chosen orthonormal basis. In the classical unweighted setting, it counts directed walks of length two, with matrix multiplication representing the concatenation of directed edges; see Section 2.1. The following stability theorem shows that “maximal spaces” with nearly zero energy are close to exact zero-energy spaces. Theorem 1.4 (informal, see Theorem 5.6). If 𝑊 is maximal and has EΛ (𝑊 ) = 𝑜 (1), then there is a nearby pair (Λ′,𝑊 ′ ) of a PSD weight matrix and a maximal matrix space, such that EΛ′ (𝑊 ′ ) = 0. Í Here, maximality is measured by the weighted mass 𝑚 Λ (𝑊 ) := 𝑘 ∥Λ𝑀𝑘 Λ∥ 2𝐹 . We call𝑊 maximal when 𝑚 Λ (𝑊 ) = 1/4, the largest possible mass of a zero-energy space; see Section 2.2 for a more detailed discussion. Applying the stability theorem to the heaviest subspace in an orthogonal decomposition of ℂ𝑁 ×𝑁 into four subspaces yields a universal lower bound on their total Λ-energy. Theorem 1.5 (informal, see Theorem 6.6). There exists a universal constant 𝐶 > 0 such that, for every dimension 𝑁 , every normalized PSD matrix Λ ∈ ℂ𝑁 ×𝑁 and every orthogonal decomposition ℂ𝑁 ×𝑁 =

4 Ê

𝑊𝑖 ,

𝑖=1

we have

4 ∑︁

EΛ (𝑊𝑖 ) ≥ 𝐶.

𝑖=1

Finally, our main impossibility result follows from an exact equivalence between the energy bound in Theorem 1.5 and the collision probability bound in Theorem 1.1. More generally, this equivalence holds for any fixed number of colors 𝑞 ≥ 2, as stated below. Theorem 1.6 (informal, see Theorem 6.2). For every fixed integer 𝑞 ≥ 2, the following are equivalent: 1. Every one-way one-round quantum algorithm that outputs a 𝑞-coloring (𝑐𝑖 ∈ [𝑞])𝑖 ∈ℤ𝑛 of a directed cycle has collision probability Pr[𝑐𝑖 = 𝑐𝑖+1 ] = Ω𝑞 (1). Consequently, one-way one-round 𝑞-coloring is impossible in the quantum LOCAL model. É 2. For every normalized PSD Λ and every orthogonal decomposition of ℂ𝑁 ×𝑁 into 𝑞 subspaces 𝑖 ∈ [𝑞 ] 𝑊𝑖 , Í their total Λ-energy 𝑖 ∈ [𝑞 ] EΛ (𝑊𝑖 ) = Ω𝑞 (1). Theorem 1.6 provides the first lower-bound technique that operates directly within the quantum LOCAL model and is not captured by bounded dependence.

1.3

Related Work

The classical locality of coloring directed cycles with any fixed number of colors 𝑞 ≥ 3 is well understood. Cole and Vishkin gave a deterministic 𝑂 (log∗ 𝑛)-round algorithm, while Linial proved a matching lower bound [CV86, Lin92]. Naor later extended the same lower bound to randomized algorithms that succeed with high probability [Nao91], so classical randomness does not help for this problem. More generally, (Δ + 1)-coloring graphs of maximum degree Δ can be solved deterministically in 𝑂 (Δ + log∗ 𝑛) rounds, which is 𝑂 (log∗ 𝑛) when Δ is constant [BEK14]. Several recent works have sought analogous quantum lower bounds. [HSW17, LGR22] show that a one-way one-round quantum algorithm cannot 3-color directed cycles. [FMZ26] proved an Ω(log∗ 𝑛) lower bound for 3-coloring rooted trees, and ruled out even constant quantum advantage for 2-coloring even cycles. All of these lower bounds also apply to the stronger boundeddependence model. Recently, [CRFdG+ 26] developed a technique for the quantum model and proved that any quantum algorithm using finitely many qubits that 3-colors an anonymous cycle with probability 1 requires Ω(𝑛) rounds. Their result is formulated in the quantum PN model, whose nodes are anonymous, rather than in the quantum LOCAL model, whose nodes have unique identifiers. Although anonymous nodes can generate unique random identifiers with high probability, this reduction is unavailable under the probability-1 restriction. Their result therefore does not imply a lower bound in the quantum LOCAL model and is complementary to our high-probability separation. Another line of work gives constructions of bounded-dependent proper colorings. A distribution over vertex labels is 𝑘-dependent if the labels on any two vertex sets at graph distance greater than 𝑘 are independent. [HL16] first constructed a stationary 2-dependent 3-coloring and a stationary 1-dependent 4-coloring of ℤ, and subsequently [HHL18] extended these constructions to finite cycles. Since any one-way one-round quantum algorithm on a directed cycle produces a stationary 1-dependent distribution, these constructions imply that bounded-dependence arguments alone cannot establish the quantum lower bound desired in this work. More generally, a problem is said to have locality 𝑇 in the bounded-dependence model if it admits a valid 2𝑇 -dependent output distribution. Without prior shared resources, every 𝑇 -round LOCAL algorithm, no matter whether classical or quantum, produces such a distribution: vertex sets at distance greater than 2𝑇 have disjoint radius-𝑇 light cones and therefore independent outputs. [ACRd+ 25] subsequently showed 4

that (Δ + 1)-coloring a graph with constant maximum degree Δ can be solved in the boundeddependence model with constant locality, imposing a strong barrier to proving quantum lower bounds for this problem.

1.4

Open Problems

We highlight two open problems that we find particularly interesting. The first problem is to generalize our lower bound to more than four colors. For four colors, averaging over four matrix spaces gives one space of mass at least 1/4, precisely the extremal threshold for a maximal zeroenergy space. For 𝑞 ≥ 5 colors, however, it guarantees only mass 1/𝑞, so our proof does not extend directly. Further progress will likely require understanding how multiple matrix spaces interact, rather than tackling them one at a time. The second, more ambitious problem is to allow bidirectional communication or more than one round. These settings involve multipartite entanglement and thus no longer admit the simple Schmidt representation used in our bipartite setting. It remains open to determine the exact quantum locality of constant-color cycle coloring and whether quantum advantage is possible for symmetry-breaking problems at all. Organization. Section 2 gives an overview of the proof. Section 3 introduces the necessary background and notation. Section 4 develops the formal definition of mass and energy, and establishes their basic properties. Next, Section 5 characterizes zero-energy operators and proves the core stability theorem for low-energy operators. Finally, Section 6 connects the energy formulation to one-way one-round quantum coloring and proves our main impossibility theorem for four colors.

Technical Overview

Our proof recasts one-way one-round coloring as an extremal-combinatorics problem. We begin in Section 2.1 by reproving the classical lower bound from this perspective. Then, in Section 2.2, we give an overview of our proof in the quantum setting, which builds on a noncommutative generalization of the classical extremal problem. In both settings, supersaturation suffices to rule out three colors, whereas our four-color argument also exploits the structure provided by stability.

2.1

Reproving the Classical Lower Bound

Recasting the classical problem. We first consider one-way one-round classical algorithms that color a directed cycle with 𝑞 colors in the randomized LOCAL model. Each processor can sample an identifier independently from a sufficiently large polynomial-size set, and the sampled identifiers are pairwise distinct with high probability. We therefore absorb the identifier into the local random seed and analyze initially identical processors that execute the same procedure. Moreover, the random coins of a classical algorithm can be pulled to the beginning, so we may describe the algorithm as follows: Let 𝑁 be the size of the local random-seed space. Every processor 𝑣𝑖 independently samples a uniform seed 𝑟𝑖 ∈ [𝑁 ], sends it to 𝑣𝑖+1 , and outputs 𝑐𝑖 = 𝑓 (𝑟𝑖 −1, 𝑟𝑖 )

for a deterministic function 𝑓 : [𝑁 ] 2 → [𝑞]. This is the standard block-factor view of constantradius stochastic processes [Nao91, HSW17]. Since the processors are completely symmetric, it suffices to analyze the local collision probability, i.e., the probability Pr[𝑐𝑖 = 𝑐𝑖+1 ] of any two adjacent processors (𝑣𝑖 , 𝑣𝑖+1 ) outputting the same color. For each color 𝑎 ∈ [𝑞], define the arc set and the corresponding directed graph 𝐸𝑎 := {(𝑥, 𝑦) ∈ [𝑁 ] 2 : 𝑓 (𝑥, 𝑦) = 𝑎},

𝐺𝑎 := ( [𝑁 ], 𝐸𝑎 ).

The sets 𝐸 1, . . . , 𝐸𝑞 partition all ordered pairs in [𝑁 ] 2 . For two adjacent processors (𝑣𝑖 , 𝑣𝑖+1 ), they both output 𝑎 exactly when (𝑟𝑖 −1, 𝑟𝑖 ) and (𝑟𝑖 , 𝑟𝑖+1 ) are arcs of 𝐺𝑎 . Consequently, 1 ∑︁ Pr[𝑐𝑖 = 𝑐𝑖+1 ] = 3 E (𝐺𝑎 ), 𝑁 𝑎=1 𝑞

where

E (𝐺𝑎 ) := #{(𝑥, 𝑦, 𝑧) ∈ [𝑁 3 ] : (𝑥, 𝑦), (𝑦, 𝑧) ∈ 𝐸𝑎 }.

(1)

The energy E (𝐺𝑎 ) counts directed 2-walks in a graph 𝐺𝑎 . Therefore, the classical lower bound is equivalent to the following extremal question: Does every 𝑞-coloring of [𝑁 ] 2 contain Ω(𝑁 3 ) monochromatic directed 2-walks? A general block-factor argument gives a positive answer for every fixed 𝑞 [HSW17, Proposition 5], but that argument essentially relies on steps such as conditioning on the intermediate random seed, which does not survive quantization due to the no-cloning principle. Instead, we give an alternative proof for 𝑞 ≤ 4 via an extremal graph argument, and its natural noncommutative counterpart leads to the quantum lower bound. The extremal graph picture. Assume 𝑁 is even. For a directed graph 𝐺 = ( [𝑁 ], 𝐸), by enumerating the intermediate vertex of a directed 2-walk, we have the identity ∑︁ (2) E (𝐺) = 𝑑 − (𝑦)𝑑 + (𝑦), 𝑦 ∈ [𝑁 ]

where 𝑑 − (𝑦) and 𝑑 + (𝑦) are the in-degree and out-degree of vertex 𝑦. The condition E (𝐺) = 0, i.e., 𝐺 contains no directed 2-walks, imposes a rigid cut structure. Lemma 2.1 (Directed Mantel’s theorem). If E (𝐺) = 0, then |𝐸| ≤ 𝑁 2 /4. Equality holds if and only if there is a partition [𝑁 ] = 𝐿 ⊔ 𝑅 with |𝐿| = |𝑅| = 𝑁2 such that 𝐸 = 𝐿 × 𝑅. Indeed, if E (𝐺) = 0, then a vertex cannot have both an incoming and an outgoing arc. If 𝐿 is the set of vertices with positive out-degree and 𝑅 = [𝑁 ] \ 𝐿, then every arc points from 𝐿 to 𝑅. Hence |𝐸| ≤ |𝐿||𝑅| ≤

𝑁2 , 4

and equality forces a balanced complete directed cut. This is a directed analogue of Mantel’s theorem [Man07]. For 𝑞 ≤ 3, averaging gives a color class with at least 𝑁 2 /3 arcs, exceeding the extremal threshold 2 𝑁 /4 by Ω(𝑁 2 ). Supersaturation therefore yields Ω(𝑁 3 ) monochromatic directed 2-walks. For 𝑞 = 4, averaging guarantees only 𝑁 2 /4 arcs, so our argument also needs stability: if |𝐸| is close to 6

𝑁 2 /4 and E (𝐺) is small, then 𝐸 must be close to a balanced complete directed cut. The following lemma establishes both supersaturation and stability. Lemma 2.2 (Robust version of Lemma 2.1). Every directed graph 𝐺 = ( [𝑁 ], 𝐸) admits a partition [𝑁 ] = 𝐿 ⊔ 𝑅 such that √︁ |𝐸 \ (𝐿 × 𝑅)| ≤ 2 𝑁 · E (𝐺). We have two immediate consequences: 1. (Supersaturation) If |𝐸| − 𝑁 2 /4 = Ω(𝑁 2 ), then E (𝐺) = Ω(𝑁 3 ). 2. (Stability) If |𝐸| = (1/4 + 𝑜 (1))𝑁 2 and E (𝐺) = 𝑜 (𝑁 3 ), then the corresponding 𝐿 and 𝑅 satisfy and

|𝐿|, |𝑅| = (1/2 + 𝑜 (1))𝑁

|𝐸 △ (𝐿 × 𝑅)| = 𝑜 (𝑁 2 ).

This mechanism follows from a thresholded source–sink separation. If E (𝐺) = 0, Lemma 2.1 already places 𝐸 inside a directed cut. Otherwise, choose the partition 𝐿 ⊔ 𝑅 as √︂ E (𝐺) + + 𝐿 := {𝑦 : 𝑑 (𝑦) > 𝜃 }, 𝑅 := {𝑦 : 𝑑 (𝑦) ≤ 𝜃 }, where 𝜃 := . 𝑁 For each 𝑦 ∈ 𝑅, delete all its outgoing arcs, and for each 𝑦 ∈ 𝐿, delete all its incoming arcs. This is equivalent to deleting all arcs outside 𝐿 × 𝑅, leaving the remaining arc set 𝐸 ′ ⊆ 𝐿 × 𝑅. Then we bound the number of deleted arcs.2 There are two possible reasons for deleting an arc: its start vertex lies in 𝑅, or its end vertex lies in 𝐿. Using Equation (2) to bound these two contributions gives Í − + ∑︁ ∑︁ 𝑑 + (𝑦) >𝜃 𝑑 (𝑦)𝑑 (𝑦) + − 𝑑 (𝑦) + 𝑑 (𝑦) ≤ 𝑁 𝜃 + |𝐸 \ (𝐿 × 𝑅)| ≤ 𝜃 + + 𝑑 (𝑦) ≤𝜃

𝑑 (𝑦) >𝜃

≤ 𝑁𝜃 +

√︁ E (𝐺) = 2 𝑁 · E (𝐺). 𝜃

Since |𝐿×𝑅| ≤ 𝑁 2 /4, any excess of |𝐸| above 𝑁 2 /4 must have been deleted. Then the above bound gives supersaturation. For the stability, under the assumption E (𝐺) = 𝑜 (𝑁 3 ), the above bound shows that only 𝑜 (𝑁 2 ) arcs are deleted, so |𝐸 ′ | = (1/4+𝑜 (1))𝑁 2 . It follows that |𝐿×𝑅| = (1/4+𝑜 (1))𝑁 2 , forcing 𝐿 and 𝑅 to be nearly balanced. Moreover, 𝐸 ′ = 𝐸 ∩ (𝐿 × 𝑅) is missing only 𝑜 (𝑁 2 ) arcs from 𝐿 × 𝑅, which gives |𝐸 △ (𝐿 × 𝑅)| = 𝑜 (𝑁 2 ). Classical impossibility for 𝑞 ≤ 4 colors. The impossibility of 𝑞 ≤ 3 colors is immediate from Lemma 2.2: By averaging, there must exist a color class, say 𝐸 1 , with at least 𝑁 2 /3 arcs, and thus supersaturation implies 𝐸 1 has Ω(𝑁 3 ) directed 2-walks. Now we prove the impossibility of 𝑞 = 4. Suppose, toward a contradiction, that a 4-coloring of [𝑁 ] 2 has only 𝑜 (𝑁 3 ) monochromatic directed 2-walks. By averaging, some color class, say 𝐸 1 , has at least 𝑁 2 /4 arcs. By assumption, 𝐸 1 has only 𝑜 (𝑁 3 ) directed 2-walks. Then by Lemma 2.2, 2 This threshold rule is not optimal. If, at each vertex, we instead delete the smaller of its incoming and outgoing arc √︁ Í sets, then the number of deletions is at most 𝑦 min{𝑑 − (𝑦), 𝑑 + (𝑦)} ≤ 𝑁 · E (𝐺). We use the threshold rule because it extends to the general quantum setting.

supersaturation forces |𝐸 1 | = (1/4 + 𝑜 (1))𝑁 2 , and stability gives a nearly balanced partition [𝑁 ] = 𝐿 ⊔ 𝑅 for which |𝐸 1 △(𝐿 × 𝑅)| = 𝑜 (𝑁 2 ). Changing the colors of these 𝑜 (𝑁 2 ) exceptional arcs changes the number of monochromatic directed 2-walks by only 𝑜 (𝑁 3 ) 3 . Therefore we can round 𝐸 1 to exactly 𝐿×𝑅. Observe that after rounding, the subgraph 𝐿 × 𝐿 contains no arcs of color 1, and thus is colored by only the other three colors. Since |𝐿| = (1/2 +𝑜 (1))𝑁 , the three-color lower bound inside 𝐿 produces Ω(|𝐿| 3 ) = Ω(𝑁 3 ) monochromatic directed 2-walks, contradicting the original assumption.

2.2

The Quantum Lower Bound

We now turn to the quantum setting. Both Lemma 2.1 and Lemma 2.2 admit noncommutative analogues. We first explain the simpler, unweighted version, corresponding to maximally entangled messages. In this setting, the classical proof above has a nearly literal quantization. General messages require a weighted version of the same argument, whose proof is more involved. The unweighted quantum setting. We first restrict to maximally entangled messages and projective measurements. In this case, each processor 𝑣𝑖 starts by preparing a maximally entangled state 1 ∑︁ |Φ⟩ = √ | 𝑗⟩ A𝑖 ⊗ | 𝑗⟩ B𝑖 , 𝑁 𝑗 ∈ [𝑁 ] then sends B𝑖 to 𝑣𝑖+1 , and finally measures B𝑖 −1 ⊗ A𝑖 with the same 𝑞-outcome projective measurement {𝑃𝑎 }𝑎∈ [𝑞 ] . This is the quantum counterpart of retaining one copy of a uniform random seed and sending the other to the next vertex. Under the vectorization map vec : ℂ𝑁 ×𝑁 → ℂ𝑁 ⊗ ℂ𝑁 , write the spectral decomposition ∑︁ 𝑃𝑎 = vec(𝑀𝑎,𝑘 )vec(𝑀𝑎,𝑘 ) †, 𝑘

where {𝑀𝑎,𝑘 }𝑘 is Frobenius-orthonormal, and set the matrix space 𝑊𝑎 := span{𝑀𝑎,𝑘 }𝑘 ⊆ ℂ𝑁 ×𝑁 . The measurement therefore induces the orthogonal decomposition ℂ𝑁 ×𝑁 = 𝑊1 ⊕ · · · ⊕ 𝑊𝑞 . A direct calculation gives Pr[𝑐𝑖 = 𝑐𝑖+1 = 𝑎] =

1 E (𝑊𝑎 ), 𝑁3

where

E (𝑊𝑎 ) :=

∑︁

∥𝑀𝑎,𝑘 𝑀𝑎,ℓ ∥ 2𝐹 .

(3)

𝑘,ℓ

The quantity E (𝑊𝑎 ) is the unweighted energy of space 𝑊𝑎 . The energy of a matrix space is precisely the noncommutative analogue of the energy of a directed graph. To see this, for a directed graph 𝐺 = ([𝑁 ], 𝐸), define a coordinate space 𝑊𝐺 = span{𝐸𝑥 𝑦 : (𝑥, 𝑦) ∈ 𝐸}, where 𝐸𝑥 𝑦 are standard matrix units. Observe that 𝐸𝑥 𝑦 𝐸 𝑤𝑧 is nonzero if and only if 𝑦 = 𝑤, namely (𝑥, 𝑦, 𝑧) forms a directed 2-walk. Thus E (𝐺) = E (𝑊𝐺 ), and we recover the classical identity Equation (1). 3 To see this, one arc forms at most 2𝑁 directed 2-walks.

By Equation (3), the desired lower bound for local collision probability in this restricted model is equivalent to the following matrix-theoretic conjecture. Conjecture 2.3 (Unweighted projective version of Conjecture 6.1). ÉFix an integer 𝑞 ≥ 2. There is 𝑁 ×𝑁 a constant 𝐶𝑞 > 0 such that every orthogonal decomposition ℂ = 𝑎∈ [𝑞 ] 𝑊𝑎 , in every dimension 𝑁 satisfies ∑︁ E (𝑊𝑎 ) ≥ 𝐶𝑞 𝑁 3 . 𝑎∈ [𝑞 ]

Indeed, after dividing by 𝑁 3 , the conclusion is exactly a dimension-independent lower bound on the local collision probability. We next develop the noncommutative analogues of Lemmas 2.1 and 2.2, and then sketch the proof for 𝑞 ≤ 4. A noncommutative directed Mantel’s theorem. For a matrix space 𝑊 and its orthonormal basis {𝑀𝑘 }, we have E (𝑊 ) = 0 if and only if 𝑀𝑘 𝑀ℓ = 0 for every 𝑘, ℓ, or equivalently 𝑊 2 := span{𝑋𝑌 : 𝑋, 𝑌 ∈ 𝑊 } = {0}. The largest matrix space with 𝑊 2 = {0} is the noncommutative counterpart of a balanced complete directed cut. Lemma 2.4 (Quantum analogue of Lemma 2.1). If 𝑊 ⊆ ℂ𝑁 ×𝑁 satisfies E (𝑊 ) = 0, then dim(𝑊 ) ≤

𝑁2 . 4

Equality holds if and only if there is an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ such that dim(𝑈 ) = dim(𝑈 ⊥ ) =

𝑁 2

and

𝑊 = L(𝑈 ⊥, 𝑈 ) := {𝑋 : Im(𝑋 ) ⊆ 𝑈 , 𝑋 |𝑈 = 0}.

Í We construct the cut by 𝑈 := 𝑋 ∈𝑊 Im(𝑋 ). Then every 𝑋 ∈ 𝑊 maps into 𝑈 , and 𝑊 2 = {0} implies that every 𝑋 ∈ 𝑊 annihilates 𝑈 . Therefore 𝑊 ⊆ L(𝑈 ⊥, 𝑈 ), so dim(𝑊 ) ≤ dim(𝑈 ) (𝑁 − dim(𝑈 )) ≤

𝑁2 . 4

Equality forces 𝑈 to be balanced and 𝑊 = L(𝑈 ⊥, 𝑈 ). If we define a unitary matrix 𝑉 ∈ U(𝑁 ) whose first half of columns form an orthonormal basis of 𝑈 and second half form that of 𝑈 ⊥ , then 𝑊 is exactly the space supported on the upper-right block 𝑁 0 𝑋 † × 𝑁2 2 𝑊 = 𝑉 𝑉 :𝑋 ∈ℂ . 0 0 As in the classical argument, we need the following robust form. Lemma 2.5 (Quantum analogue of Lemma 2.2). Every 𝑊 ⊆ ℂ𝑁 ×𝑁 admits an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ such that √︁ Tr((𝐼 − 𝑃𝐿 )𝑃𝑊 ) ≤ 2 𝑁 · E (𝑊 ), where 𝑃𝑊 and 𝑃𝐿 are the orthogonal projectors onto 𝑊 and L(𝑈 ⊥, 𝑈 ) respectively. Consequently, 9

1. (Supersaturation) If dim(𝑊 ) − 𝑁 2 /4 = Ω(𝑁 2 ), then E (𝑊 ) = Ω(𝑁 3 ). 2. (Stability) If dim(𝑊 ) = (1/4 + 𝑜 (1))𝑁 2 and E (𝑊 ) = 𝑜 (𝑁 3 ), then the corresponding 𝑈 satisfies dim(𝑈 ), dim(𝑈 ⊥ ) = (1/2 + 𝑜 (1))𝑁

∥𝑃𝑊 − 𝑃𝐿 ∥ 1 = 𝑜 (𝑁 2 ).

and

The quantity Tr((𝐼 − 𝑃𝐿 )𝑃𝑊 ) measures how much of 𝑊 falls outside L(𝑈 ⊥, 𝑈 ), which is exactly the noncommutative version of the number of arcs outside a directed cut, and ∥𝑃𝑊 − 𝑃𝐿 ∥ 1 measures the difference of 𝑊 from L(𝑈 ⊥, 𝑈 ). Indeed, for a directed graph 𝐺 = ( [𝑁 ], 𝐸) and a vertex partition [𝑁 ] = 𝐿 ⊔ 𝑅, if we set 𝑊 = span{𝐸𝑥 𝑦 : (𝑥, 𝑦) ∈ 𝐸} and 𝑈 = span{𝑒𝑥 : 𝑥 ∈ 𝐿}, then Tr((𝐼 − 𝑃𝐿 )𝑃𝑊 ) = |𝐸 \ (𝐿 × 𝑅)|,

∥𝑃𝑊 − 𝑃𝐿 ∥ 1 = |𝐸 △ (𝐿 × 𝑅)|.

The proof of Lemma 2.5 follows the same thresholded source–sink separation, now performed spectrally. Let {𝑀𝑘 } be an orthonormal basis of 𝑊 , and define a basis-independent PSD matrix with its spectral decomposition as 𝐵 :=

∑︁

𝑀𝑘 𝑀𝑘† =

𝑁 ∑︁

𝜆𝑖 𝑢𝑖 𝑢𝑖†,

𝑁 ≥ 𝜆1 ≥ · · · ≥ 𝜆𝑁 ≥ 0.

𝑖=1

𝑘

The matrix 𝐵 is the spectral analogue of the out-degree sequence. For the coordinate space defined by a directed graph, 𝐵 is diagonal with entries being precisely the out-degrees. In general, its eigenvectors {𝑢𝑖 } can be viewed as “vertices”, and the corresponding eigenvalue 𝜆𝑖 is the “outdegree” of 𝑢𝑖 . If E (𝑊 ) = 0, the preceding lemma already places 𝑊 inside an exact cut. Otherwise, the orthogonal decomposition 𝑈 ⊕ 𝑈 ⊥ is chosen by partitioning the eigenvectors as √︂ E (𝑊 ) 𝑈 := span{𝑢𝑖 : 𝜆𝑖 > 𝜃 }, 𝑈 ⊥ := span{𝑢𝑖 : 𝜆𝑖 ≤ 𝜃 }, where 𝜃 := . 𝑁 To define the analogue of in-degree, for 𝑖, 𝑗 ∈ [𝑁 ], set ∑︁ ∑︁ 𝜇 𝑗 := 𝑦𝑖 𝑗 . 𝑦𝑖 𝑗 := |𝑢𝑖† 𝑀𝑘 𝑢 𝑗 | 2, 𝑖

𝑘

Then 𝑦𝑖 𝑗 measures the flow from 𝑢𝑖 to 𝑢 𝑗 , and 𝜇 𝑗 is the “in-degree” of 𝑢 𝑗 . Naturally, the 𝑖-th row sum of 𝑦𝑖 𝑗 equals 𝜆𝑖 . One can verify that the matrix-space energy satisfies the noncommutative counterpart of Equation (2): ∑︁ E (𝑊 ) = 𝜆𝑗 𝜇𝑗 . 𝑗

All the flows from 𝑈 to 𝑈 ⊥ , i.e., from high eigenspace to low eigenspace, are contained in the cut space L(𝑈 ⊥, 𝑈 ), so the mass of 𝑊 outside L(𝑈 ⊥, 𝑈 ) is ∑︁ 𝑦𝑖 𝑗 . Tr((𝐼 − 𝑃𝐿 )𝑃𝑊 ) = 𝜆𝑖 ≤𝜃 or 𝜆 𝑗 >𝜃

Observe that the summation can be bounded by the sum of rows with 𝜆𝑖 ≤ 𝜃 plus the sum of columns with 𝜆 𝑗 > 𝜃 , which correspond to deleted out-degrees and deleted in-degrees respectively 10

in the classical picture. Thus Tr((𝐼 − 𝑃𝐿 )𝑃𝑊 ) ≤

∑︁ 𝜆𝑖 ≤𝜃

𝜆𝑖 +

∑︁

𝜇𝑗 ≤ 𝑁𝜃 +

√︁ 1 ∑︁ E (𝑊 ) 𝜆𝑗 𝜇𝑗 ≤ 𝑁 𝜃 + = 2 𝑁 · E (𝑊 ). 𝜃 𝜃

𝜆 𝑗 >𝜃

The supersaturation and stability statements follow from the same classical reasoning. Since dim(L(𝑈 ⊥, 𝑈 )) ≤ 𝑁 2 /4, the excess dimension of 𝑊 above 𝑁 2 /4 must lie outside the L(𝑈 ⊥, 𝑈 ), which gives the supersaturation. For the stability, small energy implies that most of𝑊 lies inside L(𝑈 ⊥, 𝑈 ), but 𝑊 has nearly maximal dimension, so L(𝑈 ⊥, 𝑈 ) must also be nearly maximal. Thus 𝑈 is nearly balanced, and 𝑊 is close to L(𝑈 ⊥, 𝑈 ). Quantum impossibility for 𝑞 ≤ 4 in the unweighted setting. The quantum proof now follows the outline of the classical one. For 𝑞 ≤ 3, averaging gives a space 𝑊𝑎 of dimension at least 𝑁 2 /3, noticeably larger than the extremal threshold 𝑁 2 /4, so supersaturation immediately gives E (𝑊𝑎 ) = Ω(𝑁 3 ). For 𝑞 = 4, suppose toward a contradiction that there is a sequence of orthogonal decompositions whose total energy is 𝑜 (𝑁 3 ). By averaging, one of the four spaces, say 𝑊1 , has dimension at least 𝑁 2 /4. Its energy is also 𝑜 (𝑁 3 ), so supersaturation forces dim(𝑊1 ) = (1/4 + 𝑜 (1))𝑁 2 . Stability then gives an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ such that, writing 𝐿 = L(𝑈 ⊥, 𝑈 ), dim(𝑈 ), dim(𝑈 ⊥ ) = (1/2 + 𝑜 (1))𝑁

∥𝑃𝑊1 − 𝑃𝐿 ∥ 1 = 𝑜 (𝑁 2 ).

and

We next round the approximate cut structure to an exact one. Replace 𝑊1 by L(𝑈 ⊥, 𝑈 ) and adjust the remaining three spaces so that the four still form a complete orthogonal decomposition. The adjustment can be done within a trace distance of 𝑜 (𝑁 2 ) and changes the total energy by only 𝑜 (𝑁 3 ). After rounding, the first color is supported on L(𝑈 ⊥, 𝑈 ) and hence vanishes on the diagonal block L(𝑈 , 𝑈 ). Projecting the other three spaces to L(𝑈 , 𝑈 ) gives a decomposition of the smaller space L(𝑈 , 𝑈 ) with only three colors. Each basis matrix 𝑀𝑘 from one of the remaining three color spaces lies in L(𝑈 ⊥, 𝑈 ) ⊥ . Relative to the decomposition 𝑈 ⊕ 𝑈 ⊥ , it therefore has the block form 𝑋𝑘 0 𝑀𝑘 = , where 𝑋𝑘 ∈ L(𝑈 , 𝑈 ), 𝑌𝑘 ∈ L(𝑈 , 𝑈 ⊥ ), 𝑍𝑘 ∈ L(𝑈 ⊥, 𝑈 ⊥ ). 𝑌𝑘 𝑍𝑘 Multiplication preserves the upper-left block: 𝑀𝑘 𝑀ℓ =

𝑋𝑘 𝑋 ℓ ∗

0 ∗

and hence ∥𝑀𝑘 𝑀ℓ ∥ 2𝐹 ≥ ∥𝑋𝑘 𝑋 ℓ ∥ 2𝐹 . Summing this inequality and using the energy formula (3) shows that restricting to L(𝑈 , 𝑈 ) does not increase the energy. Since dim(𝑈 ) = (1/2 +𝑜 (1))𝑁 , applying the 3-color case gives Ω(dim(𝑈 ) 3 ) = Ω(𝑁 3 ) total energy in L(𝑈 , 𝑈 ), and thus in the original four-color decomposition, which contradicts the assumption that the total energy is 𝑜 (𝑁 3 ). General quantum messages. In the classical LOCAL model, there is essentially no loss in starting with a uniform random seed: unbounded local computation can transform sufficiently many 11

uniform bits into any desired finite distribution. The quantum setting is different. The bipartite state shared across an edge after communication may have nonuniform Schmidt coefficients, so it cannot be assumed to be maximally entangled.4 Since the Schmidt bases can be absorbed into the local measurement, it suffices to consider states of the form |Ψ⟩ =

𝑁 ∑︁

𝜆 𝑗 | 𝑗⟩ A ⊗ | 𝑗⟩ B ,

where

𝜆 𝑗 ≥ 0,

𝑗=1

𝑁 ∑︁

𝜆 2𝑗 = 1.

𝑗=1

Each processor initially prepares |Ψ⟩ AB , then sends register B to its successor, and finally performs the same 𝑞-outcome projective measurement {𝑃𝑎 }𝑎∈ [𝑞 ] . 5 As before, we write 𝑊𝑎 for the matrix space associated with 𝑃𝑎 , and let {𝑀𝑎,𝑘 }𝑘 be an orthonormal basis of 𝑊𝑎 . Setting the weight matrix Λ = diag(𝜆1, . . . , 𝜆𝑁 ), the local collision probability becomes ∑︁ ∑︁ Pr[𝑐𝑖 = 𝑐𝑖+1 ] = EΛ (𝑊𝑎 ), where EΛ (𝑊𝑎 ) = ∥Λ𝑀𝑎,𝑘 Λ𝑀𝑎,ℓ Λ∥ 2𝐹 . 𝑎∈ [𝑞 ]

𝑘,ℓ

The quantity EΛ (𝑊𝑎 ) is precisely the Λ-energy of 𝑊𝑎 defined in Definition 1.3. Consequently, the Í general quantum message case is equivalent to lower bounding the total energy 𝑎∈ [𝑞 ] EΛ (𝑊𝑎 ) by a constant independent of 𝑁 , {𝑊𝑎 } and Λ, as stated in Theorem 1.6. A similar extremal structure persists in the weighted setting, but dimension is replaced by mass weighted by Λ. For a matrix space 𝑊 with orthonormal basis {𝑀𝑘 }, define its Λ-mass as ∑︁ 𝑚 Λ (𝑊 ) := ∥Λ𝑀𝑘 Λ∥ 2𝐹 . 𝑘

Operationally, this is the probability of obtaining the outcome associated with 𝑊 . Theorem 2.6 (Informal version of Theorem 5.4). If EΛ (𝑊 ) = 0, then 𝑚 Λ (𝑊 ) ≤ 1/4. After restricting to the support of Λ, equality forces an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ satisfying 1. (cut space structure) 𝑊 = L(𝑈 ⊥, 𝑈 ); 2. (balanced weight) Tr(Λ2 Π𝑈 ) = Tr(Λ2 Π𝑈 ⊥ ) = 21 ; 3. (Λ-invariance) Λ𝑈 = 𝑈 and Λ𝑈 ⊥ = 𝑈 ⊥ ; where Π𝑈 and Π𝑈 ⊥ are the orthogonal projectors onto 𝑈 and 𝑈 ⊥ . Thus the extremizer is again a complete cut space, but the balance is now measured by weight rather than dimension. In the classical weighted graph picture, the extremizer is a complete directed cut 𝐿 × 𝑅 whose two sides each carry half of the total vertex weight. The invariance condition is specific to the quantum setting. Classically, 𝑈 and 𝑈 ⊥ are spanned by standard basis vectors, so a diagonal Λ automatically preserves them. We next need a robust version of this extremal statement. Weighted supersaturation follows from observing that mass is the marginal probability of an outcome, while energy is the probability 4 A maximally entangled state can be converted into any bipartite pure state by local operations assisted by further

classical communication [NC10], but that additional communication is unavailable in our one-way one-round model. 5 Projective measurement suffices in this setting: Since we allow arbitrary quantum messages, we can use Naimark’s dilation theorem to realize any POVM as a projective measurement [NC10].

of seeing that outcome at two adjacent processors. A bounded-dependence inequality [GKDV89] then implies that mass 1/4+𝜂 forces Ω(𝜂) energy; see Lemma 6.4. We prove the following weighted stability theorem. Theorem 2.7 (Informal version of Theorem 5.6). If 𝑊 has Λ-mass 1/4 and Λ-energy 𝜖 = 𝑜 (1), then there exist a nearby PSD weight matrix Λ′ and a nearby cut space 𝑊 ′ = L(𝑈 ⊥, 𝑈 ) such that 𝑊 ′ has Λ′ -mass 1/4 and Λ′ -energy exactly zero. As in the unweighted proof, we apply the spectral source–sink decomposition to the weighted Í out-degree matrix 𝐵 := 𝑘 𝑀𝑘 Λ2 𝑀𝑘†, where {𝑀𝑘 } is an orthonormal basis of𝑊 . Setting the threshold √ to 𝜖 gives a candidate split ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ , and hence a candidate cut space 𝑊 ′ = L(𝑈 ⊥, 𝑈 ). If Λ already preserves 𝑈 ⊕ 𝑈 ⊥ , then the same argument as in the unweighted case will show that 𝑊 is close to 𝑊 ′ . Otherwise, we need to find a nearby Λ′ that does. We construct Λ′ by deleting the off-diagonal blocks of Λ with respect to 𝑈 ⊕ 𝑈 ⊥ and then rescaling the two diagonal blocks so that each side carries half of the weight. This makes (𝑊 ′, Λ′ ) exact zero-energy pair with mass 1/4. To show that it remains close to (𝑊 , Λ), the key step is to prove that small energy 𝜖 implies that Λ approximately preserves the split. Specifically, we need to control the off-diagonal quantity 𝛿 := ∥Π𝑈 ΛΠ𝑈 ⊥ ∥ 2𝐹 . We prove that 𝛿 is small by switching to a view of quantum state discrimination. Consider the two subnormalized states 𝜎0 := ΛΠ𝑈 ⊥ Λ, 𝜎1 := ΛΠ𝑈 Λ. Their pretty good measurement is essentially {Π𝑈 ⊥ , Π𝑈 }, and a direct calculation shows that its total error is exactly 2𝛿. Thus, instead of bounding this off-diagonal block directly, we explicitly √ construct a measurement that distinguishes 𝜎0 from 𝜎1 with 𝑂 ( 𝜖) error; see Lemma 5.8. The √ pretty-good-measurement bound [BK02] then implies 𝛿 = 𝑂 ( 𝜖), so Λ approximately preserves 𝑈 ⊕ 𝑈 ⊥ . Combining this approximate invariance with the low-row/high-column estimate gives the desired closeness of (𝑊 , Λ) to (𝑊 ′, Λ′ ). Finally, by plugging the proof, we can prove É weighted stability theorem into the previous 4-color Í that any decomposition 𝑎∈ [4] 𝑊𝑎 , under any weight Λ, has a total Λ-energy 𝑎∈ [4] EΛ (𝑊𝑎 ) = Ω(1). This gives a constant lower bound on the local collision probability for arbitrary quantum messages, which proves Theorem 1.1. POVMs and PSD weight matrices. In the formal proof, we extend the definitions of Λ-mass 𝑚 Λ (𝑊 ) and Λ-energy EΛ (𝑊 ) from a matrix space 𝑊 (equivalently its orthogonal projectors 𝑃𝑊 ) and a diagonal weight matrix Λ to an arbitrary PSD operator 𝑃 ∈ L(ℂ𝑁 ×𝑁 ) and arbitrary PSD weight matrix Λ; see Definition 4.1. This is needed to address two technical caveats. First, in the four-color reduction, after rounding the first color space𝑊1 to the exact off-diagonal space L(𝑈 ⊥, 𝑈 ), we restrict the other three spaces {𝑊𝑎 }2≤𝑎≤4 to the diagonal block L(𝑈 , 𝑈 ). Although the original spaces are orthogonal, their restrictions need not remain orthogonal, so the 𝑞 = 3 case of Conjecture 2.3 does not apply as stated. Nevertheless, the operators {𝑃𝑊𝑎 }2≤𝑎≤4 after restriction still form a complete POVM. It is therefore necessary to generalize the definitions of mass and energy from orthogonal projectors onto matrix spaces to general operators. Second, the split 𝑈 ⊕𝑈 ⊥ produced by the stability theorem need not be aligned with the original Schmidt basis. Consequently, the new weight matrix Λ′ need not be diagonal, but it remains PSD 13

and satisfies ∥Λ′ ∥ 𝐹 = 1. Every such Λ′ can be vectorized as a bipartite quantum state vec( Λ̄′ ), and the quantum algorithm using this state produces the corresponding Λ′ -mass and Λ′ -energy; see Lemma 4.7. Thus our formal definitions do not require the weight matrix to be diagonal.

Preliminaries

3.1

Matrix Norms

Notation and matrix norms. Given two linear spaces 𝑆 and 𝑇 , we denote by L(𝑆,𝑇 ) the space of linear operators from 𝑆 to 𝑇 , L(𝑆) := L(𝑆, 𝑆), denote by 𝑆 ⊥ the orthogonal complement of 𝑆, and denote by Π𝑆 the orthogonal projector onto 𝑆. Given a matrix 𝑋 ∈ ℂ𝑀 ×𝑁 , we denote by 𝑋¯ the conjugate of 𝑋 , 𝑋 ⊤ the transpose of 𝑋 , 𝑋 † := 𝑋¯ ⊤ the conjugate transpose of 𝑋 , and 𝑋 + the Moore–Penrose inverse (pseudoinverse) of 𝑋 . Definition 3.1 (Frobenius norm). Given a matrix 𝑋 ∈ ℂ𝑀 ×𝑁 , the Frobenius norm of 𝑋 is defined as √︄∑︁ √︁ † ∥𝑋 ∥ 𝐹 := Tr(𝑋 𝑋 ) = |𝑋𝑖,𝑗 | 2 . 𝑖,𝑗

Definition 3.2 (Schatten 𝑝-norm). Given 𝑝 ∈ [1, ∞] and any matrix 𝑋 ∈ ℂ𝑀 ×𝑁 , the Schatten 𝑝-norm of 𝑋 is defined as 1/𝑝 ∥𝑋 ∥ 𝑝 := Tr(|𝑋 |𝑝 ) for 𝑝 ∈ [1, ∞), ∥𝑋 ∥ ∞ = max ∥𝑋 𝑣 ∥ 2, ∥𝑣 ∥ 2 =1

√ where |𝑋 | := 𝑋 †𝑋 . In particular, ∥𝑋 ∥ 1 is the trace norm, ∥𝑋 ∥ 2 coincides with ∥𝑋 ∥ 𝐹 , and ∥𝑋 ∥ ∞ is the operator norm. Fact 3.3 (Schatten Hölder’s inequality). Given 𝑝, 𝑞 ∈ [1, ∞] such that 𝑝1 + 𝑞1 = 1, for any matrices 𝑋, 𝑌 ∈ ℂ𝑀 ×𝑁 , we have | Tr(𝑋 †𝑌 )| ≤ ∥𝑋 ∥ 𝑝 ∥𝑌 ∥𝑞

and

∥𝑋 †𝑌 ∥ 1 ≤ ∥𝑋 ∥ 𝑝 ∥𝑌 ∥𝑞 .

Vectorization. We introduce a useful correspondence between matrices and bipartite vectors. Let A := ℂ𝑀 and B := ℂ𝑁 , with standard bases {𝑒𝑖 }𝑖 ∈ [𝑀 ] and {𝑒 𝑗 } 𝑗 ∈ [𝑁 ] , respectively. Let 𝐸𝑖,𝑗 ∈ ℂ𝑀 ×𝑁 be the matrix unit with a 1 in entry (𝑖, 𝑗) and 0 elsewhere. Define vec : ℂ𝑀 ×𝑁 → A ⊗ B

vec(𝐸𝑖,𝑗 ) := 𝑒𝑖 ⊗ 𝑒 𝑗 .

Given a space 𝑊 ⊆ ℂ𝑀 ×𝑁 , we abuse the notation vec(𝑊 ) := {vec(𝐴) : 𝐴 ∈ 𝑊 } ⊆ ℂ𝑀 ⊗ ℂ𝑁 . We present some useful vectorization identities. For vectors 𝑢 ∈ A and 𝑣 ∈ B, vec(𝑢𝑣 ⊤ ) = 𝑢 ⊗ 𝑣,

vec(𝑢𝑣 † ) = 𝑢 ⊗ 𝑣¯ .

For matrices 𝑋, 𝑌 ∈ ℂ𝑀 ×𝑁 , vectorization preserves the Hilbert–Schmidt inner product: ⟨𝑋, 𝑌 ⟩ := Tr(𝑋 †𝑌 ) = ⟨vec(𝑋 ), vec(𝑌 )⟩. 14

For 𝑋 0 ∈ L(A) ℂ𝑀 ×𝑀 and 𝑋 1 ∈ L(B) ℂ𝑁 ×𝑁 , (𝑋 0 ⊗ 𝑋 1 )vec(𝑌 ) = vec 𝑋 0𝑌 𝑋 1⊤ . Finally, for 𝑋, 𝑌 ∈ ℂ𝑀 ×𝑁 , Tr B vec(𝑋 )vec(𝑌 ) † = 𝑋𝑌 †,

Tr A vec(𝑋 )vec(𝑌 ) † = 𝑋 ⊤𝑌¯ .

We also introduce a seminorm on bipartite matrices, called the Λ-norm, defined by the trace norm weighted by a PSD matrix Λ. Definition 3.4 (Λ-norm). Let Λ ∈ ℂ𝑁 ×𝑁 be a PSD matrix. Given any matrix 𝑋 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ), define its Λ-norm as ∥𝑋 ∥ Λ := ∥ (Λ ⊗ Λ̄)𝑋 (Λ ⊗ Λ̄) ∥ 1 . The factor Λ ⊗ Λ̄ arises naturally from the vectorization identity vec(Λ𝑋 Λ) = (Λ ⊗ Λ̄)vec(𝑋 ). The Λ-norm is only a seminorm for general PSD Λ, but becomes a proper norm if Λ ≻ 0.

3.2

Quantum Information

We introduce some tools from quantum information used in this paper. Definition 3.5 (Pretty Good Measurement). Given 𝜎0, 𝜎1 ⪰ 0, define 𝜎 := 𝜎0 +𝜎1 , and assume Tr(𝜎) = 1. The Pretty Good Measurement (PGM) is a 2-outcome POVM defined as √ √ 1 𝑀0 := 𝜎 +𝜎0 𝜎 + + Πker(𝜎 ) , 2

√ √ 1 𝑀1 := 𝜎 +𝜎1 𝜎 + + Π ker(𝜎 ) . 2

Lemma 3.6 ([BK02]). Given 𝜎0, 𝜎1 ⪰ 0 with Tr(𝜎0 + 𝜎1 ) = 1, define the optimal testing error OPT(𝜎0, 𝜎1 ) := min Tr(𝑀𝜎1 ) + Tr((𝐼 − 𝑀)𝜎0 ). 0⪯𝑀 ⪯𝐼

Let {𝑀0, 𝑀1 } be the pretty good measurement for 𝜎0, 𝜎1 . Then the PGM testing error PGM(𝜎0, 𝜎1 ) := Tr(𝑀0𝜎1 ) + Tr(𝑀1𝜎0 ) ≤ 2OPT(𝜎0, 𝜎1 ). The following lemma states that two matrices are close up to a unitary if their Gram matrices are close, which is a consequence of Uhlmann’s theorem. We use it later for rounding POVM elements in Lemma 6.8. Lemma 3.7. Given 𝑋, 𝑌 ∈ ℂ𝑁 ×𝑁 , there exists a unitary 𝑈 such that ∥𝑋 − 𝑈 𝑌 ∥ 2𝐹 ≤ ∥𝑋 †𝑋 − 𝑌 †𝑌 ∥ 1 . Proof. Let 𝛼 = Tr(𝑋 †𝑋 ) and 𝛽 = Tr(𝑌 †𝑌 ). If 𝛼 = 0, then 𝑋 = 0 and by setting 𝑈 = 𝐼 , we have ∥𝑋 − 𝑈 𝑌 ∥ 2𝐹 = ∥𝑌 ∥ 2𝐹 = Tr(𝑌 †𝑌 ) = ∥𝑌 †𝑌 ∥ 1 = ∥𝑋 †𝑋 − 𝑌 †𝑌 ∥ 1 . Similarly, if 𝛽 = 0, then 𝑈 = 𝐼 also works. 15

√︁ √ Now assume 𝛼, 𝛽 > 0. Define the quantum states 𝜌 := 𝑋 †𝑋 /𝛼, 𝜎 := 𝑌 †𝑌 /𝛽. Then 𝑋 / 𝛼 and 𝑌 / 𝛽 are purifications of 𝜌 and 𝜎 respectively. By Uhlmann’s theorem [NC10], we have " !# † 𝑋 𝑌 𝑈 √︁ max Tr √ = 𝐹 (𝜌, 𝜎), unitary 𝑈 𝛼 𝛽 √ √ where 𝐹 (𝜌, 𝜎) := ∥ 𝜌 𝜎 ∥ 1 is the fidelity between 𝜌 and 𝜎. As fidelity is homogeneous, we have 𝐹 (𝜌, 𝜎) = √1 𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ), and thus 𝛼𝛽

max

unitary 𝑈

Tr 𝑋 †𝑈 𝑌 = 𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ).

Moreover, as we optimize over all unitary, we have max Re Tr 𝑋 †𝑈 𝑌 = max Tr 𝑋 †𝑈 𝑌 = 𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ). unitary 𝑈

unitary 𝑈

Let 𝑈 be unitary that achieves Re(Tr(𝑋 †𝑈 𝑌 )) = 𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ). Expand the Frobenius norm ∥𝑋 − 𝑈 𝑌 ∥ 2𝐹 = Tr(𝑋 †𝑋 ) + Tr(𝑌 †𝑌 ) − 2Re(Tr(𝑋 †𝑈 𝑌 )) = Tr(𝑋 †𝑋 ) + Tr(𝑌 †𝑌 ) − 2𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ). By the Powers–Størmer inequality [PS70, Lemma 4.1], we have √︁ √︁ ∥𝑋 †𝑋 − 𝑌 †𝑌 ∥ 1 ≥ ∥ 𝑋 †𝑋 − 𝑌 †𝑌 ∥ 2𝐹 . The right-hand side can be expanded as √︁ √︁ √︁ √︁ ∥ 𝑋 †𝑋 − 𝑌 †𝑌 ∥ 2𝐹 = Tr(𝑋 †𝑋 ) + Tr(𝑌 †𝑌 ) − 2 Tr( 𝑋 †𝑋 𝑌 †𝑌 ), and the cross term can be bounded as √︁ √︁ √︁ √︁ √︁ √︁ Tr( 𝑋 †𝑋 𝑌 †𝑌 ) ≤ ∥𝐼 ∥ ∞ ∥ 𝑋 †𝑋 𝑌 †𝑌 ∥ 1 = ∥ 𝑋 †𝑋 𝑌 †𝑌 ∥ 1 = 𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ). Thus

∥𝑋 †𝑋 − 𝑌 †𝑌 ∥ 1 ≥ Tr(𝑋 †𝑋 ) + Tr(𝑌 †𝑌 ) − 2𝐹 (𝑋 †𝑋, 𝑌 †𝑌 ) = ∥𝑋 − 𝑈 𝑌 ∥ 2𝐹 . □

3.3

Models in Distributed Computing

We recall the classical randomized LOCAL model and its quantum variant, and then specialize them to the setting studied in this paper. Definition 3.8 (LOCAL models). Let 𝐺 = (𝑉 , 𝐸) be an 𝑛-vertex graph. Each processor 𝑣 ∈ 𝑉 knows 𝑛, has a unique identifier ID𝑣 ∈ [ poly (𝑛)], and may receive a local input 𝑥 𝑣 . Computation proceeds in synchronous rounds. In each round, every processor performs unbounded local computation and exchanges messages of unbounded length with its neighbors in 𝐺. After the last round, it produces a local output 𝑦 𝑣 . 1. In the classical randomized LOCAL model, local computations and messages are classical, and 16

each processor may use private random bits. 2. In the quantum LOCAL model, each processor may perform arbitrary local quantum operations and messages may be quantum states. The processors have no shared randomness or prior entanglement. The locality, or round complexity, of a LOCAL algorithm is its number of communication rounds. We focus on the following problem. Definition 3.9 (Directed-cycle 𝑞-coloring). Fix an integer 𝑞 ≥ 2. Consider 𝑛 processors 𝑣 1, 𝑣 2, . . . , 𝑣𝑛 arranged on a directed cycle. Each processor initially knows the direction of the cycle. The directed-cycle 𝑞-coloring problem requires each processor 𝑣𝑖 to output a color 𝑐𝑖 ∈ [𝑞] such that (𝑐𝑖 )𝑖 ∈ [𝑛] is a proper 𝑞-coloring of the cycle; that is, 𝑐𝑖 ≠ 𝑐𝑖+1 for all 𝑖 ∈ [𝑛 − 1] and 𝑐𝑛 ≠ 𝑐 1 . For 𝑞 ≥ 3, proper 𝑞-colorings of cycles always exist. We say that a randomized or quantum LOCAL algorithm solves the directed-cycle 𝑞-coloring problem if it outputs a proper 𝑞-coloring with probability at least 1 − 1/poly (𝑛). Under this definition, the assumption of unique identifiers in Definition 3.8 can be dropped without loss of generality, since independently sampling each identifier from a sufficiently large set of size poly (𝑛) yields pairwise distinct identifiers with probability at least 1 − 1/poly (𝑛), which can be absorbed into the algorithm’s failure probability. Thus, throughout our analysis of randomized and quantum LOCAL algorithms, we assume that all processors are initially identical and execute the same local procedures. Finally, we recall some terminology from probability theory. Let (𝑋𝑖 )𝑖 ∈ [𝑛] be a distribution on a cycle of length 𝑛. The distribution is stationary if its law is invariant under cyclic shifts, i.e., (𝑋 1, 𝑋 2, . . . , 𝑋𝑛 ) and (𝑋 2, 𝑋 3, . . . , 𝑋𝑛 , 𝑋 1 ) are equal in law. It is 𝑘-dependent if, for any subsets 𝑈 , 𝑉 ⊆ [𝑛] with dist(𝑈 , 𝑉 ) > 𝑘, the random vectors (𝑋𝑖 )𝑖 ∈𝑈 and (𝑋𝑖 )𝑖 ∈𝑉 are independent, where dist denotes graph distance on the cycle. These notions extend naturally to stochastic processes (𝑋𝑡 )𝑡 ∈ℤ on the infinite line ℤ. In this paper, we focus on one-way one-round LOCAL algorithms on directed cycles, in which each processor 𝑣𝑖 only sends a single message to its successor 𝑣𝑖+1 (with 𝑣𝑛 sending to 𝑣 1 ) before computing its output. Any such algorithm, whether classical or quantum, outputs a stationary 1-dependent distribution, since the output at 𝑣𝑖 depends only on the states originating from 𝑣𝑖 −1 and 𝑣𝑖 .

Energy Formulation

In this section, we formally define the notions of Λ-mass and Λ-energy and establish their basic properties. These notions are defined for any PSD operators 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) and Λ ∈ ℂ𝑁 ×𝑁 . In particular, they apply when 𝑃 is an orthogonal projector onto a matrix subspace under the vectorization equivalence ℂ𝑁 ×𝑁 ℂ𝑁 ⊗ ℂ𝑁 , and, more generally, when 𝑃 is a POVM element on the same space. Definition 4.1 (Λ-mass and Λ-energy). Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) and PSD Λ ∈ ℂ𝑁 ×𝑁 , define the Λ-mass of 𝑃 by 𝑚 Λ (𝑃) := ∥𝑃 ∥ Λ = Tr 𝑃 (Λ2 ⊗ Λ̄2 ) ,

and the Λ-energy of 𝑃 by EΛ (𝑃) := Tr (Λ𝐴Λ𝐵) ,

where 𝐴 := Tr A ((Λ2 ⊗ 𝐼 )𝑃) ⊤, 𝐵 := Tr B ((𝐼 ⊗ Λ̄2 )𝑃).

Section 4.1 proves an equivalent spectral formula for Λ-energy, matching Definition 1.3 in the introduction. Section 4.2 then illustrates the definition through several examples, several of which already appear in the technical overview. Finally, Section 4.3 interprets mass and energy as probabilities arising from a specific quantum experiment, while Section 4.4 establishes properties of the energy that will be used in the main proof.

4.1

Spectral Formula

The following fact gives an alternative expression for Λ-energy, connecting it to the multiplicative structure of the corresponding matrix space. Lemma 4.2. Given 𝑃 and Λ as above, let {𝑀𝑘 }𝑘 ⊆ ℂ𝑁 ×𝑁 be any finite family of matrices satisfying ∑︁ 𝑃= vec(𝑀𝑘 )vec(𝑀𝑘 ) † . 𝑘

Then EΛ (𝑃) =

∑︁

∥Λ𝑀𝑘 Λ𝑀ℓ Λ∥ 2𝐹 .

𝑘,ℓ

Such {𝑀𝑘 }𝑘 always exists. In particular, it can be obtained by taking a spectral decomposition of 𝑃. Proof. Note that Λ is Hermitian, so Λ = Λ† and Λ̄ = Λ⊤ . For each 𝑀𝑘 , we have Tr A (Λ2 ⊗ 𝐼 )vec(𝑀𝑘 )vec(𝑀𝑘 ) † = Tr A (Λ ⊗ 𝐼 )vec(𝑀𝑘 )vec(𝑀𝑘 ) † (Λ ⊗ 𝐼 ) = Tr A vec(Λ𝑀𝑘 )vec(Λ𝑀𝑘 ) † = (Λ𝑀𝑘 ) ⊤ Λ𝑀𝑘 = (𝑀𝑘† Λ2 𝑀𝑘 ) ⊤, where the first equality is by cyclicity of partial trace, the equality is by (𝑋 0 ⊗ 𝑋 1 )vec(𝑌 ) = second ⊤ † ⊤ ¯ vec(𝑋 0𝑌𝑋 1 ), the third equality is by Tr A vec(𝑋 )vec(𝑌 ) = 𝑋 𝑌 . Then ∑︁ ∑︁ 𝐴 := Tr A ((Λ2 ⊗ 𝐼 )𝑃) ⊤ = Tr A ((Λ2 ⊗ 𝐼 )vec(𝑀𝑘 )vec(𝑀𝑘 ) † ) ⊤ = 𝑀𝑘† Λ2 𝑀𝑘 . 𝑘

𝑘

Similarly, we have Tr B (𝐼 ⊗ Λ̄2 )vec(𝑀𝑘 )vec(𝑀𝑘 ) † = Tr B (𝐼 ⊗ Λ̄)vec(𝑀𝑘 )vec(𝑀𝑘 ) † (𝐼 ⊗ Λ̄) = Tr B vec(𝑀𝑘 Λ)vec(𝑀𝑘 Λ) † = (𝑀𝑘 Λ) (𝑀𝑘 Λ) † = 𝑀𝑘 Λ2 𝑀𝑘†, and then

𝐵 := Tr B ((𝐼 ⊗ Λ̄2 )𝑃) =

∑︁ 𝑘

𝑀𝑘 Λ2 𝑀𝑘† .

Thus we have EΛ (𝑃) = Tr(Λ𝐴Λ𝐵) =

∑︁

Tr Λ𝑀𝑘† Λ2 𝑀𝑘 Λ𝑀ℓ Λ2 𝑀ℓ†

𝑘,ℓ

∑︁ Tr Λ𝑀ℓ† Λ𝑀𝑘† Λ · Λ𝑀𝑘 Λ𝑀ℓ Λ = ∥Λ𝑀𝑘 Λ𝑀ℓ Λ∥ 2𝐹 .

𝑘,ℓ

□ For completeness, we also show that Λ-mass can be expressed in a similar way, which matches the definition appearing in the technical overview. Lemma 4.3. Given the same setting as in Lemma 4.2, we have ∑︁ 𝑚 Λ (𝑃) = ∥Λ𝑀𝑘 Λ∥ 2𝐹 . 𝑘

Proof. By definition, we have ∑︁ 𝑚 Λ (𝑃) = Tr 𝑃 (Λ2 ⊗ Λ̄2 ) = Tr (Λ ⊗ Λ̄)vec(𝑀𝑘 )vec(𝑀𝑘 ) † (Λ ⊗ Λ̄) =

𝑘 ∑︁

∑︁ Tr vec(Λ𝑀𝑘 Λ)vec(Λ𝑀𝑘 Λ) † = ∥Λ𝑀𝑘 Λ∥ 2𝐹 .

𝑘

□

4.2

Examples

In this paper, we are mainly interested in the energy of an operator 𝑃 with 0 ⪯ 𝑃 ⪯ 𝐼 , as we will use it to analyze POVM elements. If we further restrict 𝑃 to be an orthogonal projector onto a matrix space 𝑊 , then the energy of 𝑃 captures the multiplicative structure of 𝑊 . Below are several illustrative examples. Example 4.4 (Energy of matrix space). Let Λ = 𝐼 . Let Π𝑊 be the orthogonal projector onto a matrix space 𝑊 ⊆ ℂ𝑁 ×𝑁 . Then 𝑚𝐼 (Π𝑊 ) = Tr(Π𝑊 ) = dim(𝑊 ), and by Lemma 4.2, we have ∑︁ E𝐼 (Π𝑊 ) = ∥𝑀𝑘 𝑀ℓ ∥ 2𝐹 , 𝑘,ℓ

where {𝑀𝑘 } is an orthonormal basis of 𝑊 . Thus E𝐼 (Π𝑊 ) measures the multiplicative energy of space 𝑊 . Moreover, E𝐼 (Π𝑊 ) = 0 if and only if 𝑊 2 := span{𝑋𝑌 : 𝑋, 𝑌 ∈ 𝑊 } = {0}. Example 4.5 (Counting 2-walks in a graph). Let Λ = 𝐼 . Given a directed graph 𝐺 = (𝑉 , 𝐸), define a matrix space 𝑊 := span{𝐸𝑢𝑣 : (𝑢, 𝑣) ∈ 𝐸} ⊆ ℂ𝑉 ×𝑉 . Then for the orthogonal projector Π𝑊 onto 𝑊 , we have 𝑚𝐼 (Π𝑊 ) = |𝐸|, and ∑︁ ∑︁ E𝐼 (Π𝑊 ) = ∥𝐸𝑢𝑣 𝐸𝑥 𝑤 ∥ 2𝐹 = 1𝑣=𝑥 = #{(𝑢, 𝑣, 𝑤) : (𝑢, 𝑣), (𝑣, 𝑤) ∈ 𝐸}, (𝑢,𝑣),(𝑥,𝑤 ) ∈𝐸

(𝑢,𝑣),(𝑥,𝑤 ) ∈𝐸

which counts the number of 2-walks in 𝐺. Moreover, E𝐼 (Π𝑊 ) = 0 if and only if 𝐺 is contained in a directed cut. Example 4.6 (Energy of a weighted graph). We extend the previous example to the setting where each node 𝑣 ∈ 𝑉 has a weight 𝑤 𝑣 ≥ 0, and define √ Λ := diag( 𝑤 𝑣 )𝑣 ∈𝑉 . Then 𝑚 Λ (Π𝑊 ) =

(𝑢,𝑣) ∈𝐸 𝑤𝑢 𝑤 𝑣 is the weighted sum of arcs in 𝐺, and

∑︁

EΛ (Π𝑊 ) =

∥Λ𝐸𝑢𝑣 Λ𝐸𝑥 𝑤 Λ∥ 2𝐹 =

∑︁

𝑤𝑢 𝑤 𝑣 𝑤 𝑤

2-walk (u,v,w) in 𝐺

(𝑢,𝑣),(𝑥,𝑤 ) ∈𝐸

is the weighted sum of 2-walks in 𝐺.

4.3

The Operational Interpretation

The next lemma characterizes the operational meanings of mass and energy: Λ-mass is the marginal probability of obtaining the outcome corresponding to POVM operator 𝑃, and Λ-energy is the probability of obtaining the corresponding outcomes for 𝑃 ⊗ 𝑃 on some quantum state specified by Λ. Lemma 4.7. Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 and PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, define a bipartite quantum state |Ψ⟩ := vec( Λ̄), and its reduced density matrices 𝜌 := Tr A (|Ψ⟩ ⟨Ψ|),

𝜌¯ := Tr B (|Ψ⟩ ⟨Ψ|).

Then we have 𝑚 Λ (𝑃) = Tr [𝑃 (𝜌 ⊗ 𝜌)] ¯ ,

EΛ (𝑃) = Tr [(𝑃 ⊗ 𝑃) (𝜌 ⊗ |Ψ⟩ ⟨Ψ| ⊗ 𝜌)] ¯ .

Proof. Since Λ is PSD, write the spectral decomposition ∑︁ ∑︁ Λ= 𝜆𝑖 |𝜑𝑖 ⟩ ⟨𝜑𝑖 | , Λ̄ = 𝜆𝑖 |𝜑¯𝑖 ⟩ ⟨𝜑¯𝑖 | , 𝑖

𝑖

where |𝜑𝑖 ⟩ are eigenvectors and 𝜆𝑖 ≥ 0 are eigenvalues of Λ. By vec(𝑥𝑦 † ) = 𝑥 ⊗ 𝑦, ¯ we have ∑︁ |Ψ⟩ = vec( Λ̄) = 𝜆𝑖 |𝜑¯𝑖 ⟩ ⊗ |𝜑𝑖 ⟩ , 𝑖

𝜌 = Tr A (|Ψ⟩ ⟨Ψ|) =

∑︁

𝜆𝑖2 |𝜑𝑖 ⟩ ⟨𝜑𝑖 | = Λ2,

and

𝜌¯ = Tr B (|Ψ⟩ ⟨Ψ|) =

𝑖

Then

∑︁ 𝑖

Tr(𝑃 (𝜌 ⊗ 𝜌)) ¯ = Tr(𝑃 (Λ2 ⊗ Λ̄2 )) = 𝑚 Λ (𝑃).

𝜆𝑖2 |𝜑¯𝑖 ⟩ ⟨𝜑¯𝑖 | = Λ̄2 .

By definition of 𝜌, we have Tr[(𝑃 ⊗ 𝑃) (𝜌 ⊗ |Ψ⟩ ⟨Ψ| ⊗ 𝜌)] ¯ =

∑︁

𝜆𝑎2 𝜆𝑐2 Tr [(𝑃 ⊗ 𝑃) (|𝜑𝑎 , Ψ, 𝜑¯𝑐 ⟩ ⟨𝜑𝑎 , Ψ, 𝜑¯𝑐 |)] .

(4)

𝑎,𝑐

If we write the spectral decomposition of 𝑃 as 𝑃 =

† 𝑘 vec(𝑀𝑘 )vec(𝑀𝑘 ) , then

Tr [(𝑃 ⊗ 𝑃) (|𝜑𝑎 , Ψ, 𝜑¯𝑐 ⟩ ⟨𝜑𝑎 , Ψ, 𝜑¯𝑐 |)] =

∑︁

𝑎,𝑐 2 |𝛾𝑘,ℓ | ,

(5)

𝑘,ℓ 𝑎,𝑐 where 𝛾𝑘,ℓ := ⟨𝜑𝑎 , Ψ, 𝜑¯𝑐 | (vec(𝑀𝑘 ) ⊗ vec(𝑀ℓ )). By definition of |Ψ⟩ and the fact that 𝜆𝑏 are real, we have ∑︁ 𝑎,𝑐 𝛾𝑘,ℓ = 𝜆𝑏 ⟨𝜑𝑎 , 𝜑¯𝑏 , 𝜑𝑏 , 𝜑¯𝑐 | vec(𝑀𝑘 ) ⊗ vec(𝑀ℓ )

= =

𝑏 ∑︁ 𝑏 ∑︁

𝜆𝑏 ⟨𝜑𝑎 , 𝜑¯𝑏 | vec(𝑀𝑘 ) · ⟨𝜑𝑏 , 𝜑¯𝑐 | vec(𝑀ℓ ) 𝜆𝑏 · vec(|𝜑𝑎 ⟩ ⟨𝜑𝑏 |) † vec(𝑀𝑘 ) · vec(|𝜑𝑏 ⟩ ⟨𝜑𝑐 |) † vec(𝑀ℓ ),

𝑏

where the last equality is by vec(𝑥𝑦 † ) = 𝑥 ⊗ 𝑦. ¯ As vectorization preserves the Hilbert–Schmidt inner product, we have vec(|𝜑𝑎 ⟩ ⟨𝜑𝑏 |) † vec(𝑀𝑘 ) = Tr (|𝜑𝑎 ⟩ ⟨𝜑𝑏 |) † 𝑀𝑘 = ⟨𝜑𝑎 | 𝑀𝑘 |𝜑𝑏 ⟩ . Thus 𝑎,𝑐 𝛾𝑘,ℓ =

∑︁

𝜆𝑏 ⟨𝜑𝑎 | 𝑀𝑘 |𝜑𝑏 ⟩ · ⟨𝜑𝑏 | 𝑀ℓ |𝜑𝑐 ⟩ = ⟨𝜑𝑎 | 𝑀𝑘 Λ𝑀ℓ |𝜑𝑐 ⟩ .

𝑏

Plugging this into (5) and then (4), we have Tr[(𝑃 ⊗ 𝑃) (𝜌 ⊗ |Ψ⟩ ⟨Ψ| ⊗ 𝜌)] ¯ =

∑︁

𝜆𝑎2 𝜆𝑐2

𝑎,𝑐

∑︁

|⟨𝜑𝑎 | 𝑀𝑘 Λ𝑀ℓ |𝜑𝑐 ⟩| 2

𝑘,ℓ

∑︁ ∑︁

∑︁

| ⟨𝜑𝑎 | Λ𝑀𝑘 Λ𝑀ℓ Λ |𝜑𝑐 ⟩ | 2

𝑘,ℓ 𝑎,𝑐

∥Λ𝑀𝑘 Λ𝑀ℓ Λ∥ 2𝐹 = EΛ (𝑃),

𝑘,ℓ

where the second equality follows from Λ |𝜑𝑥 ⟩ = 𝜆𝑥 |𝜑𝑥 ⟩, and the third equality follows because the vectors |𝜑𝑥 ⟩ form an orthonormal basis, and the last equality is by Lemma 4.2. □

4.4

Useful Properties

We prove some natural properties of the energy function, which will be used in later sections. The first fact is that the energy is monotone with respect to PSD ordering. Fact 4.8. Given two PSD operators 𝑃, 𝑄 ∈ L(ℂ𝑁 ⊗ℂ𝑁 ), and PSD Λ ∈ ℂ𝑁 ×𝑁 , if 𝑃 ⪯ 𝑄, then EΛ (𝑃) ≤ EΛ (𝑄).

Proof. Let 𝑅 = 𝑄 − 𝑃, then 𝑅 ⪰ 0. Define EΛ (𝑄) − EΛ (𝑃) = EΛ (𝑃 + 𝑅) − EΛ (𝑃) = Tr(Λ𝐴𝑃 Λ𝐵𝑅 ) + Tr(Λ𝐴𝑅 Λ𝐵𝑃 ) + Tr(Λ𝐴𝑅 Λ𝐵𝑅 ), where 𝐴𝑃 := Tr A ((Λ2 ⊗ 𝐼 )𝑃) ⊤ ⪰ 0, 𝐵𝑃 := Tr B ((𝐼 ⊗ Λ̄2 )𝑃) ⪰ 0, and 𝐴𝑅 , 𝐵𝑅 are defined similarly for 𝑅. Since 𝐴𝑃 , 𝐵𝑃 , 𝐴𝑅 , 𝐵𝑅 ⪰ 0, the three terms Tr(Λ𝐴𝑃 Λ𝐵𝑅 ), Tr(Λ𝐴𝑅 Λ𝐵𝑃 ), and Tr(Λ𝐴𝑅 Λ𝐵𝑅 ) are all non-negative, and thus EΛ (𝑄) − EΛ (𝑃) ≥ 0. □ We conclude with a Λ-Lipschitz lemma for the energy function. Namely, for fixed 𝑃, EΛ (𝑃) is Lipschitz continuous in Λ with respect to the Frobenius norm. Lemma 4.9. Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 , and PSDs Λ, Λ′ ∈ ℂ𝑁 ×𝑁 such that ∥Λ∥ 𝐹 = ∥Λ′ ∥ 𝐹 = 1, we have |EΛ (𝑃) − EΛ′ (𝑃)| ≤ 6 ∥Λ − Λ′ ∥ 𝐹 . Proof. Let Δ := Λ − Λ′ . Define 𝐴 := Tr A ((Λ2 ⊗ 𝐼 )𝑃) ⊤, 𝐵 := Tr B ((𝐼 ⊗ Λ̄2 )𝑃), with 𝐴′, 𝐵 ′ defined similarly for Λ′ . Then we have |EΛ (𝑃) − EΛ′ (𝑃)| = | Tr(Λ𝐴Λ𝐵) − Tr(Λ′𝐴′ Λ′ 𝐵 ′ )| = | Tr(Λ𝐴Λ𝐵) − Tr(Λ′𝐴′ Λ′ 𝐵) + Tr(Λ′𝐴′ Λ′ 𝐵) − Tr(Λ′𝐴′ Λ′ 𝐵 ′ )| ≤ | Tr((Λ𝐴Λ − Λ′𝐴′ Λ′ )𝐵)| + | Tr(Λ′𝐴′ Λ′ (𝐵 − 𝐵 ′ ))| ≤ ∥Λ𝐴Λ − Λ′𝐴′ Λ′ ∥ 1 ∥𝐵∥ ∞ + ∥Λ′𝐴′ Λ′ ∥ 1 ∥𝐵 − 𝐵 ′ ∥ ∞,

(6)

where the last inequality follows from Hölder’s inequality | Tr(𝑋𝑌 )| ≤ ∥𝑋 ∥ 1 ∥𝑌 ∥ ∞ . First, observe that 𝐴′, 𝐵 ⪯ 𝐼 , and thus ∥𝐵∥ ∞ ≤ 1, and ∥Λ′𝐴′ Λ′ ∥ 1 = Tr(Λ′𝐴′ Λ′ ) ≤ Tr(Λ′2 ) = 1. Next, we bound ∥Λ𝐴Λ − Λ′𝐴′ Λ′ ∥ 1 . By definition, we have ⊤ Λ𝐴Λ − Λ′𝐴′ Λ′ = Tr A (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄) − (Λ′ ⊗ Λ̄′ )𝑃 (Λ′ ⊗ Λ̄′ ) . Then ∥Λ𝐴Λ − Λ′𝐴′ Λ′ ∥ 1 ≤ ∥ (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄) − (Λ′ ⊗ Λ̄′ )𝑃 (Λ′ ⊗ Λ̄′ ) ∥ 1 ≤ ∥ (Λ ⊗ Λ̄ − Λ′ ⊗ Λ̄′ )𝑃 (Λ ⊗ Λ̄) ∥ 1 + ∥ (Λ′ ⊗ Λ̄′ )𝑃 (Λ ⊗ Λ̄ − Λ′ ⊗ Λ̄′ ) ∥ 1 ≤ ∥Λ ⊗ Λ̄ − Λ′ ⊗ Λ̄′ ∥ 𝐹 ∥𝑃 (Λ ⊗ Λ̄) ∥ 𝐹 + ∥ (Λ′ ⊗ Λ̄′ )𝑃 ∥ 𝐹 ∥Λ ⊗ Λ̄ − Λ′ ⊗ Λ̄′ ∥ 𝐹 , where the first inequality follows from contractivity of trace norm under partial trace, the second is by triangle inequality, and the last inequality is by Hölder’s inequality ∥𝑋𝑌 ∥ 1 ≤ ∥𝑋 ∥ 𝐹 ∥𝑌 ∥ 𝐹 . Notice that √︃ √︃ ∥𝑃 (Λ ⊗ Λ̄) ∥ 𝐹 = Tr((Λ ⊗ Λ̄)𝑃 2 (Λ ⊗ Λ̄)) ≤ Tr(Λ2 ⊗ Λ̄2 ) = 1, and similarly ∥ (Λ′ ⊗ Λ̄′ )𝑃 ∥ 𝐹 ≤ 1. Thus ∥Λ𝐴Λ − Λ′𝐴′ Λ′ ∥ 1 ≤ 2∥ (Λ ⊗ Λ̄) − (Λ′ ⊗ Λ̄′ ) ∥ 𝐹 . Moreover, ∥Λ ⊗ Λ̄ − Λ′ ⊗ Λ̄′ ∥ 𝐹 ≤ ∥ (Λ − Λ′ ) ⊗ Λ̄∥ 𝐹 + ∥Λ′ ⊗ (Λ − Λ′ ) ∥ 𝐹 = ∥Δ∥ 𝐹 ∥Λ∥ 𝐹 + ∥Λ′ ∥ 𝐹 ∥Δ∥ 𝐹 = 2∥Δ∥ 𝐹 .

Thus we have ∥Λ𝐴Λ − Λ′𝐴′ Λ′ ∥ 1 ≤ 4∥Δ∥ 𝐹 . Finally, we bound ∥𝐵 − 𝐵 ′ ∥ ∞ . By definition, we have 𝐵 − 𝐵 ′ = Tr B (𝐼 ⊗ Λ̄2 )𝑃 − (𝐼 ⊗ Λ̄′2 )𝑃 = Tr B (𝐼 ⊗ ( Λ̄2 − Λ̄′2 ))𝑃 . To bound its ∞-norm, consider any unit vectors 𝑥, 𝑦 ∈ ℂ𝑁 . We have | ⟨𝑥, (𝐵 − 𝐵 ′ )𝑦⟩ | = | Tr((𝐵 − 𝐵 ′ )𝑦𝑥 † )| = | Tr[Tr B ((𝑦𝑥 † ⊗ ( Λ̄2 − Λ̄′2 ))𝑃)] | = | Tr[(𝑦𝑥 † ⊗ ( Λ̄2 − Λ̄′2 ))𝑃] | ≤ ∥𝑦𝑥 † ⊗ ( Λ̄2 − Λ̄′2 ) ∥ 1 = ∥ (Λ2 − Λ′2 ) ∥ 1 . Notice that ∥Λ2 − Λ′2 ∥ 1 ≤ ∥ (Λ − Λ′ )Λ∥ 1 + ∥Λ′ (Λ − Λ′ ) ∥ 1 ≤ ∥Δ∥ 𝐹 ∥Λ∥ 𝐹 + ∥Λ′ ∥ 𝐹 ∥Δ∥ 𝐹 = 2∥Δ∥ 𝐹 . Thus we have ∥𝐵 − 𝐵 ′ ∥ ∞ ≤ 2∥Δ∥ 𝐹 . Plugging the above bounds into (6), we have |EΛ (𝑃) − EΛ′ (𝑃)| ≤ 4∥Δ∥ 𝐹 + 2∥Δ∥ 𝐹 = 6∥Δ∥ 𝐹 .

□

Zero-Energy Operators

This section establishes the structural results on low-energy operators that drive the four-color impossibility proof. We first show that a POVM operator with zero Λ-energy has Λ-mass at most 1/4 and characterize the extremal case as the projector onto an off-diagonal matrix space associated with a balanced Λ-invariant decomposition (Theorem 5.4). We then prove a robust version: any POVM operator of mass 1/4 and small energy can be approximated, together with its weight matrix, by an exact zero-energy extremizer (Theorem 5.6). The exact characterization yields the reduction from four to three colors in Section 6.3.1, while the robust theorem is used for the general impossibility proof in Section 6.3.2.

5.1

Structure of Zero-Energy Operators

In the following, we characterize the structure of operators with exactly zero energy. We first restrict our attention to strictly positive Λ to avoid degeneracy. Definitions. Assume we have a PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 , and PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1 and Λ ≻ 0. Write the spectral decomposition of 𝑃 as ∑︁ 𝑃= vec(𝑀𝑘 )vec(𝑀𝑘 ) †, 𝑘

where 𝑀𝑘 ∈ ℂ𝑁 ×𝑁 are pairwise orthogonal matrices. Define the corresponding matrix space 𝑊 := span{𝑀𝑘 } ⊆ ℂ𝑁 ×𝑁 . Then 𝑊 defines an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ ,

where 𝑈 :=

∑︁ 𝑋 ∈𝑊

Im(𝑋 ).

We then prove two helper lemmas. Lemma 5.1. If EΛ (𝑃) = 0, then 𝑃 ⪯ Π𝑊 ⪯ ΠL( (Λ𝑈 ) ⊥,𝑈 ) = Π𝑈 ⊗ Π̄ (Λ𝑈 ) ⊥ where Λ𝑈 := {Λ𝑥 : 𝑥 ∈ 𝑈 }, and Π𝑆 denotes the orthogonal projection onto a linear space 𝑆. Proof. By 0 ⪯ 𝑃 ⪯ 𝐼 , we have that ∥𝑀𝑘 ∥ 2𝐹 = ∥vec(𝑀𝑘 ) ∥ 2 ≤ 1. Thus 𝑃=

∑︁

vec(𝑀𝑘 )vec(𝑀𝑘 ) † ⪯

𝑘

∑︁ 𝑘

1 vec(𝑀𝑘 )vec(𝑀𝑘 ) † = Π𝑊 . 2 ∥𝑀𝑘 ∥ 𝐹

(7)

By zero energy assumption and Lemma 4.2, we have ∑︁ EΛ (𝑃) = ∥Λ𝑀𝑘 Λ𝑀ℓ Λ∥ 2𝐹 = 0. 𝑘,ℓ

Together with Λ ≻ 0, it implies that 𝑀𝑘 Λ𝑀ℓ = 0 for any 𝑘, ℓ. As {𝑀𝑘 } spans 𝑊 , we have 𝑋 Λ𝑌 = 0

for any 𝑋, 𝑌 ∈ 𝑊 .

Í For any 𝑋 ∈ 𝑊 , we have Im(𝑋 ) ⊆ 𝑌 ∈𝑊 Im(𝑌 ) = 𝑈 . Moreover, we claim that Λ𝑈 ⊆ ker(𝑋 ). Indeed, for any vector 𝑢 ∈ Λ𝑈 , there exists 𝑌1, . . . , 𝑌dim(𝑊 ) ∈ 𝑊 and 𝑧 1, . . . 𝑧 dim(𝑊 ) ∈ ℂ𝑁 such that Í Í 𝑢 = Λ 𝑖 𝑌𝑖 𝑧𝑖 . Then 𝑋𝑢 = 𝑖 (𝑋 Λ𝑌𝑖 )𝑧𝑖 = 0, since 𝑋 Λ𝑌𝑖 = 0 for 𝑋, 𝑌𝑖 ∈ 𝑊 . Thus Im(𝑋 ) ⊆ 𝑈 which implies

and

Λ𝑈 ⊆ ker(𝑋 )

for any 𝑋 ∈ 𝑊 ,

𝑊 ⊆ L((Λ𝑈 ) ⊥, 𝑈 ).

Thus

Π𝑊 ⪯ ΠL( (Λ𝑈 ) ⊥,𝑈 ) .

(8)

Let {𝑢𝑖 } and {𝑣𝑖 } be orthonormal bases of 𝑈 and (Λ𝑈 ) ⊥ , respectively. Then Π L( (Λ𝑈 ) ⊥,𝑈 ) =

∑︁

† ∑︁ ∑︁ 𝑢𝑖 𝑢𝑖† ⊗ vec 𝑢𝑖 𝑣 †𝑗 vec 𝑢𝑖 𝑣 †𝑗 = 𝑣 𝑗 𝑣 †𝑗 = Π𝑈 ⊗ Π̄ (Λ𝑈 ) ⊥ , 𝑖

𝑖,𝑗

where the second equality is by vec(𝑥𝑦 † ) = 𝑥 ⊗ 𝑦. ¯ The conclusion follows by (7), (8), and (9). Lemma 5.2. Define 𝛼 := Tr(Λ2 Π𝑈 ) and 𝛽 := Tr(Λ2 Π Λ𝑈 ). Then 0 ≤ 𝛼 ≤ 𝛽 ≤ 1. Proof. First, by Tr(Λ2 ) = ∥Λ∥ 2𝐹 = 1 and 0 ⪯ Π𝑈 , ΠΛ𝑈 ⪯ 𝐼 , we have 𝛼, 𝛽 ∈ [0, 1]. Let {𝑣𝑖 ∈ ℂ𝑁 }𝑖 ∈ [𝑟 ] be an orthonormal basis of 𝑈 , and define matrix 𝑉 := [𝑣 1, . . . , 𝑣𝑟 ] ∈ ℂ𝑁 ×𝑟 , and set

𝑋 := 𝑉 † Λ2𝑉 ,

𝑌 := 𝑉 † Λ4𝑉 ∈ ℂ𝑟 ×𝑟 . 24

(9)

𝑗

□

Note that 𝑋 ≻ 0 since Λ ≻ 0 and 𝑉 has full column rank. By observing that Π𝑈 = 𝑉𝑉 † , we have 𝛼 = Tr(Λ2 Π𝑈 ) = Tr(𝑉 † Λ2𝑉 ) = Tr(𝑋 ).

(10)

As the space Λ𝑈 is spanned by columns of 𝑉˜ := Λ𝑉 , its orthogonal projector can be computed as ΠΛ𝑈 = 𝑉˜ (𝑉˜ †𝑉˜ ) −1𝑉˜ † = Λ𝑉 (𝑉 † Λ2𝑉 ) −1𝑉 † Λ = Λ𝑉 𝑋 −1𝑉 † Λ. Then

𝛽 = Tr(Λ2 Π Λ𝑈 ) = Tr(Λ2 Λ𝑉 𝑋 −1𝑉 † Λ) = Tr(𝑉 † Λ4𝑉 𝑋 −1 ) = Tr(𝑌 𝑋 −1 ).

(11)

Combining (10) and (11), we have 𝛽 − 𝛼 = Tr(𝑌 𝑋 −1 ) − Tr(𝑋 ) = Tr((𝑌 − 𝑋 2 )𝑋 −1 ) ≥ 0,

(12)

𝑌 − 𝑋 2 = 𝑉 † Λ4𝑉 − (𝑉 † Λ2𝑉 ) 2 = 𝑉 † Λ2 (𝐼 − 𝑉𝑉 † )Λ2𝑉 = 𝑉 † Λ2 Π𝑈 ⊥ Λ2𝑉 ⪰ 0.

(13)

because 𝑋 −1 ≻ 0, and

□ Combining the above two lemmas, we upper bound the mass of a zero-energy operator. Lemma 5.3. If EΛ (𝑃) = 0, then 𝑚 Λ (𝑃) ≤ 41 . Proof. By Lemma 5.1, we have 𝑃 ⪯ Π L( (Λ𝑈 ) ⊥,𝑈 ) = Π𝑈 ⊗ Π̄ (Λ𝑈 ) ⊥ , which implies 𝑚 Λ (𝑃) = Tr(𝑃 (Λ2 ⊗ Λ̄2 )) ≤ Tr(ΠL( (Λ𝑈 ) ⊥,𝑈 ) (Λ2 ⊗ Λ̄2 )) = 𝑚 Λ (Π L( (Λ𝑈 ) ⊥,𝑈 ) ), and

𝑚 Λ (Π L( (Λ𝑈 ) ⊥,𝑈 ) ) = Tr(Λ2 Π𝑈 ) · Tr(Λ2 Π (Λ𝑈 ) ⊥ ) = 𝛼 (1 − 𝛽),

where 𝛼 := Tr(Λ2 Π𝑈 ) and 𝛽 := Tr(Λ2 Π Λ𝑈 ). By Lemma 5.2, we have 0 ≤ 𝛼 ≤ 𝛽 ≤ 1, and thus 𝑚 Λ (𝑃) ≤ 𝑚 Λ (Π L( (Λ𝑈 ) ⊥,𝑈 ) ) = 𝛼 (1 − 𝛽) ≤ 𝛼 (1 − 𝛼) ≤

1 . 4

(14) □

Now we characterize the structure of zero-energy operators that achieve the maximal mass. Theorem 5.4 (Characterization of operators with zero energy and maximal mass). Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 , and PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1 and Λ ≻ 0, if 𝑚 Λ (𝑃) =

1 4

and

EΛ (𝑃) = 0,

then there exists an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ such that 25

(i) 𝑃 = Π L(𝑈 ⊥,𝑈 ) , i.e., the orthogonal projector onto the space L(𝑈 , 𝑈 ) := span{𝑥𝑦 : 𝑥 ∈ 𝑈 , 𝑦 ∈ 𝑈 } = ⊥

†

⊥

0 𝑋 0 0

:𝑋 ∈ℂ

|𝑈 | × |𝑈 ⊥ |

in the basis of 𝑈 ⊕ 𝑈 ⊥ ; (ii) 𝑈 and 𝑈 ⊥ are Λ-invariant, i.e., Λ𝑈 = 𝑈 , Λ𝑈 ⊥ = 𝑈 ⊥ ; (iii) Tr(Λ2 Π𝑈 ) = Tr(Λ2 Π𝑈 ⊥ ) = 12 , where Π𝑈 (resp. Π𝑈 ⊥ ) is the orthogonal projector onto 𝑈 (resp. 𝑈 ⊥ ). Remark 5.5. Theorem 5.4 can be viewed as the noncommutative generalization of the following classical fact. Given a directed graph 𝐺 = (𝑉 , 𝐸) in which each processor 𝑣 ∈ 𝑉 has a weight 𝑤 𝑣 > 0, suppose that the weights sum to 1. If 𝐺 contains no 2-walks, then there must exist a partition 𝑉 = 𝐿 ⊔ 𝑅, such that 𝐸 only contains edges from 𝐿 to 𝑅. Moreover, the total weight of edges 𝑚 :=

∑︁ (𝑢,𝑣) ∈𝐸

1 𝑤𝑢 𝑤 𝑣 ≤ 𝑊𝐿𝑊𝑅 ≤ , 4

where 𝑊𝐿 :=

∑︁

𝑤𝑣,

𝑣 ∈𝐿

𝑊𝑅 :=

∑︁

𝑤 𝑣 = 1 − 𝑊𝐿 .

𝑣 ∈𝑅

If the maximal 𝑚 = 1/4 is reached, then 𝐺 must be a complete directed cut and 𝑊𝐿 = 𝑊𝑅 = 1/2, which corresponds to Property (i) and (iii). √ Property (ii) has no classical analogue, as the corresponding weight matrix Λ = diag( 𝑤 𝑣 ) is diagonal in the computational basis. Proof of Theorem 5.4. By Lemma 5.3, we have 𝑚 Λ (𝑃) ≤ 1/4. Since 𝑚 Λ (𝑃) = 1/4, all inequalities in (14) must be saturated. In particular, we have 𝑚 Λ (𝑃) = 𝑚 Λ (ΠL( (Λ𝑈 ) ⊥,𝑈 ) ),

𝛽 = 𝛼,

1 and 𝛼 = . 2

We first prove (iii). By 𝛼 = 12 , we have 1 Tr(Λ2 Π𝑈 ) = 𝛼 = , 2

and

Tr(Λ2 Π𝑈 ⊥ ) = Tr(Λ2 ) − Tr(Λ2 Π𝑈 ) = 1 −

1 1 = . 2 2

Next, we prove (ii). Define 𝑋 = 𝑉 † Λ2𝑉 and 𝑌 = 𝑉 † Λ4𝑉 as in the proof of Lemma 5.2. By 𝛼 = 𝛽 and (12), we have 0 = 𝛽 − 𝛼 = Tr((𝑌 − 𝑋 2 )𝑋 −1 ), which implies 𝑌 − 𝑋 2 = 0, as 𝑌 − 𝑋 2 ⪰ 0 by (13) and 𝑋 −1 ≻ 0. Combining with (13), we have † 0 = 𝑌 − 𝑋 2 = 𝑉 † Λ2 Π𝑈 ⊥ Λ2𝑉 = Π𝑈 ⊥ Λ2𝑉 Π𝑈 ⊥ Λ2𝑉 . Thus Π𝑈 ⊥ Λ2𝑉 = 0. As 𝑈 is spanned by columns of 𝑉 , we have Λ2𝑈 ⊆ 𝑈 , i.e., 𝑈 is invariant under Λ2 . Since Λ is Hermitian, any invariant subspace of Λ2 is spanned by eigenvectors of Λ2 . Since Λ and Λ2 share the same eigenvectors, we also have Λ𝑈 ⊆ 𝑈 . Moreover, 26

because Λ is invertible, we have

Λ𝑈 = 𝑈 .

Then for any vector 𝑢 ∈ 𝑈 , 𝑢 ⊥ ∈ 𝑈 ⊥ , we have ⟨𝑢 ⊥, Λ𝑢⟩ = 0 since Λ𝑢 ∈ Λ𝑈 = 𝑈 . Since Λ is Hermitian, we have ⟨Λ𝑢 ⊥, 𝑢⟩ = ⟨𝑢 ⊥, Λ𝑢⟩ = 0. Thus 𝑈 ⊥ is also Λ-invariant, i.e., Λ𝑈 ⊥ = 𝑈 ⊥ . Finally, we prove (i). By Lemma 5.1, we know that 𝑃 ⪯ Π L( (Λ𝑈 ) ⊥,𝑈 ) . We claim that 𝑃 = ΠL( (Λ𝑈 ) ⊥,𝑈 ) . Indeed, if 𝑃 ≠ ΠL( (Λ𝑈 ) ⊥,𝑈 ) , then (Π L( (Λ𝑈 ) ⊥,𝑈 ) − 𝑃) is a nonzero PSD. By Λ2 ⊗ Λ̄2 ≻ 0, we would have 𝑚 Λ (Π L( (Λ𝑈 ) ⊥,𝑈 ) ) − 𝑚 Λ (𝑃) = Tr (Π L( (Λ𝑈 ) ⊥,𝑈 ) − 𝑃) (Λ2 ⊗ Λ̄2 ) > 0, contradicting the fact that 𝑚 Λ (𝑃) = 𝑚 Λ (Π L( (Λ𝑈 ) ⊥,𝑈 ) ). Furthermore, by Λ𝑈 = 𝑈 from (ii), we have 𝑃 = Π L( (Λ𝑈 ) ⊥,𝑈 ) = ΠL(𝑈 ⊥,𝑈 ) . This proves all three claimed properties.

5.2

□

Approximation of Zero-Energy Operators

In this section, we show that if an operator of maximal mass has small energy, then it can be approximated by an operator with exactly zero energy, as stated in Theorem 5.6. We remark that this theorem does not require Λ to be strictly positive. Theorem 5.6. Assume 𝑁 ≥ 2. Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 , and PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, if 1 EΛ (𝑃) = 𝜖 ≥ 0, and 𝑚 Λ (𝑃) = . 4 ′ ′ ′ ′ then there exists PSD 𝑃 with 0 ⪯ 𝑃 ⪯ 𝐼 and PSD Λ with ∥Λ ∥ 𝐹 = 1 such that EΛ′ (𝑃 ′ ) = 0, 5.2.1

1 𝑚 Λ′ (𝑃 ′ ) = , 4

∥Λ − Λ′ ∥ 2𝐹 = 𝑂 (𝜖 1/4 ),

and

∥𝑃 − 𝑃 ′ ∥ Λ = 𝑂 (𝜖 1/4 ).

Candidate Construction

Notice that Theorem 5.6 is trivial if EΛ (𝑃) = 0. In the following, we assume EΛ (𝑃) = 𝜖 > 0. We construct 𝑃 ′ and Λ′ as follows. First recall that ⊤ EΛ (𝑃) = Tr(Λ𝐴Λ𝐵), where 𝐴 := Tr A (Λ2 ⊗ 𝐼 )𝑃 , 𝐵 := Tr B (𝐼 ⊗ Λ̄2 )𝑃 . As 0 ⪯ 𝐵 = Tr B ((𝐼 ⊗ Λ̄)𝑃 (𝐼 ⊗ Λ̄)) ⪯ Tr B (𝐼 ⊗ Λ̄2 ) = 𝐼 , we can write its spectral decomposition as ∑︁ 𝐵= 𝜌𝑖 𝑣𝑖 𝑣𝑖† 𝑖

where {𝑣𝑖 } are orthonormal eigenvectors, and 1 ≥ 𝜌 1 ≥ 𝜌 2 ≥ · · · ≥ 𝜌 𝑁 ≥ 0 are eigenvalues of 𝐵 in non-increasing order. Define a threshold index √ 𝑡 := max{𝑖 ∈ [𝑁 ] : 𝜌𝑖 ≥ 𝜖}. Then set up the orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ ,

where 𝑈 = span{𝑣𝑖 : 𝑖 ≤ 𝑡 },

𝑈 ⊥ = span{𝑣𝑖 : 𝑖 > 𝑡 }.

Then the candidate construction is 𝑃 ′ := ΠL(𝑈 ⊥,𝑈 ) ,

Λ′ := √︁

𝑋 2Tr(𝑋 2 )

+ √︁

𝑌 2Tr(𝑌 2 )

where 𝑋 := Π𝑈 ΛΠ𝑈 and 𝑌 := Π𝑈 ⊥ ΛΠ𝑈 ⊥ . We claim that for small enough 𝜖, the above construction is well-defined, i.e., 𝑡 exists and 𝑋, 𝑌 are both nonzero; see Proof of Theorem 5.6 for details. Then it is immediate that 𝑃 ′ is an orthogonal projector, and Λ′ is PSD with ∥Λ′ ∥ 𝐹 = 1. We can also verify that the pair (𝑃 ′, Λ′ ) achieves the maximal mass and zero energy, stated as follows. Fact 5.7. 𝑚 Λ′ (𝑃 ′ ) = 41 and EΛ′ (𝑃 ′ ) = 0. Proof. As Λ′ is block diagonal with respect to 𝑈 ⊕ 𝑈 ⊥ , spaces 𝑈 , 𝑈 ⊥ are invariant under Λ′ , and thus Tr(Λ′2 Π𝑈 ) =

Tr(𝑋 2 ) 1 +0= , 2 2 2 Tr(𝑋 )

1 Tr(Λ′2 Π𝑈 ⊥ ) = 1 − Tr(Λ′2 Π𝑈 ) = . 2

Then by the fact that 𝑃 ′ = ΠL(𝑈 ⊥,𝑈 ) = Π𝑈 ⊗ Π̄𝑈 ⊥ , we have 1 𝑚 Λ′ (𝑃 ′ ) = Tr 𝑃 ′ (Λ′2 ⊗ Λ̄′2 ) = Tr(Π𝑈 Λ′2 )Tr(Π𝑈 ⊥ Λ′2 ) = . 4 Note that the spectral decomposition of 𝑃 ′ is ∑︁ 𝑃′ = vec(𝑀𝑘 )vec(𝑀𝑘 ) †, where

{𝑀𝑘 } := {𝑣𝑖 𝑣 †𝑗 : 𝑖 ≤ 𝑡, 𝑗 > 𝑡 }.

𝑘

For any two 𝑀𝑘 = 𝑣𝑖 𝑣 †𝑗 , 𝑀ℓ = 𝑣 𝑝 𝑣𝑞† , we have 𝑣 𝑗 ∈ 𝑈 ⊥ and 𝑣 𝑝 ∈ 𝑈 . As 𝑈 is invariant under Λ′ , we have Λ′𝑣 𝑝 ∈ 𝑈 , and thus 𝑣 †𝑗 Λ′𝑣 𝑝 = 0. Therefore, we have Λ′ 𝑀𝑘 Λ′ 𝑀ℓ Λ′ = Λ′𝑣𝑖 (𝑣 †𝑗 Λ′𝑣 𝑝 )𝑣𝑞† Λ′ = 0. By Lemma 4.2, we have EΛ′ (𝑃 ′ ) =

′ ′ ′ 2 𝑘,ℓ ∥Λ 𝑀𝑘 Λ 𝑀ℓ Λ ∥ 𝐹 = 0.

□

Therefore, to conclude Theorem 5.6 using (Λ′, 𝑃 ′ ), it remains to show that (Λ′, 𝑃 ′ ) is a good approximation of (Λ, 𝑃).

5.2.2

Approximate Λ-Invariance of 𝑈

We first prove that the subspace 𝑈 is approximately invariant under Λ, when EΛ (𝑃) = 𝜖 is small. Formally, Lemma 5.8. Let 𝑄 := Π𝑈 and 𝑅 := Π𝑈 ⊥ . Define the non-invariance measure of 𝑈 under Λ as 𝛿 := ∥𝑄Λ𝑅∥ 2𝐹 . √ Then we have 𝛿 = 𝑂 ( 𝜖). √ Note that 𝛿 = 0 if and only if 𝑈 is invariant under Λ, e.g., when Λ = 𝐼 / 𝑁 . To prove the lemma, the key observation is to relate 𝛿 to the testing error of the pretty-good measurement (PGM, see Definition 3.5) for two subnormalized states 𝜎0 = Λ𝑅Λ and 𝜎1 = Λ𝑄Λ. Then we construct a measurement that distinguishes 𝜎0 and 𝜎1 with small error, which implies that the optimal testing error is small, and thus the PGM testing error is also small. Proof of Lemma 5.8. Consider two states 𝜎0 := Λ𝑅Λ,

𝜎1 := Λ𝑄Λ,

and define 𝜎 = 𝜎0 + 𝜎1 = Λ2 . By Definition 3.5, the PGM for 𝜎0, 𝜎1 is 1 𝑀0 := Λ+𝜎0 Λ+ + Πker(𝜎 ) , 2

1 𝑀1 := Λ+𝜎1 Λ+ + Π ker(𝜎 ) . 2

The testing error of 𝑀0 is Tr(𝑀0𝜎1 ) = Tr(Λ+𝜎0 Λ+𝜎1 ) +

1 Tr(Π ker(𝜎 ) 𝜎1 ) = Tr(Λ+ Λ𝑅ΛΛ+ Λ𝑄Λ) + 0 = Tr(𝑅Λ𝑄Λ) = 𝛿, 2

where the first equality is by the definition of 𝑀0 , the second equality follows from 𝜎1 ⪯ 𝜎 and thus ker(𝜎) ⊆ ker(𝜎1 ), the third equality is by Λ+ ΛΛ = Λ, and the last equality is by 𝛿 = ∥𝑄Λ𝑅∥ 2𝐹 = Tr(𝑅Λ𝑄𝑄Λ𝑅) = Tr(𝑅Λ𝑄Λ). Similarly, the testing error of 𝑀1 is also Tr(𝑀1𝜎0 ) = 𝛿. Thus the testing error of PGM is PGM(𝜎0, 𝜎1 ) := Tr(𝑀0𝜎1 ) + Tr(𝑀1𝜎0 ) = 2𝛿. Now we construct a 2-outcome POVM {𝑉 , 𝐼 − 𝑉 } that distinguishes 𝜎0 and 𝜎1 . We write the spectral decomposition of 𝑃 as ∑︁ 𝑃= vec(𝑀𝑘 )vec(𝑀𝑘 ) †, 𝑘

and define a completely positive map and its adjoint map ∑︁ ∑︁ 𝑀𝑘 𝑋 𝑀𝑘†, Φ∗ (𝑋 ) := 𝑀𝑘†𝑋 𝑀𝑘 . Φ(𝑋 ) := 𝑘

𝑘

If Tr(𝑄Λ2 ) = 0, we have 0 ≤ 𝛿 = Tr(𝑅Λ𝑄Λ) ≤ Tr(𝑄Λ2 ) = 0, and thus 𝛿 = 0 = 𝑂 (𝜖 1/2 ). Assume

Tr(𝑄Λ2 ) > 0. Define a quantum state 𝜎 :=

𝑄Λ2𝑄 , Tr(𝑄Λ2 )

and feed 𝜎 through Φ∗ to get 𝑉 := Φ∗ (𝜎) =

∑︁ 1 𝑀 †𝑄Λ2𝑄𝑀𝑘 . Tr(𝑄Λ2 ) 𝑘 𝑘

This indeed defines a valid POVM operator. For every unit vector 𝑥 ∈ ℂ𝑁 , Lemma 5.10 gives 0 ≤ ⟨𝑥, 𝑉 𝑥⟩ =

Tr(𝑄Λ2𝑄) Tr(𝑥𝑥 † ) 1 2 † ≤ Tr 𝑃 𝑄Λ 𝑄 ⊗ 𝑥𝑥 = ∥𝑥 ∥ 2 = 1. Tr(𝑄Λ2 ) Tr(𝑄Λ2 )

Thus 0 ⪯ 𝑉 ⪯ 𝐼 , so {𝑉 , 𝐼 − 𝑉 } is a two-outcome POVM. By Lemma 5.9, the optimal testing error OPT(𝜎0, 𝜎1 ) ≤ Tr(𝑉 Λ𝑄Λ) + Tr((𝐼 − 𝑉 )Λ𝑅Λ) = 𝑂 (𝜖 1/2 ). By Lemma 3.6, we have

PGM(𝜎0, 𝜎1 ) ≤ 2OPT(𝜎0, 𝜎1 ) = 𝑂 (𝜖 1/2 ),

which implies 𝛿 = 21 PGM(𝜎0, 𝜎1 ) = 𝑂 (𝜖 1/2 ).

□

Lemma 5.9. Let {𝑉 , 𝐼 − 𝑉 } be the POVM defined above. Then Tr(𝑉 Λ𝑄Λ) + Tr((𝐼 − 𝑉 )Λ𝑅Λ) = 𝑂 (𝜖 1/2 ). Proof. Combine Lemma 5.12 and Lemma 5.13.

□

We first prove two helper lemmas. For convenience, we define 𝛼 := Tr(𝑄Λ2 ). The following helper lemma characterizes the action 𝑉 . Lemma 5.10. For any PSD 𝑌 , we have Tr(𝑉 𝑌 ) =

1 Tr(𝑃 (𝑄Λ2𝑄 ⊗ 𝑌¯ )). 𝛼

Proof. By the definition of 𝑉 , Tr(𝑉 𝑌 ) =

1 ∑︁ Tr(𝑌 𝑀𝑘†𝑄Λ2𝑄𝑀𝑘 ). 𝛼 𝑘

Compute ⊤ 𝑀𝑘†𝑄Λ2𝑄𝑀𝑘 = (Λ𝑄𝑀𝑘 ) † (Λ𝑄𝑀𝑘 ) = Tr A vec(Λ𝑄𝑀𝑘 )vec(Λ𝑄𝑀𝑘 ) † ⊤ = Tr A vec(𝑀𝑘 )vec(𝑀𝑘 ) † (𝑄Λ2𝑄 ⊗ 𝐼 ) .

Combining the two equations gives ∑︁ 1 Tr(𝑉 𝑌 ) = Tr 𝑌 · Tr A (vec(𝑀𝑘 )vec(𝑀𝑘 ) † (𝑄Λ2𝑄 ⊗ 𝐼 )) ⊤ 𝛼

𝑘

1 = Tr(𝑌 · Tr A (𝑃 (𝑄Λ2𝑄 ⊗ 𝐼 )) ⊤ ) 𝛼 1 1 = Tr(Tr A (𝑃 (𝑄Λ2𝑄 ⊗ 𝑌¯ ))) = Tr(𝑃 (𝑄Λ2𝑄 ⊗ 𝑌¯ )). 𝛼 𝛼 □ The next lemma bounds the normalization factor 𝛼. Lemma 5.11. We have 𝛼 ≥ Tr(𝐵𝑄Λ2𝑄) ≥

1 √ − 𝜖. 4

If 𝜖 ≤ 1/64, we have 𝛼 ≥ 1/8. Proof. By construction, we know that 1 Tr(𝐵Λ2 ) = Tr(Λ2 𝐵) = Tr(Λ2 Tr B ((𝐼 ⊗ Λ̄2 )𝑃)) = Tr((Λ2 ⊗ Λ̄2 )𝑃) = 𝑚 Λ (𝑃) = . 4 Since 𝐵 is block diagonal under 𝑄 ⊕ 𝑅, we have Tr(𝐵Λ2 ) = Tr(𝑄𝐵𝑄Λ2 ) + Tr(𝑅𝐵𝑅Λ2 ) = Tr(𝐵𝑄Λ2𝑄) + Tr(𝐵𝑅Λ2𝑅). By 𝐵 ⪯ 𝐼 , we have

Tr(𝐵𝑄Λ2𝑄) ≤ Tr(𝑄Λ2𝑄) = Tr(𝑄Λ2 ) = 𝛼 . √ √ For the second term, as 𝜌𝑖 ≤ 𝜖 for any 𝑖 > 𝑡, we have 𝑅𝐵𝑅 ⪯ 𝜖𝐼 . Thus √ √ Tr(𝐵𝑅Λ2𝑅) = Tr(𝑅𝐵𝑅Λ2 ) ≤ 𝜖Tr(Λ2 ) = 𝜖. Putting things together, √ 1 ≤ Tr(𝐵𝑄Λ2𝑄) + Tr(𝐵𝑅Λ2𝑅) ≤ 𝛼 + 𝜖 4

⇒

𝛼 ≥ Tr(𝐵𝑄Λ2𝑄) ≥

1 √ − 𝜖. 4

For 𝜖 ≤ 1/64, we have 𝛼 ≥ 1/4 − 1/8 = 1/8.

□

Then we bound the two error terms of the POVM {𝑉 , 𝐼 − 𝑉 }. The first lemma shows that 𝑉 accepts 𝜎1 = Λ𝑄Λ with low probability. Lemma 5.12. Tr(𝑉 Λ𝑄Λ) = 𝑂 (𝜖 1/2 ). Proof. If 𝜖 > 1/64 = Ω(1), then the bound is trivial since Tr(𝑉 Λ𝑄Λ) is a probability and thus at most 1. Now assume 𝜖 ≤ 1/64. By Lemma 5.10 and Lemma 5.11, we have Tr(𝑉 Λ𝑄Λ) =

1 Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑄Λ)) ≤ 8 · Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑄Λ)). 𝛼 31

Using 𝑄 + 𝑅 = 𝐼 and inequality (𝑄 + 2𝑅)Λ2 (𝑄 + 2𝑅) ⪰ 0 2Λ2 + 2𝑅Λ2𝑅 − 𝑄Λ2𝑄 ⪰ 0 𝑄Λ2𝑄 ⪯ 2Λ2 + 2𝑅Λ2𝑅, we have

Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑄Λ)) ≤ 2 · Tr(𝑃 (Λ2 ⊗ Λ𝑄Λ)) + 2 · Tr(𝑃 (𝑅Λ2𝑅 ⊗ Λ𝑄Λ)). √ For the first term, using 𝜖𝑄 ⪯ 𝐵, 1 EΛ (𝑃) √ Tr(𝑃 (Λ2 ⊗ Λ𝑄Λ)) = Tr(𝐴⊤ Λ𝑄Λ) = Tr(𝐴Λ𝑄Λ) ≤ √ Tr(𝐴Λ𝐵Λ) = √ = 𝜖. 𝜖 𝜖 √ For the second term, using Λ𝑄Λ ⪯ Λ̄2 and 𝑅𝐵𝑅 ⪯ 𝜖𝐼 , √ √ Tr(𝑃 (𝑅Λ2𝑅 ⊗ Λ𝑄Λ)) ≤ Tr(𝑃 (𝑅Λ2𝑅 ⊗ Λ̄2 )) = Tr[Tr B (𝑃 (𝐼 ⊗ Λ̄2 ))𝑅Λ2𝑅] = Tr(𝐵𝑅Λ2𝑅) ≤ 𝜖Tr(Λ2 ) = 𝜖. Putting things together, we have √ √ √ Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑄Λ)) ≤ 2 𝜖 + 2 𝜖 = 4 𝜖. √ Thus Tr(𝑉 Λ𝑄Λ) ≤ 32 𝜖 = 𝑂 (𝜖 1/2 ).

(15) □

The next lemma shows that 𝐼 − 𝑉 accepts 𝜎0 = Λ𝑅Λ with low probability. Lemma 5.13. Tr((𝐼 − 𝑉 )Λ𝑅Λ) = 𝑂 (𝜖 1/2 ). Proof. If 𝜖 > 1/64 = Ω(1), then the bound is trivial since Tr((𝐼 − 𝑉 )Λ𝑅Λ) is a probability and thus at most 1. Now assume 𝜖 ≤ 1/64. By Lemma 5.10 and Lemma 5.11, we have Tr((𝐼 − 𝑉 )Λ𝑅Λ) = Tr(Λ𝑅Λ) − Tr(𝑉 Λ𝑅Λ) = (1 − 𝛼) −

1 Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑅Λ)) 𝛼

By Λ𝑅Λ = Λ̄2 − Λ𝑄Λ, we have Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑅Λ)) = Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ̄2 )) − Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑄Λ)). The first term Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ̄2 )) = Tr(𝐵𝑄Λ2𝑄) ≥

1 √ − 𝜖, 4

where the last inequality uses Lemma 5.11. By (15), the second term √ Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑄Λ)) ≤ 4 𝜖. Thus Tr(𝑃 (𝑄Λ2𝑄 ⊗ Λ𝑅Λ)) ≥

√ 1 − 5 𝜖. 4

Plugging back gives √ √ √ 1 1 5 𝜖 Tr((𝐼 − 𝑉 )Λ𝑅Λ) ≤ 𝛼 (1 − 𝛼) − + 5 𝜖 ≤ ≤ 40 𝜖, 𝛼 4 𝛼 where the last inequality uses Lemma 5.11. 5.2.3

□

Proof of Theorem 5.6

We first introduce the weighted operator 𝑃˜ := (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄). Note that

˜ = Tr((Λ2 ⊗ Λ̄2 )𝑃) = 𝑚 Λ (𝑃) = 1 , Tr(𝑃) 4

and its partial traces are ˜ = Λ̄ Tr A ((Λ ⊗ 𝐼 )𝑃 (Λ ⊗ 𝐼 )) Λ̄ = (Λ𝐴Λ) ⊤, Tr A (𝑃)

˜ = Λ𝐵Λ. Tr B (𝑃)

and similarly,

We then prove two helper lemmas. √ Lemma 5.14. Tr(𝑃˜ (𝐼 − 𝑃 ′ )) = 𝑂 ( 𝜖). Proof. For 𝑖, 𝑗 ∈ [𝑁 ], we define the variable 𝑦𝑖 𝑗 := (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) † 𝑃˜ (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) ∈ [0, 1]. Compute its 𝑗-th column sum 𝑐 𝑗 :=

∑︁

𝑦𝑖 𝑗 =

∑︁

𝑖

˜ 𝑣¯ 𝑗 = 𝑣 † Λ𝐴Λ𝑣 𝑗 = 𝑣 † Λ𝐴Λ𝑣 𝑗 , (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) † 𝑃˜ (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) = 𝑣¯†𝑗 Tr A (𝑃) 𝑗 𝑗

𝑖

Then we can express energy as ! EΛ (𝑃) = Tr Λ𝐴Λ

∑︁

𝜌 𝑗 𝑣 𝑗 𝑣 †𝑗

∑︁

𝑗

∑︁ 𝜌 𝑗 Tr Λ𝐴Λ𝑣 𝑗 𝑣 †𝑗 = 𝜌 𝑗𝑐 𝑗 .

𝑗

Similarly, define the 𝑖-th row sum ∑︁ ∑︁ ˜ 𝑖 = 𝑣 † Λ𝐵Λ𝑣𝑖 . 𝑦𝑖 𝑗 = (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) † 𝑃˜ (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) = 𝑣𝑖† Tr B (𝑃)𝑣 𝑟𝑖 := 𝑖 𝑗

By 𝑃 ′ = ΠL(𝑈 ⊥,𝑈 ) =

† 𝑖 ≤𝑡,𝑗 >𝑡 (𝑣 𝑖 ⊗ 𝑣¯ 𝑗 ) (𝑣 𝑖 ⊗ 𝑣¯ 𝑗 ) , we have

Tr(𝑃˜ (𝐼 − 𝑃 )) = Tr 𝑃˜ 𝐼 − ′

𝑗

!! ∑︁

(𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) (𝑣𝑖 ⊗ 𝑣¯ 𝑗 )

†

∑︁ 𝑖>𝑡 or 𝑗 ≤𝑡

𝑖 ≤𝑡,𝑗 >𝑡

(𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) † 𝑃˜ (𝑣𝑖 ⊗ 𝑣¯ 𝑗 ) =

∑︁ 𝑖>𝑡 or 𝑗 ≤𝑡

𝑦𝑖 𝑗 .

Then observe that

∑︁

𝑦𝑖 𝑗 ≤

𝑖>𝑡 or 𝑗 ≤𝑡

∑︁ 𝑗 ≤𝑡

𝑐𝑗 +

∑︁

𝑟𝑖 .

𝑖>𝑡

√ For the first sum, as 𝜌 𝑗 ≥ 𝜖 for all 𝑗 ≤ 𝑡, we have ∑︁ ∑︁ √ ∑︁ 𝑐𝑗. EΛ (𝑃) = 𝜌 𝑗𝑐 𝑗 ≥ 𝜌 𝑗𝑐 𝑗 ≥ 𝜖 𝑗 ≤𝑡

𝑗

Thus ∑︁

𝑐𝑗 ≤

𝑗 ≤𝑡

For the second sum,

∑︁

𝑟𝑖 =

𝑖>𝑡

∑︁

𝑗 ≤𝑡

EΛ (𝑃) √ = 𝜖. √ 𝜖

(16)

𝑣𝑖† Λ𝐵Λ𝑣𝑖 = Tr (Π𝑈 ⊥ Λ𝐵ΛΠ𝑈 ⊥ ) .

𝑖>𝑡

√ √ As 𝐵 ⪯ 𝐼 and 𝜌 𝑗 ≤ 𝜖 for all 𝑗 > 𝑡, we have 𝐵 ⪯ Π𝑈 + 𝜖Π𝑈 ⊥ . Then √ Tr (Π𝑈 ⊥ Λ𝐵ΛΠ𝑈 ⊥ ) ≤ Tr (Π𝑈 ⊥ ΛΠ𝑈 ΛΠ𝑈 ⊥ ) + 𝜖 Tr (Π𝑈 ⊥ ΛΠ𝑈 ⊥ ΛΠ𝑈 ⊥ ) √ = 𝛿 + 𝜖 Tr (Π𝑈 ⊥ ΛΠ𝑈 ⊥ ΛΠ𝑈 ⊥ ) √ √ ≤ 𝛿 + 𝜖Tr(Λ2 ) ≤ 𝛿 + 𝜖.

(17)

Combining (16) and (17), we get ∑︁ ∑︁ ∑︁ √ √ 𝑦𝑖 𝑗 ≤ 𝑐𝑗 + 𝑟𝑖 ≤ 2 𝜖 + 𝛿 = 𝑂 ( 𝜖), 𝑖>𝑡 or 𝑗 ≤𝑡

𝑗 ≤𝑡

𝑖>𝑡

where the last inequality is by Lemma 5.8.

□

Lemma 5.15. Define 𝜂 := Tr(Λ2 Π𝑈 ). Then 𝜂−

1 = 𝑂 (𝜖 1/4 ). 2

˜ ′ ) ≤ Tr(𝑃) ˜ = 1/4, we have Proof. By Lemma 5.14 and Tr(𝑃𝑃 √ 1 ˜ ′) ≤ 1 . − 𝑂 ( 𝜖) ≤ Tr(𝑃𝑃 4 4 Then compute ˜ ′ ) = Tr((Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄)𝑃 ′ ) Tr(𝑃𝑃 ≤ Tr((Λ2 ⊗ Λ̄2 )𝑃 ′ ) = Tr((Λ2 ⊗ Λ̄2 ) (Π𝑈 ⊗ Π̄𝑈 ⊥ )) = Tr(Λ2 Π𝑈 )Tr(Λ2 Π𝑈 ⊥ ) = 𝜂 (1 − 𝜂).

Plugging back, we have 2 √ 1 1 1 − 𝑂 ( 𝜖) ≤ 𝜂 (1 − 𝜂) = − 𝜂 − 4 4 2

=⇒

𝜂−

1 = 𝑂 (𝜖 1/4 ). 2 □

Next, we bound the closeness of Λ and Λ′ . Lemma 5.16. ∥Λ − Λ′ ∥ 2𝐹 = 𝑂 (𝜖 1/4 ). Proof. Define 𝑄 := Π𝑈 and 𝑅 := Π𝑈 ⊥ . Then Λ = 𝑄Λ𝑄 + 𝑅Λ𝑅 + 𝑄Λ𝑅 + 𝑅Λ𝑄 = 𝑋 + 𝑌 + 𝑄Λ𝑅 + 𝑅Λ𝑄. First compute the Frobenius masses of 𝑋 and 𝑌 . Since 𝑄Λ2𝑄 = 𝑄Λ(𝑄 + 𝑅)Λ𝑄 = 𝑄Λ𝑄Λ𝑄 + 𝑄Λ𝑅Λ𝑄, we have

𝜂 := Tr(Λ2𝑄) = Tr(𝑄Λ2𝑄) = Tr(𝑋 2 ) + Tr(𝑄Λ𝑅Λ𝑄).

By Tr(𝑄Λ𝑅Λ𝑄) = ∥𝑄Λ𝑅∥ 2𝐹 = 𝛿, we have Tr(𝑋 2 ) = 𝜂 − 𝛿. Similarly, Tr(𝑌 2 ) = 1 − 𝜂 − 𝛿. Let 𝑥 := Tr(𝑋 2 ) = 𝜂 − 𝛿,

𝑦 := Tr(𝑌 2 ) = 1 − 𝜂 − 𝛿.

Note that {𝑄Λ𝑄, 𝑅Λ𝑅, 𝑄Λ𝑅, 𝑅Λ𝑄 } are pairwise orthogonal in Frobenius inner product. Thus ! 2 1 1 ′ 2 ∥Λ − Λ ∥ 𝐹 = 1 − √ 𝑋 + 1 − √︁ 𝑌 + 𝑄Λ𝑅 + 𝑅Λ𝑄 2𝑥 2𝑦 𝐹 !2 2 1 1 = 1− √ ∥𝑋 ∥ 2𝐹 + 1 − √︁ ∥𝑌 ∥ 2𝐹 + ∥𝑄Λ𝑅∥ 2𝐹 + ∥𝑅Λ𝑄 ∥ 2𝐹 2𝑥 2𝑦 2 2 √ 1 1 √ = 𝑥−√ + 𝑦−√ + 2𝛿. 2 2

√ √ Using ( 𝑎 − 𝑏) 2 ≤ |𝑎 − 𝑏 | for any 𝑎, 𝑏 ≥ 0, we get 1 1 + 𝑦 − + 2𝛿 2 2 1 1 = 𝜂 − 𝛿 − + 1 − 𝜂 − 𝛿 − + 2𝛿 2 2 1 1 1 = 𝜂− −𝛿 + 𝜂 − + 𝛿 + 2𝛿 ≤ 2 𝜂 − + 4𝛿. 2 2 2

∥Λ − Λ′ ∥ 2𝐹 ≤ 𝑥 −

By Lemma 5.15 and Lemma 5.8, we have √ ∥Λ − Λ′ ∥ 2𝐹 ≤ 2𝑂 (𝜖 1/4 ) + 4𝑂 ( 𝜖) = 𝑂 (𝜖 1/4 ), 35

which completes the proof.

□

Finally, we bound the closeness of 𝑃 and 𝑃 ′ . Lemma 5.17. ∥𝑃 − 𝑃 ′ ∥ Λ ≤ 𝑂 (𝜖 1/4 ). Proof. Define 𝑃˜ := (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄), Then

𝑃˜ ′ := (Λ ⊗ Λ̄)𝑃 ′ (Λ ⊗ Λ̄),

𝑇 := 𝑃 ′ (Λ2 ⊗ Λ̄2 )𝑃 ′ .

∥𝑃 − 𝑃 ′ ∥ Λ = ∥ 𝑃˜ − 𝑃˜ ′ ∥ 1 ≤ ∥ 𝑃˜ − 𝑇 ∥ 1 + ∥𝑇 − 𝑃˜ ′ ∥ 1 .

Bound ∥ 𝑃˜ − 𝑇 ∥ 1 .

Decompose space ℂ𝑁 ⊗ ℂ𝑁 into Π1 := 𝑃 ′ and Π2 := (𝐼 − 𝑃 ′ ). Then we can write 𝑃 𝑃 𝑃˜ = 11 12 , where 𝑃𝑖 𝑗 := Π𝑖 𝑃˜ Π 𝑗 . 𝑃21 𝑃 22

Then

∥ 𝑃˜ − 𝑇 ∥ 1 ≤ ∥𝑃11 − 𝑇 ∥ 1 + ∥𝑃 22 ∥ 1 + ∥𝑃 12 ∥ 1 + ∥𝑃 21 ∥ 1 .

We bound each term in the following. Since 𝑃˜ = (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄) ⪯ Λ2 ⊗ Λ̄2 , we have ˜ ′ ⪯ 𝑃 ′ (Λ2 ⊗ Λ̄2 )𝑃 ′ = 𝑇 0 ⪯ 𝑃11 = 𝑃 ′ 𝑃𝑃 Thus the first term

=⇒

𝑇 − 𝑃11 ⪰ 0.

∥𝑃11 − 𝑇 ∥ 1 = Tr(𝑇 − 𝑃 11 ) = Tr(𝑇 ) − Tr(𝑃11 ).

By 𝑃 ′ = ΠL(𝑈 ⊥,𝑈 ) = Π𝑈 ⊗ Π̄𝑈 ⊥ , we have 1 Tr(𝑇 ) = Tr(𝑃 ′ (Λ2 ⊗ Λ̄2 )) = Tr(Π𝑈 Λ2 )Tr(Π𝑈 ⊥ Λ2 ) = 𝜂 (1 − 𝜂) ≤ , 4 and

√ ˜ ′ ) = Tr(𝑃𝑃 ˜ ′ ) ≥ 1 − 𝑂 ( 𝜖), Tr(𝑃11 ) = Tr(𝑃 ′ 𝑃𝑃 4 where the last inequality is from Lemma 5.14. Thus √ √ 1 1 ∥𝑃 11 − 𝑇 ∥ 1 ≤ − − 𝑂 ( 𝜖) = 𝑂 ( 𝜖). 4 4 For the second term, as 𝑃 22 ⪰ 0, √ ˜ = 𝑂 ( 𝜖), ∥𝑃22 ∥ 1 = Tr(𝑃22 ) = Tr((𝐼 − 𝑃 ′ ) 𝑃)

where the last inequality is from Lemma 5.14. √︁ For the third term, 𝑃˜ ⪰ 0 implies that ∥𝑃 12 ∥ 1 ≤ Tr(𝑃11 )Tr(𝑃22 ). By Tr(𝑃 11 ) ≤ 41 and Tr(𝑃22 ) = √ † 𝑂 ( 𝜖), we have ∥𝑃12 ∥ 1 = 𝑂 (𝜖 1/4 ). Finally, since 𝑃 21 = 𝑃12 , the fourth term ∥𝑃21 ∥ 1 = ∥𝑃12 ∥ 1 = 𝑂 (𝜖 1/4 ). Putting things together, we have √ ∥ 𝑃˜ − 𝑇 ∥ 1 ≤ 2𝑂 ( 𝜖) + 2𝑂 (𝜖 1/4 ) = 𝑂 (𝜖 1/4 ). (18) 36

Bound ∥𝑇 − 𝑃˜ ′ ∥ 1 .

By Lemma 5.18, we have √ ∥𝑇 − 𝑃˜ ′ ∥ 1 ≤ 8 𝛿.

(19)

Combining (18), (19), and Lemma 5.8, we have √ ∥𝑃 − 𝑃 ′ ∥ Λ = ∥ 𝑃˜ − 𝑃˜ ′ ∥ 1 ≤ 𝑂 (𝜖 1/4 ) + 8 𝛿 = 𝑂 (𝜖 1/4 ). □ √ Lemma 5.18. ∥𝑇 − 𝑃˜ ′ ∥ 1 ≤ 8 𝛿. ¯ we have Proof. Let 𝑄 := Π𝑈 and 𝑅 := Π𝑈 ⊥ . By 𝑃 ′ = ΠL(𝑈 ⊥,𝑈 ) = 𝑄 ⊗ 𝑅. 𝑃˜ ′ = (Λ ⊗ Λ̄)𝑃 ′ (Λ ⊗ Λ̄) = (Λ𝑄Λ) ⊗ Λ𝑅Λ.

𝑇 = 𝑃 ′ (Λ2 ⊗ Λ̄2 )𝑃 ′ = (𝑄Λ2𝑄) ⊗ 𝑅Λ2𝑅, Compute

𝑇 − 𝑃˜ ′ = 𝑄Λ2𝑄 − Λ𝑄Λ ⊗ 𝑅Λ2𝑅 + (Λ𝑄Λ) ⊗ (𝑅Λ2𝑅 − Λ𝑅Λ). By triangle inequality and ∥𝑋 ⊗ 𝑌 ∥ 1 = ∥𝑋 ∥ 1 ∥𝑌 ∥ 1 , we have ∥𝑇 − 𝑃˜ ′ ∥ 1 ≤ ∥𝑄Λ2𝑄 − Λ𝑄Λ∥ 1 ∥𝑅Λ2𝑅∥ 1 + ∥Λ𝑄Λ∥ 1 ∥𝑅Λ2𝑅 − Λ𝑅Λ∥ 1 .

(20)

First, notice that ∥𝑅Λ2𝑅∥ 1 = Tr(𝑅Λ2𝑅) ≤ Tr(Λ2 ) = 1,

∥Λ𝑄Λ∥ 1 = Tr(Λ𝑄Λ) ≤ Tr(Λ2 ) = 1.

(21)

Next, we bound ∥𝑄Λ2𝑄 − Λ𝑄Λ∥ 1 . Write Λ𝑄Λ = (𝑄 + 𝑅)Λ𝑄Λ(𝑄 + 𝑅) = 𝑄Λ𝑄Λ𝑄 + 𝑅Λ𝑄Λ𝑅 + 𝑄Λ𝑄Λ𝑅 + 𝑅Λ𝑄Λ𝑄, 𝑄Λ2𝑄 = 𝑄Λ(𝑄 + 𝑅)Λ𝑄 = 𝑄Λ𝑄Λ𝑄 + 𝑄Λ𝑅Λ𝑄. Subtracting them gives Λ𝑄Λ − 𝑄Λ2𝑄 = 𝑅Λ𝑄Λ𝑅 + 𝑄Λ𝑄Λ𝑅 + 𝑅Λ𝑄Λ𝑄 − 𝑄Λ𝑅Λ𝑄. Then by Hölder’s inequality ∥𝑋𝑌 ∥ 1 ≤ ∥𝑋 ∥ 𝐹 ∥𝑌 ∥ 𝐹 , definition 𝛿 = ∥𝑄Λ𝑅∥ 2𝐹 = ∥𝑅Λ𝑄 ∥ 2𝐹 , and the fact that ∥𝑄Λ𝑄 ∥ 𝐹 , ∥𝑅Λ𝑅∥ 𝐹 ≤ ∥Λ∥ 𝐹 = 1, we have √ ∥𝑅Λ𝑄Λ𝑅∥ 1 ≤ ∥𝑅Λ𝑄 ∥ 𝐹 ∥𝑄Λ𝑅∥ 𝐹 = 𝛿, ∥𝑄Λ𝑄Λ𝑅∥ 1 ≤ ∥𝑄Λ𝑄 ∥ 𝐹 ∥𝑄Λ𝑅∥ 𝐹 ≤ 𝛿, √ ∥𝑄Λ𝑅Λ𝑄 ∥ 1 ≤ ∥𝑄Λ𝑅∥ 𝐹 ∥𝑅Λ𝑄 ∥ 𝐹 = 𝛿. ∥𝑅Λ𝑄Λ𝑄 ∥ 1 ≤ ∥𝑅Λ𝑄 ∥ 𝐹 ∥𝑄Λ𝑄 ∥ 𝐹 ≤ 𝛿, Combining them gives

√ √ ∥𝑄Λ2𝑄 − Λ𝑄Λ∥ 1 ≤ 2𝛿 + 2 𝛿 ≤ 4 𝛿,

(22)

where the last inequality is from 𝛿 ≤ 1. Similarly, we can show that √ ∥𝑅Λ2𝑅 − Λ𝑅Λ∥ 1 ≤ 4 𝛿.

(23)

Plugging (21), (22), and (23) into (20), we have √ √ √ ∥𝑇 − 𝑃˜ ′ ∥ 1 ≤ 4 𝛿 + 4 𝛿 = 8 𝛿. □ Now we are ready to prove Theorem 5.6. Proof of Theorem 5.6. If 𝜖 = 0, take 𝑃 ′ = 𝑃 and Λ′ = Λ. Suppose next that 𝜖 ≥ 1/16 = Ω(1). Since 𝑁 ≥ 2, we can take any valid pair (𝑃 ′, Λ′ ) such that EΛ′ (𝑃 ′ ) = 0 and 𝑚 Λ′ (𝑃 ′ ) = 1/4. Then the required approximation bounds follow since ∥Λ − Λ′ ∥ 2𝐹 = 2 − 2 Tr(ΛΛ′ ) ≤ 2 = 𝑂 (𝜖 1/4 ),

∥𝑃 − 𝑃 ′ ∥ Λ ≤ 𝑚 Λ (𝑃) + 𝑚 Λ (𝑃 ′ ) ≤ 2 = 𝑂 (𝜖 1/4 ).

√ Now assume 0 < 𝜖 < 1/16. We claim that the threshold 𝑡 := max{ 𝑗 ∈ [𝑁 ] : 𝜌 𝑗 ≥ 𝜖} is well √ defined and satisfies 𝑡 < 𝑁 . Indeed, if the defining set were empty, then 𝐵 ≺ 𝜖𝐼 , giving √ 1 1 = 𝑚 Λ (𝑃) = Tr(Λ𝐵Λ) < 𝜖 < , 4 4 √ a contradiction. If 𝑡 = 𝑁 , then 𝐵 ⪰ 𝜖𝐼 , and hence √ 1√ 𝜖 = Tr(Λ𝐴Λ𝐵) ≥ 𝜖 Tr(Λ𝐴Λ) = 𝜖, 4

(24)

(25)

which implies 𝜖 ≥ 1/16, also a contradiction. Thus 1 ≤ 𝑡 < 𝑁 . It remains to check that the normalization factors Tr(𝑋 2 ) and Tr(𝑌 2 ) in the definition of Λ′ are nonzero. Let 𝑄 := Π𝑈 and 𝑅 := Π𝑈 ⊥ . If Tr(𝑋 2 ) = 0, then 𝑋 = 𝑄Λ𝑄 = 0. Since Λ ⪰ 0, this implies √ Λ = 𝑅Λ𝑅, and thus Λ = 𝑅Λ = Λ𝑅. Since 𝑅𝐵𝑅 ≺ 𝜖𝐼 , we would have √ √ 1 1 = 𝑚 Λ (𝑃) = Tr(Λ2 𝐵) = Tr(Λ2 · 𝑅𝐵𝑅) ≤ 𝜖 Tr(Λ2 ) = 𝜖 < , 4 4 √ a contradiction. Similarly, if Tr(𝑌 2 ) = 0, then Λ = 𝑄Λ = Λ𝑄. Thus by 𝑄𝐵𝑄 ⪰ 𝜖𝑄, we would have √ 1√ 𝜖 = Tr(Λ𝐴Λ𝐵) = Tr(Λ𝐴Λ · 𝑄𝐵𝑄) ≥ 𝜖 Tr(Λ𝐴Λ) = 𝜖, 4 which implies 𝜖 ≥ 1/16, again a contradiction. Therefore Tr(𝑋 2 ), Tr(𝑌 2 ) > 0, and the pair (𝑃 ′, Λ′ ) constructed in Section 5.2.1 is well defined. The conclusion now follows from Fact 5.7 and lemmas 5.16 and 5.17. □

One-Way One-Round Quantum Coloring of Directed Cycles

In this section, we return to the quantum LOCAL model and study one-way one-round quantum algorithms for the directed-cycle 𝑞-coloring problem. The processors are arranged on a directed 𝑛-cycle 𝑣 1 → 𝑣 2 → · · · → 𝑣𝑛 → 𝑣 1 .

In the standard LOCAL model, processors have unique identifiers drawn from a set of size poly (𝑛). Since quantum algorithms are inherently randomized, they can instead sample identifiers from a set of size poly (𝑛), which will be pairwise distinct with probability 1−1/poly (𝑛). It therefore suffices to consider processors that are initially identical and execute the same quantum algorithm. During the single communication round, each processor sends one quantum message to its successor and receives one from its predecessor; it then performs a local measurement and outputs a color in [𝑞]. We express the probability of a local collision exactly in terms of the Λ-energy of the corresponding measurement operators. This yields a general characterization for every 𝑞, and our main impossibility result for 𝑞 = 4.

6.1

General Reduction

We first propose a general conjecture on the energy of POVMs, and show that it is equivalent to the impossibility of one-way one-round quantum algorithms for 𝑞-coloring directed cycles. Conjecture 6.1. Fix an integer 𝑞 ≥ 2. There exists a universal constant 𝐶𝑞 > 0 such that for every choice of local dimension 𝑁 , PSD matrix Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, and 𝑞-outcome POVM M = {𝑃𝑖 }𝑖 ∈ [𝑞 ] on ℂ𝑁 ⊗ ℂ𝑁 , we have ∑︁ EΛ (𝑃𝑖 ) ≥ 𝐶𝑞 . 𝑖 ∈ [𝑞 ]

Theorem 6.2. For every fixed integer 𝑞 ≥ 2, the following two statements are equivalent: (i) Conjecture 6.1 holds; (ii) One-way one-round quantum LOCAL algorithms cannot solve the directed-cycle 𝑞-coloring problem. Proof. We first show that (i) implies (ii). Suppose Conjecture 6.1 holds for 𝑞. Since the local computation is unbounded, by purifying private randomness and intermediate measurements, each processor may store the sampled identifier, private randomness, and intermediate outcomes coherently in the private workspace. Then their effects can be absorbed into a pure bipartite state and a final POVM. Therefore without loss of generality, we may assume any one-way one-round quantum 𝑞-coloring algorithm has the following form 1. Each processor 𝑣 ℓ prepares an identical bipartite state |Ψ⟩ Aℓ Bℓ and sends register Bℓ to 𝑣 ℓ+1 . 2. Each processor 𝑣 ℓ performs the same 𝑞-outcome POVM measurement M = {𝑃𝑖 : 𝑖 ∈ [𝑞]} on the bipartite system Bℓ −1 Aℓ and outputs the color 𝑐 ℓ ∈ [𝑞]. We write the Schmidt decomposition of |Ψ⟩ as ∑︁ |Ψ⟩ = 𝜆𝑡 |𝜓𝑡 ⟩ A |𝜑𝑡 ⟩ B ,

where 𝜆𝑡 ≥ 0,

𝑡 ∈ [𝑁 ]

∑︁

𝜆𝑡2 = 1.

𝑡

Define a local unitary 𝑈 ∈ 𝑈 (𝑁 ) that maps {|𝜑¯𝑡 ⟩} to {|𝜓𝑡 ⟩}. Since each processor 𝑣 ℓ can apply 𝐼 ⊗ 𝑈 locally on Bℓ −1 Aℓ right after communication, we may absorb 𝐼 ⊗ 𝑈 into M, and assume without loss of generality that the shared bipartite state is ∑︁ |Ψ⟩ = 𝜆𝑡 |𝜑¯𝑡 , 𝜑𝑡 ⟩ = vec( Λ̄) ∈ ℂ𝑁 ⊗ ℂ𝑁 , (26) 𝑡 ∈ [𝑁 ]

Í where Λ := 𝑡 ∈ [𝑁 ] 𝜆𝑡 |𝜑𝑡 ⟩ ⟨𝜑𝑡 | is a PSD matrix with ∥Λ∥ 𝐹 = 1. For two adjacent processors 𝑣 ℓ and 𝑣 ℓ+1 , they hold the registers Bℓ −1 Aℓ Bℓ Aℓ+1 after communication. Their joint state is 𝜎Bℓ −1 Aℓ Bℓ Aℓ +1 := Tr A (|Ψ⟩ ⟨Ψ|) Bℓ −1 ⊗ |Ψ⟩ ⟨Ψ| Aℓ Bℓ ⊗ Tr B (|Ψ⟩ ⟨Ψ|) Aℓ +1 = Λ2 ⊗ |Ψ⟩ ⟨Ψ| ⊗ Λ̄2, Then the probability of both processors outputting the same color 𝑖 ∈ [𝑞] is Pr[𝑐 ℓ = 𝑐 ℓ+1 = 𝑖] = Tr((𝑃𝑖 ⊗ 𝑃𝑖 )𝜎) = EΛ (𝑃𝑖 ), where the last equality follows from Lemma 4.7. Thus by Conjecture 6.1, we have the local collision probability ∑︁ ∑︁ Pr[𝑐 ℓ = 𝑐 ℓ+1 ] = Pr[𝑐 ℓ = 𝑐 ℓ+1 = 𝑖] = EΛ (𝑃𝑖 ) ≥ 𝐶𝑞 , 𝑖 ∈ [𝑞 ]

𝑖 ∈ [𝑞 ]

which is lower bounded by a constant independent of cycle length 𝑛. Since the algorithm is symmetric on the cycle, Pr[𝑐 ℓ = 𝑐 ℓ+1 ] is the same for all ℓ ∈ [𝑛]. As the algorithm is one-way one-round, collision events on edges whose pairwise cyclic distances are at least 3 are independent. Selecting ⌊𝑛/3⌋ such edges, the algorithm produces a proper 𝑞-coloring with probability at most (1 − 𝐶𝑞 ) ⌊𝑛/3⌋ = 𝑜 (1). For the converse direction, suppose Conjecture 6.1 does not hold. Then for any 𝜖 > 0, there exists a 𝑞-outcome POVM M = {𝑃𝑖 }𝑖 ∈ [𝑞 ] and a PSD matrix Λ with ∥Λ∥ 𝐹 = 1 such that ∑︁ EΛ (𝑃𝑖 ) ≤ 𝜖. 𝑖 ∈ [𝑞 ]

Construct a one-way one-round quantum algorithm6 by preparing the state vec( Λ̄), sending one register to the neighbor, and performing the POVM M at each processor. Then the local failure Í probability is exactly 𝑖 ∈ [𝑞 ] EΛ (𝑃𝑖 ) ≤ 𝜖. By setting 𝜖 = 1/𝑛 2 and applying the union bound, the algorithm produces a proper 𝑞-coloring of the 𝑛-cycle with probability at least 1 − 𝑛 · 1/𝑛 2 = 1 − 1/𝑛. Thus it solves the directed-cycle 𝑞-coloring problem. □

6.2

Impossibility of ≤ 3 Colors

One-way one-round quantum 𝑞-coloring is known to be impossible for 𝑞 ≤ 3, from a boundeddependence perspective [LGR22, HSW17]. Namely, stationary 1-dependent 𝑞-coloring processes do not exist for 𝑞 ≤ 3. As a corollary, Conjecture 6.1 holds for 𝑞 ≤ 3. Lemma 6.3 (Section 2 of [GKDV89]). Given a stationary 1-dependent process (𝑌𝑡 ∈ {0, 1})𝑡 ∈ℤ , if 𝛼 := Pr[𝑌𝑡 = 1] ∈ [1/4, 1/3] , 6 Although the failure of Conjecture 6.1 only asserts the existence of ({𝑃 }, Λ), the induced algorithm can be made 𝑖

uniform: If Conjecture 6.1 fails, then there exists a finite-dimensional pair ({𝑃𝑖 }, Λ) of total energy at most 𝜖/2. Since the LOCAL model allows unbounded local computation, and the energy is computable and continuous, the algorithm can exhaustively search over dense enough approximations of ({𝑃𝑖 }, Λ) to find a candidate pair with total energy at most 𝜖.

then

√ √ (1 − 2 1 − 3𝛼) (1 + 1 − 3𝛼) 2 . Pr[𝑌𝑡 = 1, 𝑌𝑡 +1 = 1] ≥ 27

Using the above lemma, we show that any operator with mass significantly larger than 1/4 must have large energy. Lemma 6.4. Given any PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) such that 0 ⪯ 𝑃 ⪯ 𝐼 and any PSD matrix Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, if 𝑚 Λ (𝑃) = 1/4 + 𝜖 for some 𝜖 ≥ 0, then we have EΛ (𝑃) ≥ min{2𝜖/9, 1/54}. Proof. Consider the two-outcome POVM M := {𝑃 0 = 𝐼 − 𝑃, 𝑃 1 = 𝑃 } and the bipartite quantum state |Ψ⟩ = vec( Λ̄). Define the process (𝑌𝑡 ∈ {0, 1})𝑡 ∈ℤ by the following algorithm: 1. Each processor 𝑡 ∈ ℤ prepares state |Ψ⟩ in register A𝑡 B𝑡 , and sends B𝑡 to processor 𝑡 + 1. 2. Each processor 𝑡 ∈ ℤ applies M to registers B𝑡 −1 A𝑡 and outputs the measurement outcome 𝑌𝑡 ∈ {0, 1}. Since this is a one-way one-round algorithm where each processor runs the same algorithm, (𝑌𝑡 )𝑡 ∈ℤ is stationary and 1-dependent. By Lemma 4.7, Pr[𝑌𝑡 = 1] = 𝑚 Λ (𝑃) =

1 + 𝜖, 4

Pr[𝑌𝑡 = 𝑌𝑡 +1 = 1] = EΛ (𝑃).

Suppose first that 𝜖 ≤ 1/12. Then Pr[𝑌𝑡 = 1] = 1/4 + 𝜖 ∈ [1/4, 1/3], so Lemma 6.3 and the inequality √ 1 − 𝑥 ≤ 1 − 𝑥2 for 𝑥 ∈ [0, 1] give √︁ √︁ √ (1 − 2 1 − 3(1/4 + 𝜖)) (1 + 1 − 3(1/4 + 𝜖)) 2 (1 − 1 − 12𝜖) · 1 (1 − (1 − 6𝜖)) 2 EΛ (𝑃) ≥ ≥ ≥ = 𝜖. 27 27 27 9 Now suppose that 𝜖 > 1/12, and set 𝑐 := 1/(3𝑚 Λ (𝑃)) < 1. The operator 𝑃 ′ := 𝑐𝑃 satisfies 0 ⪯ 𝑃 ′ ⪯ 𝐼 and 𝑚 Λ (𝑃 ′ ) = 1/3. Applying the preceding case to 𝑃 ′ and observing that Λ-energy is quadratic in 𝑃, we obtain 2 1 1 1 𝑐 2 EΛ (𝑃) = EΛ (𝑃 ′ ) ≥ − = . 9 3 4 54 Hence EΛ (𝑃) ≥ 1/54, completing the proof.

□

Corollary 6.5. Conjecture 6.1 holds for 𝑞 ≤ 3. Proof. As a 2-outcome POVM can be viewed as a 3-outcome POVM by adding an extra zero operator, it suffices to show that for any 3-outcome POVM {𝑃𝑖 }𝑖 ∈ [3] , and any PSD matrix Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, we have ∑︁ EΛ (𝑃𝑖 ) = Ω(1). 𝑖 ∈ [3]

By averaging, there exists 𝑖 ∗ ∈ [3] such that 𝑚 Λ (𝑃𝑖 ∗ ) ≥ 1/3. Then by Lemma 6.4, we have ∑︁

EΛ (𝑃𝑖 ) ≥ EΛ (𝑃𝑖 ∗ ) ≥

𝑖 ∈ [3]

1 . 54 □

Corollary 6.5 also admits a direct operator-theoretic proof, without relying on boundeddependence arguments. See Appendix A for details. We remark that the above argument stops working from 𝑞 = 4 onward, as 1-dependent 4-coloring processes do exist [HHL18].

6.3

Impossibility of 4 Colors

Our main result is that Conjecture 6.1 holds for 𝑞 = 4, and consequently one-way one-round quantum 4-coloring of directed cycles is impossible. Formally, Theorem 6.6. For any 4-outcome POVM {𝑃𝑖 }𝑖 ∈ [4] on ℂ𝑁 ⊗ ℂ𝑁 and any PSD matrix Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, we have ∑︁ EΛ (𝑃𝑖 ) = Ω(1). 𝑖 ∈ [4]

Consequently, one-way one-round quantum LOCAL algorithms cannot 4-color directed cycles. The remainder of this section proves the above theorem. Section 6.3.1 first proves a special case where 𝑃 1 has zero energy and maximal mass, and Section 6.3.2 proves the general case. 6.3.1

Warm-Up: One Color with Exact Zero Energy

We first consider a special case where one POVM operator 𝑃 1 has zero energy and maximal mass. By the structural theorem for zero-energy operators (Theorem 5.4), we know that there exists an orthogonal decomposition ℂ𝑁 = 𝑈 ⊕ 𝑈 ⊥ such that 𝑃1 is the orthogonal projector onto the off-diagonal matrix space L(𝑈 ⊥, 𝑈 ). Then by projecting the other three operators 𝑃2, 𝑃3, 𝑃4 onto diagonal block L(𝑈 , 𝑈 ), we obtain a 3-outcome POVM on 𝑈 ⊗ 𝑈¯ , which reduces to the 3-coloring case (Corollary 6.5). Lemma 6.7. Given any 4-outcome POVM {𝑃𝑖 }𝑖 ∈ [4] on ℂ𝑁 ⊗ ℂ𝑁 and any PSD matrix Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, if 𝑃1 satisfies 1 𝑚 Λ (𝑃1 ) = and EΛ (𝑃1 ) = 0, 4 then we have 4 ∑︁ EΛ (𝑃𝑖 ) = Ω(1). 𝑖=1

Proof. If Λ is not full rank, let Π Λ be the orthogonal projector onto the support of Λ. Then we have Λ = ΠΛ Λ = ΛΠΛ . For each 𝑃𝑖 , define 𝑃𝑖′ := (ΠΛ ⊗ Π̄ Λ )𝑃𝑖 (Π Λ ⊗ Π̄Λ ). 42

Then one can verify that 𝑚 Λ (𝑃𝑖 ) = 𝑚 Λ (𝑃𝑖′ ) and EΛ (𝑃𝑖 ) = EΛ (𝑃𝑖′ ). Moreover, {𝑃𝑖′ } forms a POVM on the support of Λ ⊗ Λ̄, as 4 ∑︁

𝑃𝑖′ = (ΠΛ ⊗ Π̄ Λ )

𝑖=1

4 ∑︁

! 𝑃𝑖 (Π Λ ⊗ Π̄ Λ ) = ΠΛ ⊗ Π̄Λ .

𝑖=1

Thus without loss of generality, we assume Λ ≻ 0 in the following. As 𝑚 Λ (𝑃 1 ) = 1/4 and EΛ (𝑃1 ) = 0, by Theorem 5.4, there exists an orthogonal decomposition 𝑁 ℂ = 𝑈 ⊕ 𝑈 ⊥ such that (i) 𝑃1 = Π𝑊 where the linear space 0 𝑋 ⊥ |𝑈 | × |𝑈 ⊥ | 𝑊 := L(𝑈 , 𝑈 ) = :𝑋 ∈ℂ 0 0 in the basis of 𝑈 ⊕ 𝑈 ⊥ , (ii) 𝑈 , 𝑈 ⊥ are Λ-invariant, and (iii) Tr(Λ2 Π𝑈 ) = Tr(Λ2 Π𝑈 ⊥ ) = 1/2. Í By 𝑃 1 = Π𝑊 and 𝑖 ∈ [4] 𝑃𝑖 = 𝐼 , we have that 𝑃2 + 𝑃 3 + 𝑃 4 = Π𝑊 ⊥ , and then for each 𝑖 ≥ 2, we have 𝑃𝑖 ⪯ Π𝑊 ⊥ , i.e., the support of 𝑃𝑖 is contained in 𝑊 ⊥ . Notice that in the basis of 𝑈 ⊕ 𝑈 ⊥ , 𝑋 0 |𝑈 | × |𝑈 | |𝑈 ⊥ | × |𝑈 | |𝑈 ⊥ | × |𝑈 ⊥ | ⊥ :𝑋 ∈ℂ ,𝑌 ∈ ℂ ,𝑍 ∈ ℂ . 𝑊 = 𝑌 𝑍 Thus if we write the spectral decomposition of 𝑃𝑖 (𝑖 ≥ 2) as ∑︁ † 𝑃𝑖 = vec 𝑀𝑘(𝑖 ) vec 𝑀𝑘(𝑖 ) , 𝑘

then each 𝑀𝑘(𝑖 ) is in 𝑊 ⊥ , and thus can be written in block form 𝑀𝑘(𝑖 ) =

𝑀ˆ 𝑘(𝑖 ) ★

0 ★

where 𝑀ˆ 𝑘(𝑖 ) ∈ ℂ |𝑈 | × |𝑈 | . Now define the reduced operators ∑︁ † 𝑃ˆ𝑖 := vec 𝑀ˆ 𝑘(𝑖 ) vec 𝑀ˆ 𝑘(𝑖 ) ∈ L(𝑈 ⊗ 𝑈¯ ). 𝑘

Equivalently, 𝑃ˆ𝑖 = ΠL(𝑈 ,𝑈 ) 𝑃𝑖 ΠL(𝑈 ,𝑈 ) , so 0 ⪯ 𝑃ˆ𝑖 ⪯ 𝐼 . As ΠL(𝑈 ,𝑈 ) 𝑃 1 = Π L(𝑈 ,𝑈 ) Π𝑊 = 0, and we have 4 ∑︁ 𝑃ˆ𝑖 = ΠL(𝑈 ,𝑈 ) ,

𝑖 ∈ [4] 𝑃𝑖 = 𝐼 ,

𝑖=2 4 is a 3-outcome POVM on 𝑈 ⊗ 𝑈¯ . and thus {𝑃ˆ𝑖 }𝑖=2 By 𝑈 and 𝑈 ⊥ being Λ-invariant, Λ can be written in the basis of 𝑈 ⊕ 𝑈 ⊥ as

Λ= ⊥

Λ𝑈 0

⊥

0 Λ𝑈 ⊥

where Λ𝑈 ∈ ℂ |𝑈 | × |𝑈 | and Λ𝑈 ⊥ ∈ ℂ |𝑈 | × |𝑈 | are restrictions of Λ on 𝑈 and 𝑈 ⊥ respectively. Moreover, 43

by Tr(Λ2 Π𝑈 ) = Tr(Λ2 Π𝑈 ⊥ ) = 12 , we have Tr(Λ𝑈2 ) = Tr(Λ𝑈2 ⊥ ) = 21 . Then we define the reduced weight matrix √ Λ̂ := 2Λ𝑈 ∈ L(𝑈 ), which satisfies ∥ Λ̂∥ 2𝐹 = 2 Tr(Λ𝑈2 ) = 1. Since 4 ∑︁ 𝑖=2

𝑚 Λ̂ 𝑃ˆ𝑖 = Tr

4 ∑︁

! 𝑃ˆ𝑖 Λ̂2 ⊗ Λ̂¯ 2 = Tr( Λ̂2 ⊗ Λ̂¯ 2 ) = 1,

𝑖=2

by averaging, there exists 𝑗 ∈ {2, 3, 4} such that 𝑚 Λ̂ 𝑃ˆ 𝑗 ≥ 31 . By Lemma 6.4, we have EΛ̂ 𝑃ˆ 𝑗 = Ω(1). Finally, we show that EΛ (𝑃 𝑗 ) ≥ EΛ̂ (𝑃ˆ 𝑗 )/8. Observe that in the block form, for any 𝑘, ℓ, we have Λ𝑀𝑘( 𝑗 ) Λ𝑀ℓ( 𝑗 ) Λ =

Λ𝑈 𝑀ˆ 𝑘( 𝑗 ) Λ𝑈 𝑀ˆ ℓ( 𝑗 ) Λ𝑈 ★

Then ∥Λ𝑀𝑘( 𝑗 ) Λ𝑀ℓ( 𝑗 ) Λ∥ 2𝐹 ≥ ∥Λ𝑈 𝑀ˆ 𝑘( 𝑗 ) Λ𝑈 𝑀ˆ ℓ( 𝑗 ) Λ𝑈 ∥ 2𝐹 =

0 ★

1 ∥ Λ̂𝑀ˆ 𝑘( 𝑗 ) Λ̂𝑀ˆ ℓ( 𝑗 ) Λ̂∥ 2𝐹 . 8

Thus by Lemma 4.2, EΛ (𝑃 𝑗 ) =

∑︁

∥Λ𝑀𝑘( 𝑗 ) Λ𝑀ℓ( 𝑗 ) Λ∥ 2𝐹 ≥

𝑘,ℓ

1 ∑︁ 1 ∥ Λ̂𝑀ˆ 𝑘( 𝑗 ) Λ̂𝑀ˆ ℓ( 𝑗 ) Λ̂∥ 2𝐹 = EΛ̂ (𝑃ˆ 𝑗 ) = Ω(1). 8 8 𝑘,ℓ

Í4

𝑖=1 EΛ (𝑃𝑖 ) ≥ EΛ (𝑃 𝑗 ) = Ω(1), we conclude the proof.

6.3.2

□

General Case: Proof of Theorem 6.6

The high-level idea for the general case is to use the approximation theorem (Theorem 5.6) to reduce the problem to the special case: If the energy of 𝑃1 is already large, then we are done; otherwise, we can approximate 𝑃1 by a nearby operator 𝑃1′ with exactly zero energy, and then invoke the special case. Í4 Proof of Theorem 6.6. The case 𝑁 = 1 is trivial since {𝑃𝑖 } and Λ become scalars such that 𝑖=1 𝑃𝑖 = 1 Í4 Í4 2 Í4 and Λ = 1. Then 𝑖=1 EΛ (𝑃𝑖 ) = 𝑖=1 𝑃𝑖 ≥ ( 𝑖=1 𝑃𝑖 ) 2 /4 = 1/4. Í4 Í4 Now assume 𝑁 ≥ 2. By 𝑖=1 𝑃𝑖 = 𝐼 , we have 𝑖=1 𝑚 Λ (𝑃𝑖 ) = Tr(Λ2 ⊗ Λ̄2 ) = 1. By averaging and without loss of generality, assume 𝑚 Λ (𝑃 1 ) ≥ 1/4. We claim that we can further assume 𝑚 Λ (𝑃1 ) = 1/4. Indeed, let 𝑚 Λ (𝑃1 ) = 1/4 + 𝜖, and consider two cases: 1. If 𝜖 = Ω(1), then by Lemma 6.4, we have 2 1 EΛ (𝑃1 ) ≥ min 𝜖, = Ω(1), 9 54

and thus

Í4

𝑖=1 EΛ (𝑃𝑖 ) ≥ EΛ (𝑃 1 ) = Ω(1).

2. If 𝜖 = 𝑜 (1) > 0, then decompose 𝑃 1 = 𝑃ˆ1 + 𝑅, where 𝑃ˆ1, 𝑅 ⪰ 0, 𝑚 Λ (𝑃ˆ1 ) = 1/4 and 𝑚 Λ (𝑅) = 𝜖. Then define 𝑃ˆ2 := 𝑃2 + 𝑅, 𝑃ˆ3 := 𝑃3, 𝑃ˆ4 := 𝑃4, so that {𝑃ˆ𝑖 }𝑖 ∈ [4] forms a POVM, with 𝑚 Λ (𝑃ˆ1 ) = 1/4. Note that EΛ (𝑃ˆ1 ) ≤ EΛ (𝑃1 ) by 𝑃ˆ1 ⪯ 𝑃1 , EΛ (𝑃ˆ2 ) = EΛ (𝑃2 ) + Tr(Λ𝐴𝑃2 Λ𝐵𝑅 ) + Tr(Λ𝐴𝑅 Λ𝐵𝑃2 ) + Tr(Λ𝐴𝑅 Λ𝐵𝑅 ) ≤ EΛ (𝑃2 ) + Tr(Λ𝐵𝑅 Λ) + Tr(Λ𝐴𝑅 Λ) + Tr(Λ𝐴𝑅 Λ) = EΛ (𝑃 2 ) + 3𝜖 = EΛ (𝑃2 ) + 𝑜 (1), and EΛ (𝑃ˆ3 ) = EΛ (𝑃3 ), EΛ (𝑃ˆ4 ) = EΛ (𝑃4 ). Then we have 4 ∑︁

EΛ (𝑃𝑖 ) ≥

𝑖=1

Thus

Í4

𝑖=1 EΛ ( 𝑃𝑖 ) = Ω(1) implies

4 ∑︁

EΛ (𝑃ˆ𝑖 ) − 𝑜 (1).

𝑖=1

Í4

𝑖=1 EΛ (𝑃𝑖 ) = Ω(1).

Í4 Now assume 𝑚 Λ (𝑃1 ) = 1/4. If EΛ (𝑃1 ) = Ω(1), then 𝑖=1 EΛ (𝑃𝑖 ) ≥ EΛ (𝑃1 ) = Ω(1) and we are done. Otherwise, let E := EΛ (𝑃1 ) = 𝑜 (1). By Theorem 5.6, there exist 𝑍 and Λ′ such that EΛ′ (𝑍 ) = 0,

1 𝑚 Λ′ (𝑍 ) = , 4

∥𝑃1 − 𝑍 ∥ Λ = 𝑂 (E 1/4 ),

and

∥Λ − Λ′ ∥ 2𝐹 = 𝑂 (E 1/4 ).

Then by Lemma 6.8, there exists POVM {𝑃𝑖′ }𝑖 ∈ [4] such that 𝑃 1′ = 𝑍,

and

∥𝑃𝑖 − 𝑃𝑖′ ∥ Λ = 𝑂 (E 1/8 )

for each 𝑖 ∈ [4].

As EΛ′ (𝑃1′ ) = 0 and 𝑚 Λ′ (𝑃 1′ ) = 1/4, by applying Lemma 6.7, we have 4 ∑︁

EΛ′ (𝑃𝑖′ ) = Ω(1).

(27)

𝑖=1

Then by Lemma 4.9 and ∥Λ − Λ′ ∥ 2𝐹 = 𝑂 (E 1/4 ), we have for each 𝑖 ∈ [4], |EΛ (𝑃𝑖′ ) − EΛ′ (𝑃𝑖′ )| ≤ 6∥Λ − Λ′ ∥ 𝐹 = 𝑂 (E 1/8 ), and combining with (27) gives 4 ∑︁

EΛ (𝑃𝑖′ ) ≥

𝑖=1

4 ∑︁

EΛ′ (𝑃𝑖′ ) − 𝑂 (E 1/8 ) = Ω(1).

(28)

𝑖=1

As 𝐵 = Tr𝐵 (𝑃𝑖 (𝐼 ⊗ Λ̄2 )) ⪯ Tr𝐵 (𝐼 ⊗ Λ̄2 ) = Tr( Λ̄2 )𝐼 = 𝐼 , we have ∥𝐵∥ ∞ ≤ 1. Note that Λ𝐴Λ = Tr A ((Λ ⊗ Λ̄)𝑃𝑖 (Λ ⊗ Λ̄)) ⊤

and

Λ𝐴′ Λ = Tr A ((Λ ⊗ Λ̄)𝑃𝑖′ (Λ ⊗ Λ̄)) ⊤ .

By contractivity of trace norm under partial trace, we have ∥Λ𝐴Λ − Λ𝐴′ Λ∥ 1 ≤ ∥ (Λ ⊗ Λ̄) (𝑃𝑖 − 𝑃𝑖′ ) (Λ ⊗ Λ̄) ∥ 1 = ∥𝑃𝑖 − 𝑃𝑖′ ∥ Λ = 𝑂 (E 1/8 ). Then

|Tr((Λ𝐴Λ − Λ𝐴′ Λ)𝐵)| = 𝑂 (E 1/8 ).

Similarly, the second term |Tr(𝐴′ (Λ𝐵Λ − Λ𝐵 ′ Λ))| = 𝑂 (E 1/8 ). Thus for each 𝑖 ∈ [4], we have |EΛ (𝑃𝑖 ) − EΛ (𝑃𝑖′ )| = 𝑂 (E 1/8 ) = 𝑜 (1). Combining with (28) gives 4 ∑︁

EΛ (𝑃𝑖 ) ≥

𝑖=1

4 ∑︁

EΛ (𝑃𝑖′ ) − 𝑜 (1) = Ω(1).

𝑖=1

Therefore, Conjecture 6.1 holds for 𝑞 = 4, and by applying Theorem 6.2, no one-way one-round quantum LOCAL algorithm can 4-color directed cycles. □ Lemma 6.8. Given a 4-outcome POVM {𝑃𝑖 }𝑖 ∈ [4] on ℂ𝑁 ⊗ ℂ𝑁 and another PSD operator 𝑍 with 0 ⪯ 𝑍 ⪯ 𝐼 , let Λ ∈ ℂ𝑁 ×𝑁 be PSD with ∥Λ∥ 𝐹 = 1. If ∥𝑃 1 − 𝑍 ∥ Λ = 𝜖, then we can construct another POVM {𝑃𝑖′ }𝑖 ∈ [4] such that 𝑃1′ = 𝑍 and for each 2 ≤ 𝑖 ≤ 4, √ ∥𝑃𝑖 − 𝑃𝑖′ ∥ Λ = 𝑂 ( 𝜖). Proof. Define 𝑅 := 𝐼 − 𝑃 1 and 𝑆 := 𝐼 − 𝑍 . Then we have ∥𝑅 − 𝑆 ∥ Λ = ∥𝑃1 − 𝑍 ∥ Λ = 𝜖. For 2 ≤ 𝑖 ≤ 4, define

√ √ 1 𝑀𝑖 := 𝑅 + 𝑃𝑖 𝑅 + + Π ker(𝑅) . 3

Then {𝑀𝑖 } satisfies 0 ⪯ 𝑀𝑖 ⪯ 𝐼,

𝑃𝑖 = 𝑅 1/2 𝑀𝑖 𝑅 1/2

and

4 ∑︁

𝑀𝑖 = 𝐼 .

𝑖=2

Let 𝐷 := Λ ⊗ Λ̄, 𝑋 := 𝑅 1/2 𝐷 and 𝑌 := 𝑆 1/2 𝐷. By Lemma 3.7, there exists a unitary 𝑈 such that ∥𝑋 − 𝑈 𝑌 ∥ 2𝐹 ≤ ∥𝑋 †𝑋 − 𝑌 †𝑌 ∥ 1 = ∥𝐷 (𝑅 − 𝑆)𝐷 ∥ 1 = ∥𝑅 − 𝑆 ∥ Λ = 𝜖. Therefore,

√ ∥𝑅 1/2 𝐷 − 𝑈 𝑆 1/2 𝐷 ∥ 𝐹 = ∥𝑋 − 𝑈 𝑌 ∥ 𝐹 ≤ 𝜖.

Then define the new POVM elements as 𝑃 1′ = 𝑍,

and 𝑃𝑖′ = 𝑆 1/2𝑈 † 𝑀𝑖 𝑈 𝑆 1/2

for 𝑖 ≥ 2.

The set {𝑃𝑖′ }𝑖 ∈ [4] forms a POVM since 𝑃𝑖′ ⪰ 0 and 4 ∑︁

𝑃𝑖′ = 𝑍 + 𝑆 1/2𝑈 †

4 ∑︁

𝑀𝑖 𝑆 1/2 = 𝑍 + 𝑆 1/2𝑈 †𝑈 𝑆 1/2 = 𝑍 + 𝑆 = 𝐼 .

𝑖=2

𝑖=1

It remains to bound ∥𝑃𝑖 − 𝑃𝑖′ ∥ Λ = ∥𝐷 (𝑃𝑖 − 𝑃𝑖′ )𝐷 ∥ 1 for 2 ≤ 𝑖 ≤ 4. We compute 𝐷 (𝑃𝑖 − 𝑃𝑖′ )𝐷 = 𝐷 (𝑅 1/2 𝑀𝑖 𝑅 1/2 − 𝑆 1/2𝑈 † 𝑀𝑖 𝑈 𝑆 1/2 )𝐷 = 𝑋 † 𝑀𝑖 𝑋 − (𝑈 𝑌 ) † 𝑀𝑖 (𝑈 𝑌 ) By triangle inequality and Hölder’s inequality, we have ∥𝐷 (𝑃𝑖 − 𝑃𝑖′ )𝐷 ∥ 1 ≤ ∥ (𝑋 − 𝑈 𝑌 ) † 𝑀𝑖 𝑋 ∥ 1 + ∥ (𝑈 𝑌 ) † 𝑀𝑖 (𝑋 − 𝑈 𝑌 ) ∥ 1 ≤ ∥𝑋 − 𝑈 𝑌 ∥ 𝐹 ∥𝑀𝑖 𝑋 ∥ 𝐹 + ∥ (𝑈 𝑌 ) † 𝑀𝑖 ∥ 𝐹 ∥𝑋 − 𝑈 𝑌 ∥ 𝐹 Note that

∥𝑀𝑖 𝑋 ∥ 𝐹 = ∥𝑀𝑖 𝑅 1/2 𝐷 ∥ 𝐹 ≤ ∥𝐷 ∥ 𝐹 = 1, √ Combining with ∥𝑋 − 𝑈 𝑌 ∥ 𝐹 ≤ 𝜖, we have

and similarly,

∥ (𝑈 𝑌 ) † 𝑀𝑖 ∥ 𝐹 ≤ 1.

√ ∥𝐷 (𝑃𝑖 − 𝑃𝑖′ )𝐷 ∥ 1 ≤ 2∥𝑋 − 𝑈 𝑌 ∥ 𝐹 ≤ 2 𝜖, which concludes the proof.

□

References [ACRd+ 25]

Amirreza Akbari, Xavier Coiteux-Roy, Francesco d’Amore, François Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, Václav Rozhoň, and Jukka Suomela. Online locality meets distributed quantum computing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1295–1306. ACM, 2025. 2, 4

[AF14]

Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82–104, 2014. 2

[BBCR+ 25]

Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, MarcOlivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. Distributed quantum advantage for local problems. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), pages 451–462. ACM, 2025. 1

[BCC+ 25]

Alkida Balliu, Corinna Coupette, Antonio Cruciani, Francesco d’Amore, Massimo Equi, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, and Jukka Suomela. 47

New limits on distributed quantum advantage: Dequantizing linear programs. In 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of LIPIcs, pages 11:1–11:22. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025. 2 [BCd+ 26]

Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. Distributed quantum advantage in locally checkable labeling problems. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 1268–1308. SIAM, 2026. 1

[BEK14]

Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (Δ + 1)-coloring in linear (in Δ) time. SIAM Journal on Computing, 43(1):72–95, 2014. 4

[BK02]

Howard Barnum and Emanuel Knill. Reversing quantum dynamics with nearoptimal quantum and classical fidelity. Journal of Mathematical Physics, 43(5):2097– 2106, 2002. 13, 15

[Cha20]

Yi-Jun Chang. The complexity landscape of distributed locally checkable problems on trees. In 34th International Symposium on Distributed Computing (DISC 2020), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020. 1

[CRdG+ 24]

Xavier Coiteux-Roy, Francesco d’Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. No distributed quantum advantage for approximate graph coloring. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1901–1910. ACM, 2024. 2

[CRFdG+ 26] Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois, Marc-Olivier Renou, Jukka Suomela, and Isadora Veeren. Distributed quantum algorithms cannot color cycles with probability 1, 2026. 4 [CV86]

Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32–53, 1986. 4

[FMZ26]

Pierre Fraigniaud, Frédéric Magniez, and Isabella Ziccardi. No distributed quantum advantage for 3-coloring rooted trees and 2-coloring even cycles, 2026. 2, 4

[GKDV89]

Alberto Gandolfi, M Keane, and V De Valk. Extremal two-correlations of two-valued stationary one-dependent processes. Probability theory and related fields, 80(3):475–480, 1989. 13, 40

[GKM09]

Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? round-based models for quantum distributed computing. In International Symposium on Distributed Computing, pages 243–257. Springer, 2009. 1, 2

[HHL18]

Alexander E Holroyd, Tom Hutchcroft, and Avi Levy. Finitely dependent cycle coloring. Electronic Communications in Probability, 23, 2018. 2, 3, 4, 42

[HL16]

Alexander E Holroyd and Thomas M Liggett. Finitely dependent coloring. Forum of Mathematics, Pi, 4:e9, 2016. 4

[HSW17]

Alexander E Holroyd, Oded Schramm, and David B Wilson. Finitary coloring. The Annals of Probability, 45(5):2867–2898, 2017. 2, 4, 6, 40

[LGNR19]

François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of LIPIcs, pages 49:1–49:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. 1

[LGR22]

François Le Gall and Ansis Rosmanis. Non-trivial lower bound for 3-coloring the ring in the quantum local model. arXiv preprint arXiv:2212.02768, 2022. 2, 4, 40

[Lin92]

Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193–201, 1992. 1, 2, 4

[Man07]

Willem Mantel. Problem 28. Wiskundige Opgaven, 10:60–61, 1907. 6

[Nao91]

Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics, 4(3):409–412, 1991. 2, 4, 6

[NC10]

Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010. 12, 16

[Pel00]

David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. 1

[PS70]

Robert T Powers and Erling Størmer. Free states of the canonical anticommutation relations. Communications in Mathematical Physics, 16(1):1–33, 1970. 16

[Suo13]

Jukka Suomela. Survey of local algorithms. ACM Computing Surveys, 45(2):24:1–24:40, 2013. 1

An Alternative Proof for ≤ 3 Colors

This appendix provides an operator-theoretic proof of Conjecture 6.1 for 𝑞 ≤ 3, without relying on bounded-dependence arguments. Theorem A.1. Fix 𝑞 ∈ {2, 3}. For any POVM {𝑃𝑖 }𝑖 ∈ [𝑞 ] on ℂ𝑁 ⊗ ℂ𝑁 , and any PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, we have ( 𝑞 ∑︁ 1/8 if 𝑞 = 2, EΛ (𝑃𝑖 ) ≥ 𝐶𝑞 , where 𝐶𝑞 = 1/2916 if 𝑞 = 3. 𝑖=1 Í𝑞 Í𝑞 Proof. Since 𝑖=1 𝑃𝑖 = 𝐼 , we have 𝑖=1 𝑚 Λ (𝑃𝑖 ) = Tr(Λ2 ⊗ Λ̄2 ) = 1. By averaging, there exists an index 𝑗 ∈ [𝑞] such that 𝑚 := 𝑚 Λ (𝑃 𝑗 ) ≥ 1/𝑞. Consider the following two cases: • If 𝑞 = 2, then 𝑚 ≥ 1/2. By Lemma A.2, EΛ (𝑃 𝑗 ) ≥

𝑚(3𝑚 − 1) 1 ≥ . 2 8

• Suppose 𝑞 = 3. If 𝑚 ∈ [1/3, 1/2], then Lemma A.3 implies EΛ (𝑃 𝑗 ) ≥

(1/3) 4 (4/3 − 1) 2 1 𝑚 4 (4𝑚 − 1) 2 ≥ = . 4 4 2916

If instead 𝑚 > 1/2, then Lemma A.2 gives EΛ (𝑃 𝑗 ) ≥ Therefore, in both cases,

Í𝑞 𝑖=1

1 1 𝑚(3𝑚 − 1) > > . 2 8 2916

EΛ (𝑃𝑖 ) ≥ EΛ (𝑃 𝑗 ) ≥ 𝐶𝑞 .

□

The following two technical lemmas lower bound the energy of a single element 𝑃 with 𝑚 Λ (𝑃) ≥ 1/3. The first lemma gives a positive lower bound whenever 𝑚 Λ (𝑃) > 1/3. Lemma A.2. Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 , and PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, if 𝑚 := 𝑚 Λ (𝑃) ≥ 1/3, then 𝑚(3𝑚 − 1) EΛ (𝑃) ≥ . 2 Proof. Define matrices ⊤ 𝐴 := Tr A 𝑃 (Λ2 ⊗ 𝐼 ) ,

𝐵 := Tr B 𝑃 (𝐼 ⊗ Λ̄2 ) ,

𝑃˜ := (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄).

˜ ⊤ , and Λ𝐵Λ = Tr B (𝑃). ˜ Thus Then we have 0 ⪯ 𝑃˜ ⪯ Λ2 ⊗ Λ̄2 , Λ𝐴Λ = Tr A (𝑃) ˜ = 𝑚. Tr(Λ2𝐴) = Tr(Λ2 𝐵) = Tr(𝑃) Define

E := EΛ (𝑃)

If we write then

𝑥 := Tr(Λ𝐴Λ𝐴),

𝑅 := Λ1/2𝐴Λ1/2, E = Tr(𝑅𝑆),

Consider

𝑥 = Tr(𝑅 2 ),

𝑦 := Tr(Λ𝐵Λ𝐵).

𝑆 := Λ1/2 𝐵Λ1/2,

𝑦 = Tr(𝑆 2 ),

𝑚 = Tr(Λ𝑅) = Tr(Λ𝑆).

𝜖 := ∥𝑅 + 𝑆 − 2𝑚Λ∥ 2𝐹 .

Expanding the square and using Tr(Λ2 ) = ∥Λ∥ 2𝐹 = 1 gives 𝜖 = Tr(𝑅 2 ) + Tr(𝑆 2 ) + 2 Tr(𝑅𝑆) − 4𝑚 Tr(Λ𝑅) − 4𝑚 Tr(Λ𝑆) + 4𝑚 2 Tr(Λ2 ) = 𝑥 + 𝑦 + 2E − 4𝑚 2 . Since 𝜖 ≥ 0, we obtain E≥

4𝑚 2 − (𝑥 + 𝑦) . 2

It remains to bound 𝑥 + 𝑦. Observe ˜ ⊤ = Tr (Λ𝐴Λ) ⊤𝐴⊤ = 𝑥, Tr 𝑃˜ (𝐼 ⊗ 𝐴⊤ ) = Tr Tr A (𝑃)𝐴 50

(29)

(30)

and similarly Tr 𝑃˜ (𝐵 ⊗ 𝐼 ) = 𝑦. Next, compute Tr 𝑃˜ (𝐼 − 𝐵) ⊗ (𝐼 − 𝐴⊤ ) = Tr 𝑃˜ − Tr 𝑃˜ 𝐼 ⊗ 𝐴⊤ − Tr 𝑃˜ (𝐵 ⊗ 𝐼 ) + Tr 𝑃˜ 𝐵 ⊗ 𝐴⊤ = 𝑚 − 𝑥 − 𝑦 + Tr 𝑃˜ 𝐵 ⊗ 𝐴⊤ ≤ 𝑚 − 𝑥 − 𝑦 + 𝑚 2,

(31)

where the last inequality is by 0 ⪯ 𝑃˜ ⪯ Λ2 ⊗ Λ̄2 , and thus Tr 𝑃˜ (𝐵 ⊗ 𝐴⊤ ) ≤ Tr (Λ2 ⊗ Λ̄2 ) (𝐵 ⊗ 𝐴⊤ ) = Tr(Λ2 𝐵)Tr(Λ2𝐴) = 𝑚 2 . Since (𝐼 − 𝐵) ⊗ (𝐼 − 𝐴⊤ ) ⪰ 0 by 0 ⪯ 𝐴, 𝐵 ⪯ 𝐼 , and 𝑃˜ ⪰ 0, we have Tr 𝑃˜ (𝐼 − 𝐵) ⊗ (𝐼 − 𝐴⊤ ) ≥ 0. Combining with (31), we have

𝑥 + 𝑦 ≤ 𝑚 + 𝑚2 .

(32)

Finally, by (30) and (32), we conclude that E≥

4𝑚 2 − (𝑚 + 𝑚 2 ) 𝑚(3𝑚 − 1) = . 2 2 □

To handle the case of 𝑚 = 1/3, we need a more refined analysis: we show that when (30) is almost tight, i.e. 𝜖 is close to zero, another inequality (32) must have a large slack, which together give a positive lower bound when 𝑚 = 1/3. Formally, we have the following lemma. Lemma A.3. Given PSD 𝑃 ∈ L(ℂ𝑁 ⊗ ℂ𝑁 ) with 0 ⪯ 𝑃 ⪯ 𝐼 , and PSD Λ ∈ ℂ𝑁 ×𝑁 with ∥Λ∥ 𝐹 = 1, if 𝑚 := Tr 𝑃 (Λ2 ⊗ Λ̄2 ) ∈ [1/3, 1/2], then EΛ (𝑃) ≥

𝑚 4 (4𝑚 − 1) 2 . 4

Proof. Adopt the notation introduced in the proof of Lemma A.2, and define Δ := 𝑅 + 𝑆 − 2𝑚Λ.

=⇒

𝑅 + 𝑆 = 2𝑚Λ + Δ.

Then by (29), we have ∥Δ∥ 2𝐹 = 𝜖 = 𝑥 + 𝑦 + 2E − 4𝑚 2 . Set 𝑎 := 1 − 2𝑚 ≥ 0. The definition of Δ gives the identities Λ − 𝑆 = 𝑎Λ + 𝑅 − Δ, Λ − 𝑅 = 𝑎Λ + 𝑆 − Δ. (33) Define another auxiliary matrix 𝑃ˆ := (Λ1/2 ⊗ Λ̄1/2 )𝑃 (Λ1/2 ⊗ Λ̄1/2 ). Notice the relation 𝑃˜ = (Λ ⊗ Λ̄)𝑃 (Λ ⊗ Λ̄) = (Λ1/2 ⊗ Λ̄1/2 ) 𝑃ˆ (Λ1/2 ⊗ Λ̄1/2 ). We will estimate the quantity 𝐿 := Tr 𝑃ˆ ((Λ − 𝑆) ⊗ (Λ − 𝑅) ⊤ ) .

First, we upper bound 𝐿. By cyclicity of trace, Tr 𝑃ˆ ((Λ − 𝑆) ⊗ (Λ − 𝑅) ⊤ ) = Tr 𝑃ˆ (Λ − Λ1/2 𝐵Λ1/2 ) ⊗ (Λ − Λ1/2𝐴Λ1/2 ) ⊤ = Tr (Λ1/2 ⊗ Λ̄1/2 ) 𝑃ˆ (Λ1/2 ⊗ Λ̄1/2 ) (𝐼 − 𝐵) ⊗ (𝐼 − 𝐴⊤ ) = Tr 𝑃˜ ((𝐼 − 𝐵) ⊗ (𝐼 − 𝐴⊤ )) ≤ 𝑚 − 𝑥 − 𝑦 + 𝑚 2,

(34)

where the last inequality is from (31). We next lower bound 𝐿 by applying identities in (33) as 𝐿 = Tr 𝑃ˆ ((𝑎Λ + 𝑅 − Δ) ⊗ (𝑎Λ + 𝑆 − Δ) ⊤ ) = 𝑎 2 Tr 𝑃ˆ (Λ ⊗ Λ̄) ¯ + 𝑎 Tr 𝑃ˆ (𝑅 ⊗ Λ̄) + Tr 𝑃ˆ (𝑅 ⊗ 𝑆) ¯ + 𝑎 Tr 𝑃ˆ (Λ ⊗ 𝑆) ¯ + Tr 𝑃ˆ (Δ ⊗ Δ̄) . − 𝑎 Tr 𝑃ˆ (Λ ⊗ Δ̄) − 𝑎 Tr 𝑃ˆ (Δ ⊗ Λ̄) − Tr 𝑃ˆ (𝑅 ⊗ Δ̄) − Tr 𝑃ˆ (Δ ⊗ 𝑆) ˜ = 𝑚. The next three terms in the second line are nonnegative The first term Tr[𝑃ˆ (Λ ⊗ Λ̄)] = Tr(𝑃) ˆ as 𝑎 ≥ 0 and Λ, 𝑅, 𝑆, 𝑃 ⪰ 0. It remains to bound the absolute values of error terms in the third line. We write 𝐷 := Λ1/2 ΔΛ1/2 . As 14 + 12 + 41 = 1, the generalized Hölder’s inequality gives √ ∥𝐷 ∥ 1 ≤ ∥Λ1/2 ∥ 4 ∥Δ∥ 2 ∥Λ1/2 ∥ 4 = ∥Δ∥ 2 = ∥Δ∥ 𝐹 = 𝜖. For every PSD 𝑋 , by Hölder’s inequality and 0 ⪯ 𝑃 ⪯ 𝐼 , √ Tr 𝑃ˆ (𝑋 ⊗ Δ̄) = Tr 𝑃 (Λ1/2𝑋 Λ1/2 ) ⊗ 𝐷¯ ≤ ∥𝑃 ∥ ∞ ∥Λ1/2𝑋 Λ1/2 ⊗ 𝐷 ∥ 1 ≤ Tr(Λ𝑋 ) 𝜖, √ and similarly Tr 𝑃ˆ (Δ ⊗ 𝑋¯ ) ≤ Tr(Λ𝑋 ) 𝜖. Since Tr(Λ2 ) = 1 and Tr(Λ𝑅) = Tr(Λ𝑆) = 𝑚, the first four √ √ error terms are bounded in absolute value by 2(𝑎 + 𝑚) 𝜖 = 2(1 − 𝑚) 𝜖. Finally, the last error term ¯ ≤ ∥𝑃 ∥ ∞ ∥𝐷 ⊗ 𝐷¯ ∥ 1 ≤ ∥𝐷 ∥ 21 ≤ 𝜖. Tr 𝑃ˆ (Δ ⊗ Δ̄) = Tr 𝑃 (𝐷 ⊗ 𝐷) Consequently,

√ 𝐿 ≥ (1 − 2𝑚) 2𝑚 − 2(1 − 𝑚) 𝜖 − 𝜖.

(35)

Combining (34) and (35), we have √ 𝑚 − 𝑥 − 𝑦 + 𝑚 2 ≥ (1 − 2𝑚) 2𝑚 − 2(1 − 𝑚) 𝜖 − 𝜖. Substituting 𝜖 = 𝑥 + 𝑦 + 2E − 4𝑚 2 and simplifying gives √ 2E ≥ 4𝑚 3 − 𝑚 2 − 2(1 − 𝑚) 𝜖.

(36)

Moreover, by (32) and the assumption 𝑚 ≥ 1/3, 𝜖 = 𝑥 + 𝑦 + 2E − 4𝑚 2 ≤ 𝑚 + 𝑚 2 + 2E − 4𝑚 2 = 𝑚(1 − 3𝑚) + 2E ≤ 2E. Plugging this into (36), we obtain √ 2E ≥ 4𝑚 3 − 𝑚 2 − 2(1 − 𝑚) 2E. 52

(37)

√ Finally, we lower bound E using (37). Let 𝑢 := 2E, 𝑐 := 1 − 𝑚, and 𝑏 := 4𝑚 3 − 𝑚 2 = 𝑚 2 (4𝑚 − 1). Then (37) can be written as 𝑢 2 + 2𝑐𝑢 − 𝑏 ≥ 0. Since 𝑢 ≥ 0, it follows that √︁ 𝑢 ≥ −𝑐 + 𝑐 2 + 𝑏 = Therefore, E=

𝑏 𝑏 ≥ √ . √ 𝑐 + 𝑐2 + 𝑏 2 𝑐2 + 𝑏

𝑢2 𝑏2 . ≥ 2 8(𝑐 2 + 𝑏)

For 𝑚 ∈ [1/3, 1/2], 𝑐 2 + 𝑏 = 1 − 2𝑚 + 4𝑚 3 =

1 (1 − 2𝑚) (4𝑚 2 + 2𝑚 − 1) 1 − ≤ . 2 2 2

Here the final inequality follows because both factors in the subtracted term are nonnegative on [1/3, 1/2]. Consequently, 𝑏 2 𝑚 4 (4𝑚 − 1) 2 E≥ = . 4 4 □

Record · ID 667975 · SHA-256 56e0fdc15ae5194a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.