Related papers: The exact quantum chromatic number of Hadamard graphs

The exact quantum chromatic number of Hadamard graphs

URL: http://arxiv.org/abs/2410.00042v2
Date: Mon, 14 Oct 2024 17:56:04 GMT
Title: The exact quantum chromatic number of Hadamard graphs
Authors: Meenakshi McNamara,
Abstract summary: We compute the quantum chromatic numbers of Hadamard graphs of order $n=2N$ for $N$ a multiple of $4$. We also compute the exact quantum chromatic number of the categorical product of Hadamard graphs.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We compute the exact value of the quantum chromatic numbers of Hadamard graphs of order $n=2^N$ for $N$ a multiple of $4$ using the upper bound derived by Avis, Hasegawa, Kikuchi, and Sasaki, as well as an application of the Hoffman-like lower bound of Elphick and Wocjan that was generalized by Ganesan for quantum graphs. As opposed to prior computations for the lower bound, our approach uses Ito's results on conjugacy class graphs allowing us to also find bounds on the quantum chromatic numbers of products of Hadamard graphs. In particular, we also compute the exact quantum chromatic number of the categorical product of Hadamard graphs.

Related papers

Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs [26.8902894372334]
In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs.
arXiv Detail & Related papers (2024-10-06T08:57:30Z)
Quantum Counting on the Complete Bipartite Graph [0.0]
Quantum counting is a key quantum algorithm that aims to determine the number of marked elements in a database. Since Grover's algorithm can be viewed as a quantum walk on a complete graph, a natural way to extend quantum counting is to use the evolution operator of quantum-walk-based search on non-complete graphs.
arXiv Detail & Related papers (2023-11-17T09:22:28Z)
Quantum tomography of helicity states for general scattering processes [55.2480439325792]
Quantum tomography has become an indispensable tool in order to compute the density matrix $rho$ of quantum systems in Physics. We present the theoretical framework for reconstructing the helicity quantum initial state of a general scattering process.
arXiv Detail & Related papers (2023-10-16T21:23:42Z)
Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
We take a perspective of taking limits of operators derived from graphs, such as the aggregation operation that makes up GNNs. Our results hold for dense and sparse graphs, and various notions of graph limits.
arXiv Detail & Related papers (2023-06-07T15:04:58Z)
From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
arXiv Detail & Related papers (2022-02-19T02:56:47Z)
Spectral bounds for the quantum chromatic number of quantum graphs [0.0]
We obtain lower bounds for the classical and quantum number of a quantum graph using eigenvalues of the quantum adjacency matrix. We generalize all the spectral bounds given by Elphick and Wocjan to the quantum graph setting. Our results are achieved using techniques from linear algebra and a complete definition of quantum graph coloring.
arXiv Detail & Related papers (2021-12-03T05:36:21Z)
Average-case Speedup for Product Formulas [69.68937033275746]
Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
arXiv Detail & Related papers (2021-11-09T18:49:48Z)
Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z)
How to Teach a Quantum Computer a Probability Distribution [0.0]
We explore teaching a coined discrete time quantum walk on a regular graph a probability distribution. We also discuss some hardware and software concerns as well as immediate applications and the several connections to machine learning.
arXiv Detail & Related papers (2021-04-15T02:41:27Z)
High-Dimensional Gaussian Process Inference with Derivatives [90.8033626920884]
We show that in the low-data regime $ND$, the Gram matrix can be decomposed in a manner that reduces the cost of inference to $mathcalO(N2D + (N2)3)$. We demonstrate this potential in a variety of tasks relevant for machine learning, such as optimization and Hamiltonian Monte Carlo with predictive gradients.
arXiv Detail & Related papers (2021-02-15T13:24:41Z)
Complex Hadamard Diagonalisable Graphs [0.0]
We show that a large class of complex Hadamard diagonalisable graphs have sets forming an equitable partition. We provide examples and constructions of complex Hadamard diagonalisable graphs. We discuss necessary and sufficient conditions for $(alpha, beta)$--Laplacian fractional revival and perfect state transfer.
arXiv Detail & Related papers (2020-01-01T17:49:25Z)

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