is great, but it left me wondering what it could mean to “solve” a maze if the solution isn’t a description of a complete path from entry to exit.
The linked paper https://arxiv.org/abs/quant-ph/0209131 has the answer. Vertices are given random labels, and a maze oracle, queried with one vertex’s label, tells you the labels of the vertices you can reach from it. To “solve” the maze means identifying the label of the exit.
So a quantum algorithm that won’t remember any specific sequence of vertices through the maze can still tell you the name of the exit vertex.
