Quantum algorithms and the power of forgetting
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 (https://arxiv.org/pdf/quant-ph/0209131.pdf). 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.