Quantum Theseus beats the Minotaur faster
Monday, 20 Jun. 2016, 17:30 - 18:30
Presenter: Yasser Omar
Host: Anton Zeilinger
Where: ATI, Stadionallee 2, Lecture-Hall, Vienna
Quantum computers can offer a speed-up for the spatial search problem, namely to find a marked vertex in a given graph. In particular, as defined by Childs and Goldstone, it is possible to perform quantum spatial search using a continuous-time quantum walk. Until recently, this approach was known to yield the optimal quadratic speed-up only for a handful of graphs, where symmetry and regularity seemed to be key features. However, in a sequence of works together with A. Ambainis, M. Mohseni, H. Neven, L. Novo, and S. Chakraborty, we have shown that quantum spatial search by quantum walk is robust to the loss of edges in a graph, and is in fact optimal for almost all graphs. Furthermore, I will show how these results on search can be extended to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely to perform quantum state transfer, as well as entanglement generation.