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:2502.05136 · Annales Henri Poincaré

Quantum Perfect Matchings

David Cui, Laura Mančinska, Seyed Sajjad Nezhadi, David E. Roberson

Published Oct 14, 2025• 0 citations
arXivHTMLPDF

Abstract

Abstract We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for L-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. Our definitions come from the fact that these games are classical property tests for the corresponding matching conditions. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings. Finally, we provide characterizations of when graphs exhibit these extended properties: For nonsignaling matchings, we give a complete combinatorial characterization. In particular, a graph has a nonsignaling perfect matching if and only if it admits a fractional perfect matching that has bounded value on triangles. In bipartite graphs, the nonsignaling L-perfect matching property is achieved exactly when the left component of the graph can be split into two disjoint subgraphs: one with a classical L-perfect matching and another with left-degree 2. In the quantum setting, we show that complete graphs $$K_n$$ K n with odd $$n \ge 7$$ n ≥ 7 have quantum perfect matchings. We prove that a graph has a quantum perfect matching if and only if the quantum independence number of its line graph is maximal, extending a classical relationship between perfect matchings and line graph independence numbers. For bipartite graphs, we establish that the L-perfect matching game does not exhibit quantum pseudotelepathy, but we characterize the quantum advantage for complete bipartite graphs $$K_{n,2}$$ K n , 2 . Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leaves open the question of its complexity in graphs.

DOI
10.1007/s00023-025-01632-5

Related papers

Communication Complexity of Graph Isomorphism, Coloring, and Distance Games

Pierre Botteron, Moritz Weber

In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter $D\in\mathbb N$, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.

arXiv:2406.02199•Jun 4, 2024•0 citations

Complete characterization of perfect quantum strategies in quantum magic rectangle games

Yueying Wu

We provide a complete structural characterization of perfect quantum strategies for arbitrary quantum magic rectangle games. We derive necessary and sufficient conditions that jointly constrain the shared state and measurement operators, establishing a unified analytical framework for perfect nonlocal strategies in this setting. Our results show that all perfect quantum solution states (PQSS) must exhibit a specific algebraic--combinatorial structure, ruling out a priori assumptions about particular entangled resources and clarifying the full class of states compatible with perfect correlations. We further show that perfect quantum strategies do not exist for $2 \times n$ quantum magic rectangle games with odd $n$, and introduce a corresponding quantum magic rectangle inequality to characterize optimal non-perfect strategies. While our results are structural, they may provide a foundation for future developments in quantum information and quantum cryptography based on perfect nonlocal correlations.

quant-pharXiv:2604.18317•Apr 21, 2026•0 citations

Relaxations of Graph Isomorphism

Mancinska, Laura, David E. Roberson, Samal, Robert +2 more

We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.

Leibniz international proceedings in informatics•Jan 1, 2017•13 citations

Entanglement and Non-locality in Games and Graphs

Arthur Mehta

Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].

•Jun 1, 2021•0 citations

Maximally entangled states are not complete for pseudo-telepathy

Olivier Lalonde

One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.

quant-pharXiv:2608.05378•Aug 7, 2026•0 citations

New bounds on the classical and quantum communication complexity of some graph properties

Gábor Ivanyos, Hartmut Klauck, Troy Lee +2 more

We study the communication complexity of a number of graph properties where the edges of the graph $G$ are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.

arXiv:1204.4596•Leibniz international proceedings in informatics•Jan 1, 2012•11 citations
Abstract We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for L-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. Our definitions come from the fact that these games are classical property tests for the corresponding matching conditions. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings. Finally, we provide characterizations of when graphs exhibit these extended properties: For nonsignaling matchings, we give a complete combinatorial characterization. In particular, a graph has a nonsignaling perfect matching if and only if it admits a fractional perfect matching that has bounded value on triangles. In bipartite graphs, the nonsignaling L-perfect matching property is achieved exactly when the left component of the graph can be split into two disjoint subgraphs: one with a classical L-perfect matching and another with left-degree 2. In the quantum setting, we show that complete graphs KnK_nKn​ K n with odd n≥7n \ge 7n≥7 n ≥ 7 have quantum perfect matchings. We prove that a graph has a quantum perfect matching if and only if the quantum independence number of its line graph is maximal, extending a classical relationship between perfect matchings and line graph independence numbers. For bipartite graphs, we establish that the L-perfect matching game does not exhibit quantum pseudotelepathy, but we characterize the quantum advantage for complete bipartite graphs Kn,2K_{n,2}Kn,2​ K n , 2 . Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leaves open the question of its complexity in graphs.
In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter D∈ND\in\mathbb ND∈N, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.
We provide a complete structural characterization of perfect quantum strategies for arbitrary quantum magic rectangle games. We derive necessary and sufficient conditions that jointly constrain the shared state and measurement operators, establishing a unified analytical framework for perfect nonlocal strategies in this setting. Our results show that all perfect quantum solution states (PQSS) must exhibit a specific algebraic--combinatorial structure, ruling out a priori assumptions about particular entangled resources and clarifying the full class of states compatible with perfect correlations. We further show that perfect quantum strategies do not exist for 2×n2 \times n2×n quantum magic rectangle games with odd nnn, and introduce a corresponding quantum magic rectangle inequality to characterize optimal non-perfect strategies. While our results are structural, they may provide a foundation for future developments in quantum information and quantum cryptography based on perfect nonlocal correlations.
We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.
Quantum graph theory, also known as non-commutative graph theory, is an operator space generalization of graph theory. The independence number, and Lovasz theta function were generalized to this setting by Duan, Severini, and Winter [DSW13] and two different version of the chromatic number were introduced by Stahlke [Sta16] and Paulsen [HPP16]. We introduce two new generalizations of the chromatic number to non-commutative graphs and provide an upper bound on the parameter of Stahlke. We provide a generalization of the graph complement and show the chromatic number of the orthogonal complement of a non-commutative graph is bounded below by its theta number. We also provide a generalization of both Sabidussi's Theorem and Hedetniemi's conjecture to non-commutative graphs. The study of non-local games considers scenarios in which separated players collaborate to provide satisfying responses to questions given by a referee. The condition of separating players makes non-local games an excellent setting to gain insight into quantum phenomena such as entanglement and non-locality. Non-local games can also provide protocols known as self-tests. Self-testing allows an experimenter to interact classically with a black box quantum system and certify that a specific entangled state was present and a specific set of measurements were performed. The most studied self-test is the CHSH game which certifies the presence of a single EPR entangled state and the use of anti-commuting Pauli measurements. We introduce an algebraic generalization of CHSH and obtain a self-test for non-Pauli operators resolving an open question posed by Coladangelo and Stark (QIP 2017). Our games also provide a self-test for states other than the maximally entangled state, and hence resolves the open question posed by Cleve and Mittal (ICALP 2012). This thesis is primarily based on two collaborative works written by the author and several coauthors [CMMN20], [KM19].
One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.
We study the communication complexity of a number of graph properties where the edges of the graph GGG are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.