Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.10872

Quantum Colorings of Spheres

Olivier Lalonde

quant-phSubmitted Jun 9, 2026• Announced Jun 10, 2026• 0 citations
arXivHTMLPDF

Abstract

Cameron, Montanaro, Newman, Severini and Winter gave a construction which shows that, for $n \in \{2,4,8\}$, any graph $G$ which admits a real $n$-dimensional orthogonal representation is quantumly $n$-colorable. This result can be recast as the statement that the real sphere $S^{n-1}$ is quantumly $n$-colorable for these values of $n$. We investigate possible extensions of their construction. We first show that their hypothesis that the orthogonal representation be real-valued is required by proving that there is no analogue of this for the complex spheres, which all have quantum chromatic number strictly bigger than the dimension except in two dimensions. We also provide candidate finitary witnesses of this and show for the first time that the real and complex orthogonal ranks are distinct as a byproduct. For the real case, we show that if $S^{n-1}$ is quantumly $n$-colorable, then either $n=2$ or $n$ is a multiple of 4, and show that the converse holds whenever a Hadamard matrix of order $n$ exists. Hence, assuming the Hadamard conjecture, this completely classifies the dimensions to which the CMNSW construction can be extended. Our method of proof involves showing the equivalence between the existence of such a construction and the existence of a maximal code space for Clifford-algebraic errors given a clean ancilla, and we believe that the representation-theoretic techniques we use for tackling the latter problem could be of independent interest. It also follows from this equivalence that $S^{n-1}$ admits a rank-one quantum $n$-coloring if and only if $n \in \{2,4,8\}$, thereby settling a conjecture of Zeng and Zhang, as does the fact that for all $m \geq 1$, there exists a catalytic zero-error remote state preparation protocol for real $m$-qubit states with $m$ bits of communication and which consumes $m$ ebits.

Related papers

Oddities of Quantum Colorings

Laura Mančinska, David E. Roberson

The main purpose of this work is to collect some interesting facts related to quantum graph coloring.We consider the orthogonality graph of the three-dimensional vectors with entries from the set {-1, 0, 1}.If we ignore the overall sign of the vectors, this yields a graph on thirteen vertices, which we denote by G13.It turns out that G13 (or the graph obtained from this by adding an apex vertex) is the smallest known example which exhibits separations between several graph parameters.We are particularly interested in using G13 to separate quantum graph parameters from their classical counterparts.We give a proof that G13 is not quantum 3-colorable, which shows that its orthogonal rank is strictly less than its quantum chromatic number.This also proves, along with other previously known results, that adding an apex vertex to G13 does not change its quantum chromatic number.The graph G13 is the first and only known graph with either of these properties.Lastly, we investigate a graph construction used for taking instances of 3-SAT to instances of 3-COLORING.We show that any graph constructed in this manner has an orthogonal representation in dimension three if and only if it is 3-colorable.Since it has been previously shown that there are such graphs with quantum 3-colorings but no classical 3-colorings, it follows that quantum chromatic number can be strictly less than orthogonal rank.Together with the above, this proves that orthogonal rank and quantum chromatic number are not comparable as graph parameters.

arXiv:1801.03542•Baltic Journal of Modern Computing•Dec 19, 2016•2 citations

On the Quantum Chromatic Numbers of Small Graphs

Olivier Lalonde

We make two contributions pertaining to the study of the quantum chromatic numbers of small graphs. Firstly, in an elegant paper, Mančinska and Roberson [Baltic Journal on Modern Computing, 4(4), 846-859, 2016] gave an example of a graph $G_{14}$ on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank-$r$ quantum chromatic numbers. While it can now be shown that for every $r$, $\chi_q$ and $\chi^{(r)}_q$ are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph $G_{21}$ on 21 vertices with $\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4$ and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph $G_{msg}$ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies $\chi_q(G_{msg}) = 3$ and $\chi^{(1)}_q(G_{msg}) = 4$. In addition, $G_{21}$ provides the first provable separation between the parameters $\chi^{(1)}_q$ and $\chi^{(2)}_q$. We believe that our techniques for constructing $G_{21}$ and lower bounding its orthogonal rank could be of independent interest.

