Quantum speedups related to the welded-trees problem


Shankar Balasubramanian March 31, 2023.


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 mapped 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.

This is work joint with Tongyang Li and Aram Harrow.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Brooks' Theorem in Graph Streams, A Single-Pass Semi-Streaming Algorithm for Δ-Coloring
  • Are quantum speedups for learning expressive classes possible?
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • Derandomization from Time-Space Tradeoffs
  • Foundations of Lattice-based Cryptography