Continuous-time quantum walk


A continuous-time quantum walk is a quantum walk on a given graph that is dictated by a time-varying unitary matrix that relies on the Hamiltonian of the quantum system and the adjacency matrix. The concept of a CTQW is believed to have been first considered for quantum computation by Edward Farhi and Sam Gutmann; since many classical algorithms are based on random walks, the concept of CTQWs were originally considered to see if there could be quantum analogues of these algorithms with e.g. better time-complexity than their classical counterparts. In recent times, problems such as deciding what graphs admit properties such as perfect state transfer with respect to their CTQWs have been of particular interest.

Definitions

Suppose that is a graph on vertices, and that.

Continuous-time quantum walks

The continuous-time quantum walk on at time is defined as:letting denote the adjacency matrix of.
It is also possible to similarly define a continuous-time quantum walk on relative to its Laplacian matrix; although, unless stated otherwise, a CTQW on a graph will mean a CTQW relative to its adjacency matrix for the remainder of this article.

Mixing matrices

The mixing matrix of at time is defined as.
Mixing matrices are symmetric doubly-stochastic matrices obtained from CTQWs on graphs: gives the probability of transitioning to at time for any vertices and v on.

Periodic vertices

A vertex on is said to periodic at time if.

Perfect state transfer

Distinct vertices and on are said to admit perfect state transfer at time if.
If a pair of vertices on admit perfect state transfer at time t, then itself is said to admit perfect state transfer.
A set of pairs of distinct vertices on is said to admit perfect state transfer if each pair of vertices in admits perfect state transfer at time.
A set of vertices on is said to admit perfect state transfer if for all there is a such that and admit perfect state transfer at time.

Periodic graphs

A graph itself is said to be periodic if there is a time such that all of its vertices are periodic at time.
A graph is periodic if and only if its eigenvalues are all rational multiples of each other.
Moreover, a regular graph is periodic if and only if it is an integral graph.

Perfect state transfer

Necessary conditions

If a pair of vertices and on a graph admit perfect state transfer at time, then both and are periodic at time.

Perfect state transfer on products of graphs

Consider graphs and.
If both and admit perfect state transfer at time, then their Cartesian product admits perfect state transfer at time.
If either or admits perfect state transfer at time, then their disjoint union admits perfect state transfer at time.

Perfect state transfer on walk-regular graphs

If a walk-regular graph admits perfect state transfer, then all of its eigenvalues are integers.
If is a graph in a homogeneous coherent algebra that admits perfect state transfer at time, such as e.g. a vertex-transitive graph or a graph in an association scheme, then all of the vertices on admit perfect state transfer at time. Moreover, a graph must have a perfect matching that admits perfect state transfer if it admits perfect state transfer between a pair of adjacent vertices and is a graph in a homogeneous coherent algebra.
A regular edge-transitive graph cannot admit perfect state transfer between a pair of adjacent vertices, unless it is a disjoint union of copies of the complete graph.
A strongly regular graph admits perfect state transfer if and only if it is the complement of the disjoint union of an even number of copies of.
The only cubic distance-regular graph that admits perfect state transfer is the cubical graph.