The Quantum Walking Dead

Find a path through a maze exponentially faster

One of the most striking demonstrations of the potential of quantum computing is how quantum algorithms can navigate through mazes.

Classic algorithms are limited to exploring one path at a time.

They can either dive deep into a single corridor with depth-first search or slowly spread out in all directions with breadth-first search.

Either way, they are slow, methodical and terribly inefficient at finding the shortest path through a complex maze if there is no meaningful heuristic.

Quantum computers, on the other hand, are often said to explore many possibilities at once. That sounds ideal, doesn't it? If there was ever a perfect use case for quantum computers, it would surely be escaping from a maze.