  The so-called welded tree problem provides an example of a black-box problem
that can be solved exponentially faster by a quantum walk than by any classical
algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find
another distinguished EXIT vertex using polynomially many queries, though
without finding any particular path from ENTRANCE to EXIT. It has been an open
problem for twenty years whether there is an efficient quantum algorithm for
finding such a path, or if the path-finding problem is hard even for quantum
computers. We show that a natural class of efficient quantum algorithms
provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider
algorithms that, within each branch of their superposition, always store a set
of vertex labels that form a connected subgraph including the ENTRANCE, and
that only provide these vertex labels as inputs to the oracle. While this does
not rule out the possibility of a quantum algorithm that efficiently finds a
path, it is unclear how an algorithm could benefit by deviating from this
behavior. Our no-go result suggests that, for some problems, quantum algorithms
must necessarily forget the path they take to reach a solution in order to
outperform classical computation.
