The Simons Center at Stony Brook University in an archival photograph. University context; not a photograph of a quantum computer or a solved pathfinding instance.Image: Stony Brook Simons Center exterior · Kenneth C. Zirkel · CC BY-SA 4.0Full image credit
A quantum computer can identify the exit of a specially constructed maze far faster than a classical algorithm. Producing an actual route through that maze is a different problem.[1][2]
A Stony Brook research update describes a proof that quantum algorithms still need exponentially many queries to produce such a route in the welded-tree model.[1][2]
David Miloschewsky and Supartha Podder posted their preprint on September 17. The university highlighted it on October 22. Their argument tracks information an algorithm learns and forgets, using a compressed permutation-oracle method to rule out efficient path construction in the specified model.[1][2]
The result sharpens the boundary around a celebrated quantum speedup. It does not show that quantum computers are bad at every routing problem or remove the speedup for identifying the exit.[1]
Finding a destination and returning the sequence of steps needed to reach it remain distinct computational tasks.[1]
