Continuous-time quantum walk

The continuous-time quantum walk ${\displaystyle U(t)\in \operatorname {Mat} _{n\times n}(\mathbb {C} )}$ on ${\displaystyle G}$ at time ${\displaystyle t}$ is defined as:

$${\displaystyle U(t):=e^{itA}}$$

letting ${\displaystyle A}$ denote the adjacency matrix of ${\displaystyle G}$.

It is also possible to similarly define a continuous-time quantum walk on ${\displaystyle G}$ 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.

The mixing matrix ${\displaystyle M(t)\in \operatorname {Mat} _{n\times n}(\mathbb {R} )}$ of ${\displaystyle G}$ at time ${\displaystyle t}$ is defined as ${\displaystyle M(t):=U(t)\circ U(-t)}$.

Mixing matrices are symmetric doubly-stochastic matrices obtained from CTQWs on graphs: ${\displaystyle {M(t)}_{u,v}}$ gives the probability of ${\displaystyle u}$ transitioning to ${\displaystyle v}$ at time ${\displaystyle t}$ for any vertices ${\displaystyle u}$ and v on ${\displaystyle G}$.

A vertex ${\displaystyle u}$ on ${\displaystyle G}$ is said to periodic at time ${\displaystyle t}$ if ${\displaystyle {M(t)}_{u,u}=1}$.

Distinct vertices ${\displaystyle u}$ and ${\displaystyle v}$ on ${\displaystyle G}$ are said to admit perfect state transfer at time ${\displaystyle t}$ if ${\displaystyle M(t)_{u,v}=1}$.

If a pair of vertices on ${\displaystyle G}$ admit perfect state transfer at time t, then ${\displaystyle G}$ itself is said to admit perfect state transfer (at time t).

A set ${\displaystyle S}$ of pairs of distinct vertices on ${\displaystyle G}$ is said to admit perfect state transfer (at time ${\displaystyle t}$) if each pair of vertices in ${\displaystyle S}$ admits perfect state transfer at time ${\displaystyle t}$.

A set ${\displaystyle S}$ of vertices on ${\displaystyle G}$ is said to admit perfect state transfer (at time ${\displaystyle t}$) if for all ${\displaystyle u\in S}$ there is a ${\displaystyle v\in S}$ such that ${\displaystyle u}$ and ${\displaystyle v}$ admit perfect state transfer at time ${\displaystyle t}$.

If a pair of vertices ${\displaystyle u}$ and ${\displaystyle v}$ on a graph ${\displaystyle G}$ admit perfect state transfer at time ${\displaystyle t}$, then both ${\displaystyle u}$ and ${\displaystyle v}$ are periodic at time ${\displaystyle 2t}$.[3]

Consider graphs ${\displaystyle G}$ and ${\displaystyle H}$.

If both ${\displaystyle G}$ and ${\displaystyle H}$ admit perfect state transfer at time ${\displaystyle t}$, then their Cartesian product ${\displaystyle G\,\square \,H}$ admits perfect state transfer at time ${\displaystyle t}$.

If either ${\displaystyle G}$ or ${\displaystyle H}$ admits perfect state transfer at time ${\displaystyle t}$, then their disjoint union ${\displaystyle G\sqcup H}$ admits perfect state transfer at time ${\displaystyle t}$.

If a walk-regular graph admits perfect state transfer, then all of its eigenvalues are integers.

If ${\displaystyle G}$ is a graph in a homogeneous coherent algebra that admits perfect state transfer at time ${\displaystyle t}$, such as e.g. a vertex-transitive graph or a graph in an association scheme, then all of the vertices on ${\displaystyle G}$ admit perfect state transfer at time ${\displaystyle t}$. Moreover, a graph ${\displaystyle G}$ 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 ${\displaystyle G}$ cannot admit perfect state transfer between a pair of adjacent vertices, unless it is a disjoint union of copies of the complete graph ${\displaystyle K_{2}}$.

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 ${\displaystyle K_{2}}$.

The only cubic distance-regular graph that admits perfect state transfer is the cubical graph.