Quantum Theseus beats the Minotaur faster

Imagine you are lost in a labyrinth looking for the exit. Or that you are the ancient Greek hero Theseus searching for the Minotaur. Is using a quantum computer, which can explore all paths in parallel thanks to the quantum superposition principle, the fastest way to find the solution?

The answer was known to be yes, but only for a handful of labyrinth structures, having a lot of regularity and symmetry (such as the one in Fig. 1a). In their work published in Physical Review Letters and highlighted as an editors' suggestion, Shantanav Chakraborty, Leonardo Novo and Yasser Omar from the Physics of Information and Quantum Technologies Group at Instituto de Telecomunicações together with Andris Ambainis from the University of Latvia, found that a quantum walk through random labyrinths still allows finding the exit in the fastest way possible, even though the structure can be extremely disordered. This shows that the quantum advantage in computation is robust to spatial disorder. Furthermore, the authors extend their results to show that it is possible to establish high fidelity quantum communication between two arbitrary nodes of a random network, namely to perform quantum bit transfer, as well as entanglement generation. This work opens way to developing quantum information tasks that retain optimal performance in highly disordered systems.

For more details, see the article:
S. Chakraborty, L. Novo, A. Ambainis, Y. Omar, Spatial search by quantum walk is optimal for almost all graphs, Physical Review Letters 116, 100501 (2016)