# Quantum Computation and Information Seminar

### 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.

Supported by: Phys-Info (IT), SQIG (IT), CeFEMA and CAMGSD, with funding from FCT, FEDER and EU FP7, specifically through the Doctoral Programme in the Physics and Mathematics of Information (DP-PMI), FCT strategic projects PEst-OE/EEI/LA0008/2013 and UID/EEA/50008/2013, IT project QuSim, project CRUP-CPU CQVibes, the FP7 Coordination Action QUTE-EUROPE (600788), and the FP7 projects Landauer (GA 318287) and PAPETS (323901).