betaFeedback

WorksPhysics and Astronomy

Quantum Coloring Games on Complete Graphs

Abstract

We study the nonlocal game where two players are both given an input (xx and yy, respectively), from a set of size nn and, without communicating, must give outputs aa and bb, respectively, from a set of size m<nm < n, winning when (x=y)↔(a=b)(x = y) \leftrightarrow (a = b). This can be considered a graph coloring game on the complete graph with nn vertices. In the simplest case, the players get random equal inputs with probability 12\frac{1}{2} and random unequal inputs otherwise. We solve this case of the game, and many others, for both classical and quantum (i.e., where the players may share finite-dimensional entangled quantum states) strategy sets, proving the value (the probability of winning) of the optimal strategies and providing explicit strategies that attain this optimum for all nn and mm. Our optimal strategies are synchronous: i.e., the two players always give equal outputs when given equal inputs. These strategies remain optimal when the probability of receiving equal inputs is at least 2m+2\frac{2}{m + 2}. Across this wide range of cases, we find that quantum strategies have an advantage over classical strategies exactly when mm does not divide nn; this advantage is O(mn2)O\left(\frac{m}{n^2}\right).

Background

Nonlocal Games

A nonlocal game is a cooperative game, traditionally with two players named Alice and Bob and a single referee (also sometimes referred to as a verifier). The referee chooses inputs for each of Alice and Bob from a finite set of inputs via some fixed probability distribution. Alice and Bob, once they receive their inputs, may not communicate in any way, and must give outputs to the referee. The referee decides whether or not the game has been won according to some predicate function of the inputs and outputs.

The value of a nonlocal game on a class of strategies is defined as the supremum of the winning probabilities of all such strategies. The quantum value is the value on the class of quantum strategies (where Alice and Bob can share any finite amount of entanglement), and the classical value is the value on the class of classical strategies. The quantum advantage of a game can then be defined as the difference between these two quantities.

Interest in the quantum values of nonlocal games was popularized by Cleve, Høyer, Toner, and Watrous [9]. To use a famous example, in the CHSH game [8], Alice and Bob each receive a single bit and must each output a single bit, winning if the parity (i.e., XOR) of their outputs equals the logical AND of their inputs. The classical value of this game is 34=0.75\frac{3}{4}=0.75, whereas the quantum value is cos⁡2(π8)≈0.85\cos^{2}\left(\frac{\pi}{8}\right)\approx0.85, so the game has positive quantum advantage. These games have been proposed as experiments to refute “local hidden variable” theories of quantum mechanics [3], which would preclude any quantum advantage. Some such experiments have been successfully run [14].

Building upon this work was the study of XOR games. An XOR game is defined as one where Alice and Bob may each respond with only a single bit, and the referee considers only the inputs and the parity (i.e., XOR) of the outputs when deciding whether the players won. It can be quickly observed that the CHSH game is an XOR game, as indeed is the m=2m=2 case of the game we study. XOR games have received a substantial amount of study, from investigating their quantum values to bounding the entanglement needed to play optimally, and there is notably a method to compute the optimal solution for an XOR game via a semidefinite program [5, 9].

One interesting variation on the study of nonlocal games, and one that much of our paper will discuss, is analyzing the synchronous value of a nonlocal game [13]. A synchronous strategy is a strategy that guarantees that, if Alice and Bob are given the same input, then they will respond with the same output. Note that if we repeatedly give Alice and Bob the same input across multiple “rounds”, we do not require that they give the same output for each “round”, only that in each “round” Alice’s output matches Bob’s output. The synchronous value of a game for a class of strategies is defined as the supremum of the success probabilities of all synchronous strategies in that class.

Games that require the players to answer (classically impossible) questions about graphs have garnered significant recent research interest. One example of this is the study of the chromatic number and quantum chromatic number of a graph [6]. Both can be defined relative to a nonlocal game where Alice and Bob seek to convince a referee that they have a valid mm-coloring of a graph G=(V,E)G=(V,E). The referee asks each of Alice and Bob what color a specific vertex (vav_a and vbv_b, respectively) is. If given the same vertex, they must respond with the same color, and if given adjacent vertices, they must respond with different colors. The chromatic number of a graph GG is defined as the minimum number of colors for which this graph coloring game has classical value 1. Likewise, the quantum chromatic number of GG is the minimum number of colors where the graph coloring game has quantum value 1. Notably, not every graph’s quantum chromatic number equals its classical chromatic number: Cameron et al. give a graph with classical chromatic number 5 but quantum chromatic number 4 [6]. The graph coloring game on specifically complete graphs has received some special attention, which we will discuss in § 1.4.