arXiv:2311.08194•The Electronic Journal of Combinatorics•Feb 14, 2025•1 citation

A counterexample to the quantum Hedetniemi conjecture

Julius A. Zeiss

Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs $G,H$ with \[ χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).\]The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital $C^*$-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and $C^*$-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.

math.COCross-listedarXiv:2609.20690•Sep 18, 2026•0 citations

χ-colorable graph states: closed-form expressions and quantum orthogonal arrays

Konstantinos-Rafail Revis, Hrachya Zakaryan, Zahra Raissi

Abstract Graph states are a fundamental class of multipartite entangled quantum states with wide-ranging applications in quantum information and computation. In this work, we develop a systematic approach for constructing and analyzing χ-colorable graph states, deriving explicit closed-form expressions for arbitrary χ. For a broad family of two- and three-colorable graph states, the representations obtained using only local operations require a minimal number of terms in the Z-eigenbasis. We prove that every two-colorable graph state is local Clifford (LC) equivalent to a state expressible as a summation of rows of an orthogonal array (OA). For graph states with χ > 2, we show that they are LC-equivalent to quantum OAs, establishing a direct combinatorial connection between multipartite entanglement and structured quantum states. Furthermore, the upper and lower bounds of the Schmidt measure for graph states with arbitrary χ colorability are discussed, extending the results for an arbitrary local dimension. Our results offer an efficient and practical method for systematically constructing graph states, optimizing their representation in quantum circuits, and identifying structured forms of multipartite entanglement. This approach also connects graph states to k-uniform and absolutely maximally entangled states, motivating further exploration of the structure of entangled states and their applications in quantum networks, quantum error correction, and measurement based quantum computing.

arXiv:2408.09515•Journal of Physics A Mathematical and Theoretical•Aug 21, 2025•0 citations

Chromatic Constraints on Quantum Observables: Gaps, Contextuality, and Separability

Karl Svozil

Intertwined complete projective experiments share outcomes, motivating the search for a common spectral labeling across contexts. Strong coloring tests whether complete contexts admit one context-independent nondegenerate spectrum; when that labeling exists, chromatic separability tests which event distinctions it preserves. We distinguish these questions from ordinary Kochen--Specker statelessness, geometric realizability, event-order representation, and Born-probability models. A state extends to a strong d-coloring exactly when deletion of its support leaves a (d-1)-colorable graph. Faithful real 17- and 21-ray restrictions of completed Yu--Oh have separating ordinary states but forced color identities; one quantum preparation requires exactly 1/9 nonextendable weight despite admitting an ordinary-state model. Independent Hermitian projection arguments correct earlier inferences from a chromatic gap to statelessness or nonrealizability. Hesse's complex 37-ray example separates real and complex geometry and has exact state-family minima 6/7/18 for three representation requirements. A rational two-plane construction gives a linear real 65-ray example with 393,216 states and explicit event-order and probability failures. General and specified ancestry results distinguish geometric KS extensions from abstract chromatic-to-stateless constructions. Detailed enumerations, regenerated state certificates, and extended proofs are supplementary.

quant-pharXiv:2607.04289•Jul 7, 2026•0 citations

Noncontextual coloring of orthogonality hypergraphs

Mohammad Hadi Shekarriz, Karl Svozil

We discuss representations and colorings of orthogonality hypergraphs in terms of their two-valued states interpretable as classical truth assignments. Such hypergraphs, if they allow for a faithful orthogonal representation, have quantum mechanical realizations in terms of intertwined contexts or maximal observables that are widely discussed as empirically testable criteria for contextuality. A reconstruction is possible for the class of perfectly separable hypergraphs. Colorings can be constructed from a minimal set of two-valued states. Some examples from exempt categories are presented, which either cannot be reconstructed by two-valued states or whose two-valued states cannot yield a chromatic number that is equal to the maximal clique number.

