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