The Signal

Stony Brook Proves Quantum Algorithms Need Exponential Queries for Welded-Tree Paths

A Stony Brook proof shows that quantum algorithms need at least Ω(2^(n/24)) queries to find a path through a welded tree of height n, even though a quantum walk can find the exit exponentially faster than classical algorithms. A second proo

Quantum.world Team · Written with AI · fact-checked · 2026-10-23

For a welded tree of height n, any quantum algorithm needs at least Ω(2^n/24) queries to produce an entrance-to-exit path with constant probability, according to a proof by Stony Brook University researchers. The result concerns queries to a mathematical graph oracle, not the runtime of a physical quantum computer. It resolves a long-standing question about a problem where a quantum walk can locate the exit exponentially faster than classical algorithms, yet finding and reporting a route appears far harder.

A 2^n/24 Query Floor

The graph consists of two binary trees joined at their leaves by alternating edges that form a central weld. The roots serve as entrance and exit. An algorithm begins with the entrance’s label and learns about the graph by querying an oracle for neighboring labels; the vertices receive random labels, so the labels themselves do not reveal their positions in the maze.

David Miloschewsky, a Stony Brook computer science graduate student, and Supartha Podder, an assistant professor in the department, posted their preprint on September 17, 2026. The authors state the result in the abstract: “We answer this by proving an exponential quantum query lower bound for finding such path.”

We answer this by proving an exponential quantum query lower bound for finding such path.

David Miloschewsky and Supartha Podder, authors of “Hardness of Pathfinding in a Welded Tree”

The bound is exponential in tree height, but its precise meaning is tied to the paper’s oracle model and graph-instance distribution. The authors note that their model and distribution resemble those used in earlier welded-tree work but are not identical. The theorem is a lower bound on the number of oracle queries; it does not say that quantum computers cannot find the exit.

Finding the Exit Is Not Finding the Route

The distinction matters because a quantum walk can exploit interference among many possible routes to identify the exit without leaving a classical travel log. A classical search can record the sequence of junctions it visits and retrace those steps after reaching the destination. For a quantum algorithm, retaining route information can interfere with the behavior that makes the walk effective.

Earlier results left open whether a different quantum strategy could avoid that trade-off: explore parts of the graph, discard some connections from memory, and later assemble a complete path. Miloschewsky and Podder remove restrictions imposed in a 2023 analysis, according to Stony Brook’s account. Their lower bound applies even when an algorithm can forget how a portion of its explored graph connects back toward the entrance.

A Ledger for What the Algorithm Forgets

The proof uses a compressed permutation oracle, a technique for tracking how an algorithm interacts with a graph whose labels are hidden. The researchers model that information in a “quantum ledger” that follows what the algorithm has learned and what it has erased from memory. Their analysis shows why independently explored sections of the graph are unlikely to connect across its large middle region quickly enough to form an entrance-to-exit path.

The argument addresses more than the familiar observation that recording a quantum walk’s route can spoil interference. It seeks to rule out efficient path-finding by any quantum algorithm in the stated model, including approaches that do not simply record the walk step by step. That broader claim is what turns a limitation of one algorithm into a query lower bound for the full class being studied.

A Second Proof Sets Up the Exponent Question

A separate group posted another proof on September 22, five days after the Stony Brook preprint. Joseph Carolan, Andrew M. Childs, Matthew Coudron and Amin Shiraz Gilani report a lower bound of Ω(2^n/12) queries for height-n graphs with independently matched welded trees. The two papers establish exponential lower bounds in their respective settings; their exponents should not be treated as a direct comparison without accounting for the models and graph distributions.

Stony Brook reports that the two groups are now working together to determine the optimal bound. That shared target is the remaining concrete measure of how much query effort welded-tree path-finding requires: the strongest lower bound that holds under a common formulation of the problem.