A quantum walk-based scheme for distributed searching on arbitrary graphs

• URL: http://arxiv.org/abs/2310.10451v2
• Date: Sat, 23 Dec 2023 17:21:48 GMT
• Title: A quantum walk-based scheme for distributed searching on arbitrary graphs
• Authors: Mathieu Roget and Giuseppe Di Molfetta
• Abstract summary: A discrete time quantum walk is known to be the single-particle sector of a quantum cellular automaton. This work introduces a new quantum walk-based searching scheme, designed to search nodes or edges on arbitrary graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A discrete time quantum walk is known to be the single-particle sector of a quantum cellular automaton. Searching in this mathematical framework has interested the community since a long time. However, most results consider spatial search on regular graphs. This work introduces a new quantum walk-based searching scheme, designed to search nodes or edges on arbitrary graphs. As byproduct, such new model allows to generalise quantum cellular automata, usually defined on regular grids, to quantum anonymous networks, allowing a new physics-like mathematical environment for distributed quantum computing.

Related papers

• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• On the quantum simulation of complex networks [0.0]
  Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. We extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse.
  arXiv  Detail & Related papers  (2022-12-12T18:55:31Z)
• 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)
• 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)
• Designing exceptional-point-based graphs yielding topologically guaranteed quantum search [0.0]
  We show how to construct walks with the property that all the eigenvalues of the non-Hermitian survival operator, coalesce to zero. The resulting search is guaranteed to succeed in a bounded time for any initial condition.
  arXiv  Detail & Related papers  (2022-02-08T04:30:24Z)
• Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
  Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
  arXiv  Detail & Related papers  (2021-12-23T17:57:49Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48:00Z)
• 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)
• Compiling single-qubit braiding gate for Fibonacci anyons topological quantum computation [0.0]
  Topological quantum computation is an implementation of a quantum computer in a way that radically reduces decoherence. Topological qubits are encoded in the topological evolution of two-dimensional quasi-particles called anyons.
  arXiv  Detail & Related papers  (2020-08-08T15:34:03Z)
• How fast do quantum walks mix? [0.34410212782758054]
  We find the quantum mixing time of Erd"os-Renyi random networks where each edge exists with probability $p$ independently. Our results could lead to novel insights into the equilibration times of isolated quantum systems defined by random Hamiltonians.
  arXiv  Detail & Related papers  (2020-01-14T10:45:41Z)

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.