on 30-06-2017
Daniel Reitzner
Instituto Superior Técnico, Lisbon, Room P9, Mathematics Building, Friday, June 30th, 15:00h
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 ocalized 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.
Quantum Computation and Information Seminar
http://math.tecnico.ulisboa.pt/seminars/qci/index.php.en?action=next
Support: Phys-Info (IT), SQIG (IT) and CAMGSD, with support from FCT and FEDER, namely via the Doctoral Programme in the Physics and Mathematics of Information (DP-PMI), and projects UID/EEA/50008/2013, QuNet, ProQuNet, and NQuN.