Event Details:
Location
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 a d-dimensional lattice of "supervertices". 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 is 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.
Related Topics
Explore More Events
-
Q-FARM Seminar
Jordan Docter and Michelle Xu [Stanford University]
-Physics and Astrophysics Building
452 LOMITA MALL
PAB 102/103
Stanford, CA 94305
United States -
Q-FARM Seminar
Nikolas Breuckmann [University of Bristol, England]
-Physics and Astrophysics Building
452 LOMITA MALL
PAB 102/103
Stanford, CA 94305
United States -
Q-FARM Seminar
Charles Brown [Yale University]
-Physics and Astrophysics Building
452 LOMITA MALL
PAB 102/103
Stanford, CA 94305
United States