11-25
Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard

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 provides an example of a problem that a quantum computer can solve exponentially faster than any classical algorithm by exploring exponentially many paths in superposition, but where it is provably intractable to find any such path. The proof uses compressed permutation oracles to record the progress of a quantum algorithm as it queries the graph, where we show that the compressed database remains path-free up to a small error.

Date and Time
Wednesday November 25, 2026 2:00pm - 3:00pm
Location
Computer Science Small Auditorium (Room 105)
Speaker
Joseph Carolan, from University of Maryland

Contributions to and/or sponsorship of any event does not constitute departmental or institutional endorsement of the specific program, speakers or views presented.

CS Talks Mailing List