{"id":"arxiv/2609.26712","url":"https://arxiv.org/abs/2609.26712","tags":["quant-ph"],"score":0,"title":"A quantum lower bound for path finding in welded trees","domain":"quant-ph","source":"arxiv","authors":["Joseph Carolan","Andrew M. Childs","Matthew Coudron","Amin Shiraz Gilani"],"reviews":0,"subject":"quant-ph","summary":"In the welded tree problem, an algorithm is tasked with navigating a graph formed from two binary trees joined at the leaves through a ``weld'' of connecting edges. A quantum walk can navigate from root to root exponentially faster than any classical algorithm. However, known efficient quantum algorithms cannot find a path between the roots, as recording the path destroys constructive interference and thus the speedup. We prove that this is inherent: any quantum algorithm needs exponentially many queries to find a path between the roots of an independently matched welded tree graph. This…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-22","reactions":{}}