arXiv:2105.08520•Journal of Mathematical Physics•Mar 1, 2022•4 citations
Cameron, Montanaro, Newman, Severini and Winter gave a construction which shows that, for n∈{2,4,8}n \in \{2,4,8\}n∈{2,4,8}, any graph GGG which admits a real nnn-dimensional orthogonal representation is quantumly nnn-colorable. This result can be recast as the statement that the real sphere Sn−1S^{n-1}Sn−1 is quantumly nnn-colorable for these values of nnn. We investigate possible extensions of their construction. We first show that their hypothesis that the orthogonal representation be real-valued is required by proving that there is no analogue of this for the complex spheres, which all have quantum chromatic number strictly bigger than the dimension except in two dimensions. We also provide candidate finitary witnesses of this and show for the first time that the real and complex orthogonal ranks are distinct as a byproduct. For the real case, we show that if Sn−1S^{n-1}Sn−1 is quantumly nnn-colorable, then either n=2n=2n=2 or nnn is a multiple of 4, and show that the converse holds whenever a Hadamard matrix of order nnn exists. Hence, assuming the Hadamard conjecture, this completely classifies the dimensions to which the CMNSW construction can be extended. Our method of proof involves showing the equivalence between the existence of such a construction and the existence of a maximal code space for Clifford-algebraic errors given a clean ancilla, and we believe that the representation-theoretic techniques we use for tackling the latter problem could be of independent interest. It also follows from this equivalence that Sn−1S^{n-1}Sn−1 admits a rank-one quantum nnn-coloring if and only if n∈{2,4,8}n \in \{2,4,8\}n∈{2,4,8}, thereby settling a conjecture of Zeng and Zhang, as does the fact that for all m≥1m \geq 1m≥1, there exists a catalytic zero-error remote state preparation protocol for real mmm-qubit states with mmm bits of communication and which consumes mmm ebits.
The main purpose of this work is to collect some interesting facts related to quantum graph coloring.We consider the orthogonality graph of the three-dimensional vectors with entries from the set {-1, 0, 1}.If we ignore the overall sign of the vectors, this yields a graph on thirteen vertices, which we denote by G13.It turns out that G13 (or the graph obtained from this by adding an apex vertex) is the smallest known example which exhibits separations between several graph parameters.We are particularly interested in using G13 to separate quantum graph parameters from their classical counterparts.We give a proof that G13 is not quantum 3-colorable, which shows that its orthogonal rank is strictly less than its quantum chromatic number.This also proves, along with other previously known results, that adding an apex vertex to G13 does not change its quantum chromatic number.The graph G13 is the first and only known graph with either of these properties.Lastly, we investigate a graph construction used for taking instances of 3-SAT to instances of 3-COLORING.We show that any graph constructed in this manner has an orthogonal representation in dimension three if and only if it is 3-colorable.Since it has been previously shown that there are such graphs with quantum 3-colorings but no classical 3-colorings, it follows that quantum chromatic number can be strictly less than orthogonal rank.Together with the above, this proves that orthogonal rank and quantum chromatic number are not comparable as graph parameters.
We make two contributions pertaining to the study of the quantum chromatic numbers of small graphs. Firstly, in an elegant paper, Mančinska and Roberson [Baltic Journal on Modern Computing, 4(4), 846-859, 2016] gave an example of a graph G14G_{14}G14​ on 14 vertices with quantum chromatic number 4 and classical chromatic number 5, and conjectured that this is the smallest graph exhibiting a separation between the two parameters. We describe a computer-assisted proof of this conjecture, thereby resolving a longstanding open problem in quantum graph theory. Our second contribution pertains to the study of the rank-rrr quantum chromatic numbers. While it can now be shown that for every rrr, χq\chi_qχq​ and χq(r)\chi^{(r)}_qχq(r)​ are distinct, few small examples of separations between these parameters are known. We give the smallest known example of such a separation in the form of a graph G21G_{21}G21​ on 21 vertices with χq(G21)=χq(2)(G21)=4\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4χq​(G21​)=χq(2)​(G21​)=4 and $ \xi(G_{21}) = \chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a graph GmsgG_{msg}Gmsg​ on 57 vertices that was first considered in the aforementioned paper of Mančinska and Roberson and which satisfies χq(Gmsg)=3\chi_q(G_{msg}) = 3χq​(Gmsg​)=3 and χq(1)(Gmsg)=4\chi^{(1)}_q(G_{msg}) = 4χq(1)​(Gmsg​)=4. In addition, G21G_{21}G21​ provides the first provable separation between the parameters χq(1)\chi^{(1)}_qχq(1)​ and χq(2)\chi^{(2)}_qχq(2)​. We believe that our techniques for constructing G21G_{21}G21​ and lower bounding its orthogonal rank could be of independent interest.
Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs G,HG,HG,H with χ(G×H)≤1538<1539=min⁡(χq(G),χq(H)). χ(G\times H) \leq 1538 < 1539 = \min(χ_q(G),χ_q(H)).χ(G×H)≤1538<1539=min(χq​(G),χq​(H)).The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital C∗C^*C∗-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and C∗C^*C∗-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.
Abstract Graph states are a fundamental class of multipartite entangled quantum states with wide-ranging applications in quantum information and computation. In this work, we develop a systematic approach for constructing and analyzing χ-colorable graph states, deriving explicit closed-form expressions for arbitrary χ. For a broad family of two- and three-colorable graph states, the representations obtained using only local operations require a minimal number of terms in the Z-eigenbasis. We prove that every two-colorable graph state is local Clifford (LC) equivalent to a state expressible as a summation of rows of an orthogonal array (OA). For graph states with χ > 2, we show that they are LC-equivalent to quantum OAs, establishing a direct combinatorial connection between multipartite entanglement and structured quantum states. Furthermore, the upper and lower bounds of the Schmidt measure for graph states with arbitrary χ colorability are discussed, extending the results for an arbitrary local dimension. Our results offer an efficient and practical method for systematically constructing graph states, optimizing their representation in quantum circuits, and identifying structured forms of multipartite entanglement. This approach also connects graph states to k-uniform and absolutely maximally entangled states, motivating further exploration of the structure of entangled states and their applications in quantum networks, quantum error correction, and measurement based quantum computing.
Intertwined complete projective experiments share outcomes, motivating the search for a common spectral labeling across contexts. Strong coloring tests whether complete contexts admit one context-independent nondegenerate spectrum; when that labeling exists, chromatic separability tests which event distinctions it preserves. We distinguish these questions from ordinary Kochen--Specker statelessness, geometric realizability, event-order representation, and Born-probability models. A state extends to a strong d-coloring exactly when deletion of its support leaves a (d-1)-colorable graph. Faithful real 17- and 21-ray restrictions of completed Yu--Oh have separating ordinary states but forced color identities; one quantum preparation requires exactly 1/9 nonextendable weight despite admitting an ordinary-state model. Independent Hermitian projection arguments correct earlier inferences from a chromatic gap to statelessness or nonrealizability. Hesse's complex 37-ray example separates real and complex geometry and has exact state-family minima 6/7/18 for three representation requirements. A rational two-plane construction gives a linear real 65-ray example with 393,216 states and explicit event-order and probability failures. General and specified ancestry results distinguish geometric KS extensions from abstract chromatic-to-stateless constructions. Detailed enumerations, regenerated state certificates, and extended proofs are supplementary.
We discuss representations and colorings of orthogonality hypergraphs in terms of their two-valued states interpretable as classical truth assignments. Such hypergraphs, if they allow for a faithful orthogonal representation, have quantum mechanical realizations in terms of intertwined contexts or maximal observables that are widely discussed as empirically testable criteria for contextuality. A reconstruction is possible for the class of perfectly separable hypergraphs. Colorings can be constructed from a minimal set of two-valued states. Some examples from exempt categories are presented, which either cannot be reconstructed by two-valued states or whose two-valued states cannot yield a chromatic number that is equal to the maximal clique number.