Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs

• URL: http://arxiv.org/abs/2407.14398v1
• Date: Fri, 19 Jul 2024 15:21:13 GMT
• Title: Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
• Authors: Jianqiang Li, Yu Tong,
• Abstract summary: We find a class of graphs that allows exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle. We provide an efficient quantum algorithm to find an $s$-$t$ path in the regular sunflower graph while any classical algorithm takes exponential time.
• Score: 5.173438526554426
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding problems that allow for superpolynomial quantum speedup is one of the most important tasks in quantum computation. A key challenge is identifying problem structures that can only be exploited by quantum mechanics. In this paper, we find a class of graphs that allows for exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle, and this class of graphs is named regular sunflower graphs. We prove that, with high probability, a regular sunflower graph of degree at least $7$ is a mild expander graph, that is, the spectral gap of the graph Laplacian is at least inverse polylogarithmic in the graph size. We provide an efficient quantum algorithm to find an $s$-$t$ path in the regular sunflower graph while any classical algorithm takes exponential time. This quantum advantage is achieved by efficiently preparing a $0$-eigenstate of the adjacency matrix of the regular sunflower graph as a quantum superposition state over the vertices, and this quantum state contains enough information to help us efficiently find an $s$-$t$ path in the regular sunflower graph. Because the security of an isogeny-based cryptosystem depends on the hardness of finding an $s$-$t$ path in an expander graph \cite{Charles2009}, a quantum speedup of the pathfinding problem on an expander graph is of significance. Our result represents a step towards this goal as the first provable exponential speedup for pathfinding in a mild expander graph.

Related papers

• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
  arXiv  Detail & Related papers  (2024-04-30T11:45:49Z)
• Exponential speedups for quantum walks in random hierarchical graphs [8.984888893275713]
  We show how to generalize the use of quantum walks to a class of hierarchical graphs. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians.
  arXiv  Detail & Related papers  (2023-07-27T17:59:58Z)
• Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
  Given $s, t$ in an unweighted undirected graph $G$, the goal of the pathfinding problem is to find an $s$-$t$ path. We construct a graph $G$ based on welded trees and define a pathfinding problem in the adjacency list oracle $O$. We prove that no classical algorithm can find an $s$-$t$ path in subexponential time with high probability.
  arXiv  Detail & Related papers  (2023-07-24T02:50:34Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• 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)
• 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)
• Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
  We show that spatial search on Johnson graphs by continuous-time quantum walk achieves the lower bound $pisqrtN/2$ with success probability $1$ally for every fixed diameter. The proof is mathematically rigorous and can be used for other graph classes.
  arXiv  Detail & Related papers  (2021-08-04T12:16:24Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• (Sub)Exponential advantage of adiabatic quantum computation with no sign problem [0.0]
  We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph.
  arXiv  Detail & Related papers  (2020-11-18T19:04:51Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)

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.