Spectral bounds for the quantum chromatic number of quantum graphs

• URL: http://arxiv.org/abs/2112.01726v1
• Date: Fri, 3 Dec 2021 05:36:21 GMT
• Title: Spectral bounds for the quantum chromatic number of quantum graphs
• Authors: Priyanga Ganesan
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum graphs are an operator space generalization of classical graphs that have emerged in different branches of mathematics including operator theory, non-commutative topology and quantum information theory. In this paper, we obtain lower bounds for the classical and quantum chromatic number of a quantum graph using eigenvalues of the quantum adjacency matrix. In particular, we prove a quantum generalization of Hoffman's bound and introduce quantum analogues for the edge number, Laplacian and signless Laplacian. We generalize all the spectral bounds given by Elphick and Wocjan (2019) to the quantum graph setting and demonstrate the tightness of these bounds in the case of complete quantum graphs. Our results are achieved using techniques from linear algebra and a combinatorial definition of quantum graph coloring, which is obtained from the winning strategies of a quantum-to-classical nonlocal graph coloring game, given by M. Brannan, P. Ganesan and S. Harris (2020).

Related papers

• How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing [0.2184775414778289]
  We show that advantages in space complexity are possible for quantum algorithms over their classical counterparts in the streaming model. We give a simple quantum sketch that encompasses all these results, allowing them to be derived from entirely classical algorithms using our quantum sketch as a black box.
  arXiv  Detail & Related papers  (2024-10-24T17:11:37Z)
• Quantum Games and Synchronicity [0.0]
  We extend nonlocal games to allow quantum questions and answers. Equations are presented using a diagrammatic calculus for tensor categories. We extend the standard definitions, including strategies, correlations, and synchronicity.
  arXiv  Detail & Related papers  (2024-08-27T23:27:59Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  We establish a continuity relation between the topological space of quantum channels and the quotient of the complex Stiefel manifold. The established relation can be applied to various quantum optimization problems.
  arXiv  Detail & Related papers  (2024-08-19T09:15:54Z)
• Extreme quantum states and processes, and extreme points of general spectrahedra in finite dimensional algebras [0.27195102129094995]
  Convex sets of quantum states and processes play a central role in quantum theory and quantum information. Many important examples of convex sets in quantum theory are spectrahedra, that is, sets of positive operators subject to affine constraints. This contribution provides a characterisation of the extreme points of general spectrahedra, and bounds on the ranks of the corresponding operators.
  arXiv  Detail & Related papers  (2023-11-18T01:31:16Z)
• Algebraic Geometry of Quantum Graphical Models [0.0]
  We introduce the foundations to carry out a similar study of quantum counterparts. quantum graphical models are families of quantum states satisfying certain locality or correlation conditions encoded by a graph.
  arXiv  Detail & Related papers  (2023-08-22T16:07:07Z)
• Quantivine: A Visualization Approach for Large-scale Quantum Circuit Representation and Analysis [31.203764035373677]
  We develop Quantivine, an interactive system for exploring and understanding quantum circuits. A series of novel circuit visualizations are designed to uncover contextual details such as qubit provenance, parallelism, and entanglement. The effectiveness of Quantivine is demonstrated through two usage scenarios of quantum circuits with up to 100 qubits.
  arXiv  Detail & Related papers  (2023-07-18T04:51:28Z)
• A vertical gate-defined double quantum dot in a strained germanium double quantum well [48.7576911714538]
  Gate-defined quantum dots in silicon-germanium heterostructures have become a compelling platform for quantum computation and simulation. We demonstrate the operation of a gate-defined vertical double quantum dot in a strained germanium double quantum well. We discuss challenges and opportunities and outline potential applications in quantum computing and quantum simulation.
  arXiv  Detail & Related papers  (2023-05-23T13:42:36Z)
• 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)
• Stochastic emulation of quantum algorithms [0.0]
  We introduce higher-order partial derivatives of a probability distribution of particle positions as a new object that shares basic properties of quantum mechanical states needed for a quantum algorithm. We prove that the propagation via the map built from those universal maps reproduces up to a prefactor exactly the evolution of the quantum mechanical state. We implement several well-known quantum algorithms, analyse the scaling of the needed number of realizations with the number of qubits, and highlight the role of destructive interference for the cost of emulation.
  arXiv  Detail & Related papers  (2021-09-16T07:54:31Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• Spectra of Perfect State Transfer Hamiltonians on Fractal-Like Graphs [62.997667081978825]
  We study the spectral features, on fractal-like graphs, of Hamiltonians which exhibit the special property of perfect quantum state transfer. The essential goal is to develop the theoretical framework for understanding the interplay between perfect quantum state transfer, spectral properties, and the geometry of the underlying graph.
  arXiv  Detail & Related papers  (2020-03-25T02:46:14Z)

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.