Quantum Perfect Matchings

• URL: http://arxiv.org/abs/2502.05136v1
• Date: Fri, 07 Feb 2025 18:13:05 GMT
• Title: Quantum Perfect Matchings
• Authors: David Cui, Laura Mančinska, Seyed Sajjad Nezhadi, David E. Roberson,
• Abstract summary: We introduce nonlocal games that test for $L$-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings.
• Score: 0.0
• License:
• 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 characterizations. 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. \item 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$ with odd $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}$. - Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leave open the question of its complexity in graphs.

Related papers

• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  This article presents a novel and succinct algorithmic framework via alternating quantum walks. It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs. The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
  arXiv  Detail & Related papers  (2024-07-01T06:09:19Z)
• Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
  We show that perfect non-signalling strategies collapse communication complexity under favorable conditions. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies.
  arXiv  Detail & Related papers  (2024-06-04T10:53:16Z)
• M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clustering [57.947071423091415]
  We introduce Minorize-Maximization Matching and Clustering (M3C), a learning-free algorithm that guarantees theoretical convergence. We develop UM3C, an unsupervised model that incorporates novel edge-wise affinity learning and pseudo label selection. Our method outperforms state-of-the-art graph matching and mixture graph matching and clustering approaches in both accuracy and efficiency.
  arXiv  Detail & Related papers  (2023-10-27T19:40:34Z)
• On the Equivalence of Graph Convolution and Mixup [70.0121263465133]
  This paper investigates the relationship between graph convolution and Mixup techniques. Under two mild conditions, graph convolution can be viewed as a specialized form of Mixup. We establish this equivalence mathematically by demonstrating that graph convolution networks (GCN) and simplified graph convolution (SGC) can be expressed as a form of Mixup.
  arXiv  Detail & Related papers  (2023-09-29T23:09:54Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• Learning Universe Model for Partial Matching Networks over Multiple Graphs [78.85255014094223]
  We develop a universe matching scheme for partial matching of two or multiple graphs. The subtle logic for inlier matching and outlier detection can be clearly modeled. This is the first deep learning network that can cope with two-graph matching, multiple-graph matching, online matching, and mixture graph matching simultaneously.
  arXiv  Detail & Related papers  (2022-10-19T08:34:00Z)
• Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
  We study the solution groups of graph incidence games in which the underlying linear system is the incidence system of a two-coloured graph. Arkhipov's theorem states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. We extend Arkhipov's theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization.
  arXiv  Detail & Related papers  (2022-05-10T03:21:38Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Quantum search of matching on signed graphs [0.0]
  We construct a quantum searching model of a signed edge driven by a quantum walk. Under an arbitrary edge coloring which gives a matching on a complete graph, we consider a quantum search of a colored edge from the edge set of a complete graph.
  arXiv  Detail & Related papers  (2020-07-13T09:36:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.