DF Seminar

[Rosita Glavina]

Department of Physics - University of Trieste

Friday 3 September 2010 - 3.00 pm
Room 204 (2nd floor LB)

prof. Domenico D'Alessandro
(Iowa State University, Ames, Iowa, USA)

Title: Controllability of Quantum Random Walks on Graphs

Abstract: In recent years, quantum random walks have been studied as 
useful protocols to design quantum algorithms. In these algorithms, the 
state of a quantum system modeled after a random walk on a graph is 
driven from one state to another solving a specific computational 
problem. In this talk, we shall consider a general model of a quantum 
walk evolving in discrete time steps and ask the question of 
characterizing the set of states that can be attained by these  systems. 
This question is referred to as the controllability of the system. After 
the description of the model and its dynamics  we shall characterize the 
controllability of quantum  walks in terms of both algebraic and 
combinatorial conditions. One of the main results states that the 
controllability of the quantum walk only depends on the underlying graph 
and, in particular, any unitary evolution between states is possible as 
long as the underlying graph is not bipartite. We shall also discuss the 
impact of these results on the problem of establishing a relation 
between discrete time and continuous time quantum walks.