Graph theory has also been used as a tool to investigate values of nonlocal games. In particular, Chailloux et al. construct a “game graph” encoding the verifier’s predicate [7], then bound both the classical and quantum values of a game by an efficiently computable quantity of this graph known as the Lovász theta number [7, 15].

Nonlocal games, and the quantum advantages that are achievable in some of them, have also shown some relevance to networking. Previous work has investigated how the superior correlation offered by shared entanglement could be used to improve coordination and load balancing in distributed or networked systems [2, 12].

The mm-Coloring Game on an nn-Node Complete Graph

In this paper, we will focus on the mm-coloring game on the complete graph KnK_n. More precisely, Alice and Bob are given inputs xx and yy, respectively, from a set of size nn (which we will represent as [n]:={k∈N0∣k<n}[n] := \{k \in\mathbb{N}_0 \mid k < n\}) and must give outputs aa and bb, respectively, from a set of size mm (which we will represent as [m][m]), winning when (x=y)⇔(a=b)(x = y) \Leftrightarrow(a = b).

To preserve symmetry, we will consider only input distributions π\pi over [n]×[n][n] \times[n] that assign equal probability to every pair of inputs where x≠yx \ne y and equal probability to every pair of inputs where x=yx = y: i.e., letting p:=P[x=y]p := \mathbb{P}[x = y], we have π(x,x)=pn\pi(x,x) = \frac{p}{n} for each x∈[n]x \in[n] and π(x,y)=1−pn(n−1)\pi(x,y) = \frac{1-p}{n(n-1)} (or 0 when n=1n = 1) whenever x≠yx \ne y.

When m≥nm \ge n, Alice and Bob may always simply output their respective inputs, in which case the win condition becomes (x=y)⇔(x=y)(x = y) \Leftrightarrow(x = y), which is trivially always true and hence this strategy is clearly optimal. Also, when m=1m = 1, Alice and Bob both must output 0 and thus have no choice in strategy. Hence, we focus on the interesting case where 2≤m<n2 \le m < n.

Similarly, when p=1p = 1, the players always win if Alice and Bob both output 0 regardless of their inputs, and when p=0p = 0 they always win if Alice always outputs 0 and Bob always outputs 1 (which is valid for all m≥2m \ge2), so we focus on the interesting case where p∈(0,1)p \in(0,1).

Applications in Distributed Computer Systems

This game can also be interpreted in a load-balancing scenario: imagine a networked system with mm machines and nn users. Users can submit jobs (queries that specify a user xx and yy respectively, which each correspond to one of the nn vertices of KnK_n) to two load balancers (Alice and Bob) far enough apart that classical communication between them is not viable. The load balancers must return a machine (aa and bb respectively, each corresponding to one of the mm colors) on which the job should run. We prefer for jobs for the same user to run on the same machine, so if both jobs are for the same user (i.e., x=yx = y), then we will consider it a success if a=ba = b. Jobs for different users should be spread across different machines, so if x≠yx \ne y, a success would require that a≠ba \ne b.

This framing also helps to justify the interest in pp, the probability that Alice and Bob receive the same input. Increasing pp can be seen as increasing the relative weight in the objective of equal-input scenarios, effectively increasing the penalty for routing one user’s jobs to two different machines relative to the penalty for placing two unrelated jobs on the same machine. Similarly, synchronous strategies for this game (i.e., strategies that guarantee that x=y⇒a=bx=y\Rightarrow a=b) can be thought of as strategies for the scenario where a given user’s jobs submitted in the same round absolutely must run on the same machine.

Previous Work

There are a few notable past results that will guide our work here. The first comes from Cameron et al., which states that the quantum chromatic number of a complete graph KnK_n is nn: that is, it is impossible to always convince a verifier (i.e., win our game) of a coloring with mm colors for any m<nm<n. Thus, they show that the game we study has no perfect quantum strategy. We prove stronger results, bounding the value more tightly and finding the exact value in many cases.

