Exponential speedups for quantum walks in random hierarchical graphs

• URL: http://arxiv.org/abs/2307.15062v2
• Date: Fri, 2 Aug 2024 17:27:42 GMT
• Title: Exponential speedups for quantum walks in random hierarchical graphs
• Authors: Shankar Balasubramanian, Tongyang Li, Aram Harrow,
• Abstract summary: 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.
• Score: 8.984888893275713
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There are few known exponential speedups for quantum algorithms and these tend to fall into even fewer families. One speedup that has mostly resisted generalization is the use of quantum walks to traverse the welded-tree graph, due to Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman. We show how to generalize this to a large class of hierarchical graphs in which the vertices are grouped into "supervertices" which are arranged according to a $d$-dimensional lattice. Supervertices can have different sizes, and edges between supervertices correspond to random connections between their constituent vertices. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians. The speedups range from superpolynomial to exponential, depending on the underlying dimension and the random graph model. We also provide concrete realizations of these hierarchical graphs, and introduce a general method for constructing graphs with efficient quantum traversal times using graph sparsification.

Related papers

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs) We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN. The most important observation is that the generalization capability can be realized with one large graph instead of being limited to the size of the graph as in previous results.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs [5.173438526554426]
  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.
  arXiv  Detail & Related papers  (2024-07-19T15:21:13Z)
• 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)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• A convergence time of Grover walk on regular graph to stationary state [0.0]
  We consider a quantum walk model on a finite graph which has an interaction with the outside. We show that larger degree of the regular graph makes the convergence speed of this quantum walk model slower.
  arXiv  Detail & Related papers  (2022-10-16T02:57:33Z)
• 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)
• Search by Lackadaisical Quantum Walk with Symmetry Breaking [0.0]
  The lackadaisical quantum walk is a lazy version of a discrete-time, coined quantum walk. They have been used to speed up spatial search on a variety of graphs.
  arXiv  Detail & Related papers  (2021-08-31T14:08:40Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGAT is a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks.
  arXiv  Detail & Related papers  (2020-06-15T22:07:54Z)
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
  The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph. It can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. We present a number of numerical simulations supporting this hypothesis.
  arXiv  Detail & Related papers  (2020-02-26T00:10:38Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42: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.