Automatica, Vol.49, No.5, 1358-1364, 2013
Controllability of system dynamics on networks, quantum walks and random walks
We consider a model of system dynamics on networks consisting of a certain number of stations (nodes) connected by edges. At every time step, a certain quantity leaves the stations and gets re-distributed among the neighboring stations (preserving an appropriate norm). One has the control, at every station, on the relative quantity which is sent to the various neighbors. Controllability is achieved when every possible distribution of the given quantity in a natural set can be obtained. This general model includes, in particular, classical and quantum walks on graphs. The case of quantum walks is treated in detail and it is proved that controllability is achieved if and only if the underlying graph is not bipartite. This extends to general graphs a result previously proved in the literature for the case where the underlying graph is regular. Then extensions are presented to general systems modeling system dynamics on networks. (c) 2013 Elsevier Ltd. All rights reserved.