Optimal search in random graphs using quantum walks
Leonardo Novo (Instituto de Telecomunicaçoes)
Place: Sala 1.11
Time: 13.6.2017, 10:30
Title: Optimal search in random graphs using quantum walks
The problem of searching an element in a database is one of the most fundamental ones in computer science. In quantum computation, this problem can be tackled by Grover’s algorithm, which has a provable quadratic speed-up with respect to the best possible classical algorithm for unstructured search. For structured search, it is possible to tackle this problem by using quantum walks in continuous time, where a wavefunction evolves in the vertices of a graph that encodes the structure of the database. A natural question is: for what kind of graphs does quantum search work in optimal time? Results were known for a handful of families of graphs like lattices and hypercubes. In this work we show that it is possible to search in optimal time in a completely random graph, where each edge exists with a certain probability. This implies that if we pick a graph at random from the set of all graphs, quantum search will most likely work. We also show that state transfer and entanglement generation are possible with high fidelity in a random structure. We further discuss optimality of search in an extension of the model where the edges can appear and disappear dynamically.