Ver Post

Quantum Theseus beats the Minotaur faster

29 abril 2016, 10:00 - Sandra Rodrigues José Martins

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 and Leonardo Novo, two students from the Doctoral Programme in the Physics and Mathematics of Information at Instituto Superior Técnico (University of Lisbon), jointly with their supervisor Yasser Omar, all of them members of the Physics of Information and Quantum Technologies Group at Instituto de Telecomunicações, in Portugal, 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 (such as the one in Fig. 1b). This is a very surprising discovery, which shows that the quantum advantage in computation is robust to spatial disorder.


 Picture  (see attach)
Fig. 1 - Can a quantum computer help Theseus find the minotaur in the fastest way possible? The answer was only known to be yes for a few very easy labyrinths (Fig. 1a), but the authors have now discovered that in fact this can be the case for almost any labyrinth (Fig. 1b).


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) – Editors' Suggesttion. Get PDF