Finding a path through a maze is hard, even for quantum algorithms.

A quantum traveler has found the exit of a maze but wonders which route brought him there. Conceptual illustration.

A quantum computer can find the exit of a certain kind of maze far faster than a classical computer. But can it also give you directions? David Miloschewsky and Supartha Podder of Stony Brook University's Department of Computer Science have proven that finding a route remains hard for every quantum algorithm in the mathematical model they study.

Imagine entering a maze without a map. At each junction, you can learn which passages connect to it, but you cannot see the layout from above or tell which turns lead toward the exit.

Computer scientists have been studying this problem using mazes called welded trees. Picture two (complete binary) trees whose branches split in two again and again. A tangled loop joins their outermost tips, alternating between the two trees. The base of one tree is the entrance; the base of the other is the exit. Starting from the entrance, the goal is to find the exit.

A small welded-tree maze. Each circle is a junction and each line is a passage. The tangled connections in the middle join the outermost tips of the two trees. Crossing lines are not additional junctions.

In 2003, Andrew Childs and five colleagues showed that a quantum computer could identify the exit exponentially faster than any classical algorithm. As branching layers are added, the work required by a classical computer grows exponentially, while the quantum algorithm's workload grows much more slowly.

The classical computer struggles because the maze offers little guidance. After crossing the tangle in the middle, it typically encounters junctions with one passage leading toward the exit and two leading back toward the tangle. So, it tends to get stuck in the middle layers and finding the exit becomes extremely challenging.

A quantum computer explores the maze using a method called a quantum walk. Its search behaves like a wave spreading through the passages. Like overlapping water ripples, parts of the wave can strengthen or cancel one another in an effect called interference. In this particular maze, the branching pattern helps the wave reach the exit, allowing the quantum computer to find it far faster than a classical computer.

But identifying the exit is different from providing directions. A classical computer can record how it reaches each new junction. Once it finds the exit, it can follow those records backward to produce a route. The quantum walk identifies the exit without supplying such a record. Could another quantum method find a route efficiently? For many years, this question was left open.

Scott Aaronson highlighted this question in his 2021 list of open problems. Proving that every quantum algorithm needs exponential work to find a route, he wrote, would establish "a striking algorithmic version of wave/particle duality."

The analogy comes from the double-slit experiment. Electrons are sent one at a time toward a barrier with two narrow openings. A screen beyond it records each arrival as a dot. Over time, the dots form alternating crowded and nearly empty bands. The wave describing an electron spreads through both openings, and its two parts reinforce or cancel each other, much like overlapping water ripples.

Detectors that reliably record which opening an electron uses remove this interference. Keeping distinct route records likewise changes the interference in a quantum walk. But showing why a travel log disrupts one method does not prove that every possible method for finding a route must be slow.

Electrons arrive one at a time as tiny dots, yet together they form stripes that reveal their wave behavior. When detectors record which slit each electron passes through, the interference is lost and the stripes disappear.

In 2023, Childs, Matthew Coudron and Amin Shiraz Gilani proved that finding a route was hard for quantum algorithms under two restrictions. Every junction an algorithm remembered had to remain connected to the entrance through connections it also remembered. The algorithm also had to treat junction labels as names, using limited operations instead of arbitrary calculations on the bits that make up those names.

Those restrictions left some strategies open. An algorithm might forget how an explored section connected to the entrance, investigate elsewhere, and later piece together a route. Ben Brubaker highlighted this possibility in Quanta Magazine's account of the work. "That is still not ruled out," Childs said at the time.

David Miloschewsky and Supartha Podder. Photo credit: Margaret Yu (Qianxun Yu).

Now Stony Brook computer science graduate student David Miloschewsky and computer science assistant professor Supartha Podder have proven that finding a route requires exponential work for every quantum algorithm in the welded-tree model. Miloschewsky and Podder's new proof removes both restrictions. They proved that to produce any entrance-to-exit route with a reliable chance of success, every quantum algorithm must spend an exponential amount of time inside the maze. Thus, quantum algorithms struggle like any classical algorithms when it comes to path finding, even though identifying the exit is efficient.

Their proof tracks what an algorithm learns and forgets. Building on Joseph Carolan's compressed permutation oracle technique, they use a mathematical "quantum ledger" that accounts for information held in multiple possibilities at once, while recording what information is erased from the algorithm's memory. The proof shows that even though quantum algorithms can figure out separate sections of the graph, those separately explored sections rarely meet in the enormous middle, making it hard to assemble a route efficiently.

Miloschewsky and Podder posted their preprint on September 17, 2026. Five days later, researchers Carolan, Childs, Coudron and Gilaniposted a different proof for the very same problem. Both proofs show that finding a route takes exponential time, but not exactly how much. The two groups are now working together to pin down the optimal bound, a step toward understanding exactly what quantum algorithms can and cannot do.

-By David Miloschewsky & Supartha Podder