Quantum algorithms can find their way out of mazes exponentially faster than classical ones, at the cost of forgetting the path they took. A new result suggests that the trade-off may be inevitable. The post To Move Fast, Quantum Maze Solvers Must Forget the Past first appeared on Quanta Magazine
Imagine you visit a maze with some friends. You emerge from the exit shortly after going in, and wait around for hours before your friends emerge. Naturally, they ask about the path you took — surely you can retrace your steps and show them the 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…