Multiparticle quantum walks for distinguishing hard graphs

• URL: http://arxiv.org/abs/2501.03683v1
• Date: Tue, 07 Jan 2025 10:30:40 GMT
• Title: Multiparticle quantum walks for distinguishing hard graphs
• Authors: Sachin Kasture, Shaheen Acheche, Loic Henriet, Louis-Paul Henry,
• Abstract summary: In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs.
• Score: 0.0
• License:
• Abstract: Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).

Related papers

• Chordal Graphs and Distinguishability of Quantum Product States [0.0]
  We identify chordality as the key graph structure that drives distinguishability in one-way LOCC. We derive a one-way LOCC characterization for chordal graphs that establishes a connection with the theory of matrix completions.
  arXiv  Detail & Related papers  (2023-05-17T12:17:47Z)
• QESK: Quantum-based Entropic Subtree Kernels for Graph Classification [11.51839867040302]
  We propose a novel graph kernel, namely the Quantum-based Entropic Subtree Kernel (QESK) for Graph Classification. We show how this AMM matrix can be employed to compute a series of entropic subtree representations associated with the classical Weisfeiler-Lehman (WL) algorithm. We show that the proposed QESK kernel can significantly outperform state-of-the-art graph kernels and graph deep learning methods for graph classification problems.
  arXiv  Detail & Related papers  (2022-12-10T07:10:03Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  We propose quantum graph convolutional networks (QuanGCN), which learns the local message passing among nodes with the sequence of crossing-gate quantum operations. To mitigate the inherent noises from modern quantum devices, we apply sparse constraint to sparsify the nodes' connections. Our QuanGCN is functionally comparable or even superior than the classical algorithms on several benchmark graph datasets.
  arXiv  Detail & Related papers  (2022-11-09T21:43:16Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Discrete Quantum Walks on the Symmetric Group [0.0]
  In quantum walks, the propagation is governed by quantum mechanical rules; generalizing random walks to the quantum setting. In this paper we investigate the discrete time coined quantum walk (DTCQW) model using tools from non-commutative Fourier analysis. Specifically, we are interested in characterizing the DTCQW on Cayley graphs generated by the symmetric group ($sym$) with appropriate generating sets.
  arXiv  Detail & Related papers  (2022-03-28T23:48:08Z)
• 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)
• Equivariant Quantum Graph Circuits [10.312968200748116]
  We propose equivariant quantum graph circuits (EQGCs) as a class of parameterized quantum circuits with strong inductive bias for learning over graph-structured data. Our theoretical perspective on quantum graph machine learning methods opens many directions for further work, and could lead to models with capabilities beyond those of classical approaches.
  arXiv  Detail & Related papers  (2021-12-10T00:14:12Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Facial Expression Recognition on a Quantum Computer [68.8204255655161]
  We show a possible solution to facial expression recognition using a quantum machine learning approach. We define a quantum circuit that manipulates the graphs adjacency matrices encoded into the amplitudes of some appropriately defined quantum states.
  arXiv  Detail & Related papers  (2021-02-09T13:48:00Z)
• Graph Coloring with Quantum Annealing [0.0]
  We develop a graph coloring approximation algorithm that uses the D-Wave 2X as an independent set sampler. A randomly generated set of small but hard graph instances serves as our test set. Our performance analysis suggests limited quantum advantage in the hybrid quantum-classical algorithm.
  arXiv  Detail & Related papers  (2020-12-08T15:08:22Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs) first augments node features with certain multi-hop operators on the graph. We prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth.
  arXiv  Detail & Related papers  (2020-10-28T17:59:59Z)

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.