Quantum-Assisted Graph Domination Games

• URL: http://arxiv.org/abs/2511.15802v1
• Date: Wed, 19 Nov 2025 19:00:08 GMT
• Title: Quantum-Assisted Graph Domination Games
• Authors: C. Weeks, P. Strange, P. Drmota, J. Quintanilla,
• Abstract summary: We study quantum advantage in the 1-step graph domination game on cycle graphs numerically, analytically and through the use of Noisy intermediate scale quantum (NISQ) processors.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study quantum advantage in the 1-step graph domination game on cycle graphs numerically, analytically and through the use of Noisy intermediate scale quantum (NISQ) processors. We find explicit strategies that realise the recently found upper bounds for small graphs and generalise them to larger cycles. We demonstrate that NISQ computers realise the predicted quantum advantages with high accuracy.

Related papers

• Quantum Graph Attention Networks: Trainable Quantum Encoders for Inductive Graph Learning [0.6999740786886536]
  We introduce Quantum Graph Attention Networks (QGATs) as trainable quantum encoders for inductive learning on graphs.<n>QGATs leverage parameterized quantum circuits to encode node features and neighborhood structures.<n>We evaluate our approach on the QM9 dataset, targeting the prediction of various chemical properties.
  arXiv  Detail & Related papers  (2025-09-14T18:56:05Z)
• 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)
• Discrete-Time Quantum Walks: A Quantum Advantage for Graph Representation [0.0]
  The paper adeptly maps intricate graph topologies into the Hilbert space, which significantly enhances the efficacy of graph analysis. This development promises to revolutionize the intersection of quantum computing and graph theory.
  arXiv  Detail & Related papers  (2024-07-16T11:49:49Z)
• Quantum-assisted Rendezvous on Graphs: Explicit Algorithms and Quantum Computer Simulations [0.0]
  We study quantum advantage in one-step rendezvous games on simple graphs analytically, numerically, and using noisy intermediate-scale quantum (NISQ) processors.
  arXiv  Detail & Related papers  (2024-05-23T18:01:02Z)
• 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)
• 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)
• Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach [47.19265172105025]
  We propose a novel hybrid quantum-classical algorithm for graph-structured data, which we refer to as the Ego-graph based Quantum Graph Neural Network (egoQGNN) egoQGNN implements the GNN theoretical framework using the tensor product and unity matrix representation, which greatly reduces the number of model parameters required. The architecture is based on a novel mapping from real-world data to Hilbert space.
  arXiv  Detail & Related papers  (2022-01-13T16:35:45Z)
• 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)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• 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)

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.