On the Quantum Chromatic Numbers of Small Graphs
- URL: http://arxiv.org/abs/2311.08194v1
- Date: Tue, 14 Nov 2023 14:27:03 GMT
- Title: On the Quantum Chromatic Numbers of Small Graphs
- Authors: Olivier Lalonde
- Abstract summary: We give the smallest known example of a separation between the parameters $chi(1)_q$ and $chi(2)_q$.
In addition, $G_21$ provides the first provable separation between the parameters $chi(1)_q$ and $chi(2)_q$.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We make two contributions pertaining to the study of the quantum chromatic
numbers of small graphs. Firstly, in an elegant paper, Man\v{c}inska and
Roberson [\textit{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\v{c}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.
Related papers
- Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem.
We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph.
Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
arXiv Detail & Related papers (2023-04-17T10:38:08Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights.
We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs.
Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
arXiv Detail & Related papers (2022-08-18T09:19:01Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann.
We show how our results have immediate applications to the modern theory of polarization.
arXiv Detail & Related papers (2022-05-30T18:01:34Z) - Repeated Averages on Graphs [2.363388546004777]
We prove that $frac(1-epsilon)2log2nlog n-O(n)$ is a general lower bound for all connected graphs on $n$ nodes.
We also get sharp magnitude of $t_epsilon,1$ for several important families of graphs, including star, expander, dumbbell, and cycle.
arXiv Detail & Related papers (2022-05-09T20:18:31Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
This paper studies the problem of matching two complete graphs with edge weights correlated through latent geometries.
We derive an approximate maximum likelihood estimator, which provably achieves, with high probability, perfect recovery of $pi*$.
As a side discovery, we show that the celebrated spectral algorithm of [Ume88] emerges as a further approximation to the maximum likelihood in the geometric model.
arXiv Detail & Related papers (2022-02-22T04:14:45Z) - Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice
Gauge Theory [9.83302372715731]
The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem.
We present an approach in terms of $mathbbZ$ lattice gauge theory defined on the lattice with the graph as its dual.
For some random samples of small graphs, we demonstrate that the dependence of the average value of $g_c$ on $sqrtN_hc$, $N_hc$ being the number of HCs, and that of the average value of $frac1g_c$ on $N
arXiv Detail & Related papers (2022-02-17T18:39:42Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs)
A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data.
We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
arXiv Detail & Related papers (2021-11-12T07:08:13Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
An $soperatorname-t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects $s$ and $t$.
In this work we describe a quantum algorithm for the minimum $soperatorname-t$ cut problem on undirected graphs.
arXiv Detail & Related papers (2021-10-29T07:35:46Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs.
It can be viewed as a noisy average-case version of the graph isomorphism problem.
arXiv Detail & Related papers (2021-10-11T05:07:50Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
We consider a structural assumption on the graph Laplacian matrix $L$.
The first $K$ eigenvectors of $L$ are pre-selected, e.g., based on domain-specific criteria.
We design an efficient hybrid graphical lasso/projection algorithm to compute the most suitable graph Laplacian matrix $L* in H_u+$ given $barC$.
arXiv Detail & Related papers (2020-10-25T18:12:50Z)
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.