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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="23_2025_1632_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">$K_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> with odd <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="23_2025_1632_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$n \ge 7$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="23_2025_1632_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="32" /> </InlineMediaObject> <EquationSource Format="TEX">$K_{n,2}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>. Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leaves open the question of its complexity in graphs.

Quantum Perfect Matchings

期刊论文
出版模式：

开放获取
发表日期：

2025年10月14日

查看全文

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

摘要

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 \geq 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.