Quantum Computation and Information Seminar 

30/06/2017, 15:00 — 16:00 — Room P9, Mathematics Building
Daniel Reitzner, Slovak Academy of Sciences

Navigating a Maze Using Quantum-Walk Searches

Quantum searches are used to localize a specific element within the Hilbert space. Usually such element is a base state, or a small subspace of the Hilbert space. We expand this set by searching for a path in a maze between two specific vertices using quantum walks. A particular type of maze we use is a chain of connected stars. We show, that having $M$ stars, each of them containing $N$ spikes, we can find the whole path in $O(M N^{1/2})$ steps. Standard choice of the initial state in a large, albeit phase-modulated superposition leads to the usual Grover search. However, such state is usually hard to prepare and a choice of a localized state is preferred. In such case we show, that it is possible to find the path with the same efficiency (up to a multiplicative constant) successively, by starting on the first star and uncovering successive stars by short searches of $O(N^{1/2})$ steps.