# Exponential speedups for quantum walks in random hierarchical graphs

**Authors:** Shankar Balasubramanian, Tongyang Li, Aram Harrow  
**arXiv:** [2307.15062](https://arxiv.org/abs/2307.15062)  
**Date:** 2023-07-27  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2307.15062v1/

## Key points

- Authors explore exponential speedups in quantum algorithms through quantum walks on hierarchical graphs
- Generalizing application of quantum walks to a broader class of hierarchical graphs beyond welded-tree structures
- Introducing supervertices with varying sizes and random connections to improve traversal times
- Hitting times of quantum walks linked to localization properties of zero modes in disordered tight binding Hamiltonians
- Providing concrete examples of hierarchical graph realizations and proposing efficient traversal graph construction method using graph sparsification techniques
- Speedups achieved can range from superpolynomial to exponential based on dimensionality and randomness model of the graph

## Summary

In their paper titled "Exponential speedups for quantum walks in random hierarchical graphs," authors Shankar Balasubramanian, Tongyang Li, and Aram Harrow explore the potential for exponential speedups in quantum algorithms through the use of quantum walks on hierarchical graphs. This approach builds upon previous work by Childs et al. on using quantum walks to traverse welded-tree graphs. The key innovation of this study lies in generalizing the application of quantum walks to a broader class of hierarchical graphs beyond just welded-tree structures. By introducing supervertices with varying sizes and random connections between them, the authors demonstrate how quantum traversal times can be significantly improved compared to classical algorithms. The hitting times of quantum walks on these hierarchical graphs are shown to be closely linked to the localization properties of zero modes in disordered tight binding Hamiltonians. Moreover, the authors provide concrete examples of hierarchical graph realizations and propose a novel method for constructing efficient traversal graphs using graph sparsification techniques. Through their analysis, they showcase that the speedups achieved can range from superpolynomial to exponential, depending on the underlying dimensionality and randomness model of the graph. Overall, this research sheds light on new possibilities for leveraging quantum walks on hierarchical graphs to achieve significant computational advantages over classical algorithms. The findings not only contribute to advancing our understanding of quantum algorithm design but also offer practical insights into optimizing traversal times in complex network structures.