Quantum Computation and Information Seminar 

27/03/2009, 15:00 — 16:00 — Room P4.35, Mathematics Building
Daniel Reitzner, Slovak Academy of Sciences

Scattering-Quantum-Walk searches

We show how to apply scattering quantum walks on highly symmetric graphs to solve search problems on these graphs for one of the marked target vertices. Scattering properties of the vertices depend on whether they are the target ones or not. To provide such differentiation we employ a quantum circuit that utilizes standard Grover oracle alongside presented evolution of the walk. This circuit allows us to separate oracular elements of the problem from the rest of the evolution. As graphs we consider complete graph, complete bipartite graph, and an $M$-partite graph as their common generalization. In all considered graphs, for the symmetry reasons --- these graphs have large automorphism groups --- the evolution takes place in a Hilbert space of small dimension, not unlike in standard Grover search. Joint work with M. Hillery, E. Feldman, V. Buzek