Melanie Jensenworth: Extending the welded tree speedup

Abstract

A welded tree is a graph consisting of two binary trees "welded"
together with a random cycle between the leaves. In 2003, Childs et
al. showed that a quantum walk has an exponential speedup over
classical algorithms when traversing the graph from one root vertex to
the other. I give evidence that related graphs also have an
exponential gap between classical algorithms and the quantum walk.