Quantum Graph Theory by Example

• URL: http://arxiv.org/abs/2603.23651v1
• Date: Tue, 24 Mar 2026 18:51:14 GMT
• Title: Quantum Graph Theory by Example
• Abstract summary: We present a collection of non-trivial quantum graphs that can be thought of in discrete terms.<n>The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups.<n>We give exact formulas or establish bounds for quantum graph parameters.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices $(A, B, C)$. The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: $A$ and $C$ are described by a classical weighted graph called the strange graph, while $B$ provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.

Related papers

• An Introduction to Quantum Graphs and Current Applications [0.0]
  We give a didactical introduction to quantum graphs, or Schrdinger Hamiltonians on metric graphs.<n>We focus on results related to quantum chaos, periodic theory and spectral theory.
  arXiv  Detail & Related papers  (2026-04-14T13:00:51Z)
• Properties of multiqubit variational quantum states representing weighted graphs and their computing with quantum programming [0.0]
  We study multiqubit variational quantum states that can be considered as weighted quantum graph states.<n>We derive the geometric measure of entanglement and evaluate quantum correlators.
  arXiv  Detail & Related papers  (2026-04-01T14:33:09Z)
• High-dimensional graphs convolution for quantum walks photonic applications [41.94295877935867]
  We suggest a new method for lattices and hypercycle convolution that preserves quantum walk dynamics.<n>Our findings may be useful for saving a significant number of qubits required for algorithms that use quantum walk simulation on quantum devices.
  arXiv  Detail & Related papers  (2025-07-21T18:28:34Z)
• Solving graph problems using permutation-invariant quantum machine learning [35.99391901074448]
  In quantum machine learning, the ansatz can be tuned to correspond to the specific symmetry of the problem.<n>We show how the symmetry can be included in the quantum circuit in a straightforward constructive method.
  arXiv  Detail & Related papers  (2025-05-19T06:44:03Z)
• QGHNN: A quantum graph Hamiltonian neural network [30.632260870411177]
  Graph Neural Networks (GNNs) strive to address the challenges posed by complex, high-dimensional graph data.<n>Quantum Neural Networks (QNNs) present a compelling alternative due to their potential for quantum parallelism.<n>This paper introduces a quantum graph Hamiltonian neural network (QGHNN) to enhance graph representation and learning on noisy intermediate-scale quantum computers.
  arXiv  Detail & Related papers  (2025-01-14T10:15:17Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  We introduce and study the clique problem for quantum graphs.<n>Our approach utilizes a well-known connection between quantum graphs and quantum channels.<n>We show that, quantified over all channels, this problem is complete for QMA(2).<n>We also give a new proof of the celebrated reduction of QMA(k) to QMA(2).
  arXiv  Detail & Related papers  (2023-09-22T14:20:14Z)
• 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)
• Application of graph theory in quantum computer science [0.0]
  We demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. The quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
  arXiv  Detail & Related papers  (2021-09-27T12:07:25Z)
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios [37.067444579637076]
  Quantum self-testing is the task of certifying quantum states and measurements using the output statistics solely. We present a new approach for quantum self-testing in Bell non-locality scenarios.
  arXiv  Detail & Related papers  (2021-04-27T08:15:01Z)
• 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)
• 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.