Welcome to Quantum Magazine's podcast. Each episode we bring you stories about developments

in science and mathematics. I'm Susan Vallage. Quantum algorithms can find their way out of

mazes exponentially faster than classical ones at the cost of forgetting the paths they took.

A new result suggests that the trade-off may be inevitable.

That's next.

Quantum Magazine is an editorially independent online publication supported by the Simon's Foundation, to enhance

public understanding of science.

Imagine you visit a maze with some friends. You make it through to the end pretty quickly,

then wait around for hours before your friends emerge. Naturally, they ask you about the path you

took. Surely you can retrace your steps and show them their way, right? Not so in a world

governed by the strange laws of quantum physics. Twenty years ago, quantum computing researchers

developed an algorithm that harnessed those laws to traverse a specific kind of mathematical maze much faster than any algorithm running on an ordinary classical computer.

But the speed up comes at a cost. The fast quantum algorithm finds the exit, but has no idea how it got there.

Researchers have long wondered whether this trade-off is inevitable.

Is it really impossible to find the exit quickly without forgetting the way?

Matthew Kudron is a computer scientist at the National Institute of Standards and Technology in Gaithersburg, Maryland.

It's kind of mind-blowing that you could even need to ask this question.

Like, why is there even a question about whether you could find a path?

Last November, Kudron and two colleagues took a big step toward resolving that long-standing problem.

They proved that no algorithm in a broad and natural class of fast

quantum algorithms can find a path through that special maze, called a welded tree graph. The results

show that any hypothetical path-finding algorithm that doesn't blindly guess would have to temporarily

...