{"id":"arxiv/2609.20651","url":"https://arxiv.org/abs/2609.20651","tags":["quant-ph","cs.CC"],"score":0,"title":"Hardness of Pathfinding in a Welded Tree","domain":"quant-ph","source":"arxiv","authors":["David Miloschewsky","Supartha Podder"],"reviews":0,"subject":"quant-ph","summary":"Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}