Secondly, Cui et al., in their analysis of the Bipartite Perfect Matching game, establish that there is a quantum advantage for the 2-coloring game played on a uniform input distribution on K3K_3, but that there is no advantage for KnK_n when n≥4n\geq4 [10]. This solves a special case of our game where m=2m=2 and p=1np=\frac{1}{n}.

Finally, Helton et al. bound the optimal synchronous value of the coloring game (on arbitrary graphs, not just complete ones) in terms of the graph correlation function [11], which they compute explicitly for (most) complete graphs [13]. We use these theorems to prove that our quantum strategy is optimal in the synchronous case.

Main Results

Our results all concern input distributions where the players receive uniformly random equal inputs with probability pp and uniformly random unequal inputs with probability 1−p1-p.

In § 3.2, we prove that the synchronous classical value of the game we study is

p+(1−p)(1−(⌊nm⌋−1)n+(⌈nm⌉+1)(n mod m)n(n−1)).p+(1-p)\left(1-\frac{\left(\left\lfloor\frac{n}{m}\right\rfloor-1\right)n+\left(\left\lceil\frac{n}{m}\right\rceil+1\right)(n\bmod m)}{n(n-1)}\right).

In § 3.3, we prove that this value is the classical value of the game whenever p≥2m+2p\geq\frac{2}{m+2}.

In § 4.1 we present a synchronous quantum strategy for this game with value

p+(1−p)(1−n−mm(n−1)),p+(1-p)\left(1-\frac{n-m}{m(n-1)}\right),

which is notably the same expression as the classical value when n mod m=0n\bmod m=0. We prove in § 4.3 that this strategy is optimal across all synchronous quantum strategies. We then prove in § 4.4 that the same strategy is optimal across all quantum strategies when p≥2n−m(m+2)n−2mp\geq\frac{2n-m}{(m+2)n-2m}.

Letting rr be the remainder of nn divided by mm, we then show in § 4.6 that this optimal strategy achieves an advantage (in terms of difference in value) of

(1−p)(r(m−r)mn(n−1)).(1-p)\left(\frac{r(m-r)}{mn(n-1)}\right).

over the best classical synchronous strategies, as well as over the best classical strategies when p≥2m+2p\geq\frac{2}{m+2}. Notably, we show that this advantage is 0 if and only if mm divides nn.

Preliminaries

We can begin by establishing some helpful results and definitions.

Value

The value ω\omega of a strategy is simply defined as the probability that the players win the game when using that strategy. If we define cxyc_{xy} as the probability that a=ba=b given the input pair (x,y)(x,y), the value can be written as

∑x=0n−1pncxx+∑x=0n−1∑y≠x1−pn(n−1)(1−cxy)=pn∑x=0n−1cxx+1−pn(n−1)∑x=0n−1∑y≠x(1−cxy).\sum_{x=0}^{n-1}\frac{p}{n}c_{xx}+\sum_{x=0}^{n-1}\sum_{y\ne x}\frac{1-p}{n(n-1)}(1-c_{xy})=\frac{p}{n}\sum_{x=0}^{n-1}c_{xx}+\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}\sum_{y\ne x}(1-c_{xy}).

We can insert a term to counteract the skipped index in the sums over yy, giving

pn∑x=0n−1cxx−1−pn(n−1)∑x=0n−1(1−cxx)+1−pn(n−1)∑x=0n−1∑y=0n−1(1−cxy).\frac{p}{n}\sum_{x=0}^{n-1}c_{xx}-\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}(1-c_{xx})+\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}(1-c_{xy}).

Rewriting this expression as a polynomial in the variables {cxy}\{c_{xy}\} gives

(1−p)nn−1−1−pn−1+(pn+1−pn(n−1))∑x=0n−1cxx−1−pn(n−1)∑x=0n−1∑y=0n−1cxy.\frac{(1-p)n}{n-1}-\frac{1-p}{n-1}+\left(\frac{p}{n}+\frac{1-p}{n(n-1)}\right)\sum_{x=0}^{n-1}c_{xx}-\frac{1-p}{n(n-1)}\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}c_{xy}.

