Departamento de Matemática Técnico Técnico

Seminário de Computação e Informação Quântica  RSS

30/06/2017, 15:00 — 16:00 — Sala P9, Pavilhão de Matemática
, 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.

Apoiado por: Phys-Info (IT), SQIG (IT), CeFEMA e CAMGSD, com financiamento de FCT, FEDER and EU FP7, especificamente via o Doctoral Programme in the Physics and Mathematics of Information (DP-PMI), os projectos estratégicos FCT PEst-OE/EEI/LA0008/2013 e UID/EEA/50008/2013, o projecto IT QuSim, o projecto CRUP-CPU CQVibes, a Acção de Coordenação FP7 QUTE-EUROPE (600788) e os projectos FP7 Landauer (GA 318287) e PAPETS (323901).


Instituto de TelecomunicaçõesCAMGSDFCT7th Framework Programme