Quantum-assisted Rendezvous on Graphs: Explicit Algorithms and Quantum Computer Simulations

• URL: http://arxiv.org/abs/2405.14951v3
• Date: Wed, 24 Jul 2024 13:17:30 GMT
• Title: Quantum-assisted Rendezvous on Graphs: Explicit Algorithms and Quantum Computer Simulations
• Authors: J. Tucker, P. Strange, P. Mironowicz, J. Quintanilla,
• Abstract summary: We study quantum advantage in one-step rendezvous games on simple graphs analytically, numerically, and using noisy intermediate-scale quantum (NISQ) processors.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study quantum advantage in one-step rendezvous games on simple graphs analytically, numerically, and using noisy intermediate-scale quantum (NISQ) processors. Our protocols realise the recently discovered [arXiv:2207.14404] optimal bounds for small cycle graphs and cubic graphs. In the case of cycle graphs, we generalise the protocols to arbitrary graph size. The NISQ processor experiments realise the expected quantum advantage with high accuracy for rendezvous on the complete graph K3. In contrast, for the graph 2K4, formed by two disconnected 4-vertex complete graphs, the performance of the NISQ hardware is sub-classical, consistent with the deeper circuit and known qubit decoherence and gate error rates.

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)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Graph Transformers for Large Graphs [57.19338459218758]
  This work advances representation learning on single large-scale graphs with a focus on identifying model characteristics and critical design constraints. A key innovation of this work lies in the creation of a fast neighborhood sampling technique coupled with a local attention mechanism. We report a 3x speedup and 16.8% performance gain on ogbn-products and snap-patents, while we also scale LargeGT on ogbn-100M with a 5.9% performance improvement.
  arXiv  Detail & Related papers  (2023-12-18T11:19:23Z)
• Implementation of Continuous-Time Quantum Walks on Quantum Computers [0.0]
  Quantum walks are interesting candidates to be implemented on quantum computers. We describe efficient circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms on three graph classes.
  arXiv  Detail & Related papers  (2022-12-17T14:59:21Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• 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)
• Q2Graph: a modelling tool for measurement-based quantum computing [0.0]
  The quantum circuit model is the default for encoding an algorithm intended for a NISQ computer or a quantum computing simulator. A graph representation is well-suited for algorithms intended for a quantum computing facility founded on measurement-based quantum computing (MBQC) principles. We submit Q2Graph, a software package for designing and testing of simple graphs as algorithms for quantum computing facilities.
  arXiv  Detail & Related papers  (2022-10-03T00:12:44Z)
• 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)
• Simplifying Continuous-Time Quantum Walks on Dynamic Graphs [0.0]
  A continuous-time quantum walk on a dynamic graph evolves by Schr"odinger's equation with a sequence of Hamiltonians encoding the edges of the graph. In this paper, we give six scenarios under which a dynamic graph can be simplified.
  arXiv  Detail & Related papers  (2021-06-10T19:24:32Z)
• 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)

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.