The constant term in this polynomial can be simplified to 1−p1-p.

It is then convenient to define

ξ:=∑x=0n−1cxx\xi:= \sum_{x=0}^{n-1}c_{xx}

and

μ:=∑x=0n−1∑y=0n−1cxy.\mu:= \sum_{x=0}^{n-1}\sum_{y=0}^{n-1}c_{xy}.

Since 0≤cxy≤10\le c_{xy}\le1 for all (x,y)∈[n]2(x,y)\in[n]^2, 0≤ξ≤n0\le\xi\le n and 0≤μ≤n20\le\mu\le n^2.

Also, μ−ξ=∑x=0n−1∑y=0n−1cxy−∑x=0n−1cxx=∑x=0n−1∑y≠xcxy≥0\mu-\xi=\sum_{x=0}^{n-1}\sum_{y=0}^{n-1}c_{xy}-\sum_{x=0}^{n-1}c_{xx}=\sum_{x=0}^{n-1}\sum_{y\ne x}c_{xy}\ge0, so ξ≤μ\xi\le\mu.

We can then write the value in terms of these abbreviations:

References

  1. [1]T. Ando. Concavity of certain maps on positive definite matrices and applications to hadamard products. Linear Algebra and its Applications, 26:203–241, 1979.DOI
  2. [2]Venkat Arun, Vijay Chidambaram, and Scott Aaronson. Faster-than-light coordination for networked systems with quantum non-local games. In Proceedings of the 24th ACM Workshop on Hot Topics in Networks, HotNets ’25, page 10–18, New York, NY, USA, 2025. Association for Computing Machinery.DOI
  3. [3]J. S. Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1:195–200, Nov 1964.
  4. [4]Rajendra Bhatia. Positive Definite Matrices. Princeton University Press, 2007.
  5. [5]Jop Briët and Thomas Vidick. Explicit lower and upper bounds on the entangled value of multiplayer XOR games. Communications in Mathematical Physics, 321:181–207, 2013.DOI
  6. [6]Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter. On the quantum chromatic number of a graph. Electron. J. Comb., 14:2007, 9 2006.arxiv.org/abs/quant-ph/0608016
  7. [7]André Chailloux, Laura Mancinska, Giannicola Scarpa, and Simone Severini. Graph-theoretical Bounds on the Entangled Value of Non-local Games. In Steven T. Flammia and Aram W. Harrow, editors, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014), volume 27 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67–75, Dagstuhl, Germany, 2014. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.DOI
  8. [8]John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. In Physical Review Letters, volume 23, pages 880–884, 1969.
  9. [9]Richard Cleve, Peter Høyer, Ben Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, pages 236–249. IEEE, 2004.arxiv.org/abs/quant-ph/0404076
  10. [10]David Cui, Laura Mancinska, Seyed Nezhadi, and David Roberson. Quantum perfect matchings. Annales Henri Poincaré, 10 2025.arxiv.org/abs/2502.05136
  11. [11]Ken Dykema, Vern I. Paulsen, and Jitendra Prakash. Non-closure of the set of quantum correlations via graphs. Communications in Mathematical Physics, 365:1125–1142, 2017.arxiv.org/abs/1709.05032
  12. [12]Francisco Ferreira da Silva and Stephanie Wehner. Entanglement improving coordination in distributed systems. Phys. Rev. A, 113:062611, Jun 2026.DOI
  13. [13]J. William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I. Paulsen, and Travis B. Russell. Synchronous values of games. Annales Henri Poincaré, 25:4357–4397, 2024.arxiv.org/abs/2109.14741
  14. [14]B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson. Loophole-free bell inequality violation using electron spins separated by 1.3 kilometres. Nature, 526(7575):682–686, October 2015.
  15. [15]László Lovász. On the shannon capacity of a graph. IEEE Transactions on Information Theory, 25(1):1–7, 1979.DOI
  16. [16]Connor Paddock. Rounding near-optimal quantum strategies for nonlocal games to strategies using a maximally entangled state. Journal of Mathematical Physics, 66, 12 2025.DOI

Paper details

vlnc:W_z9njamg8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

ChatGPT, Claude, ChatGPT Astra 6, Claude Opus 5.5

View statement
Looking for related papers…
Contents