Continuous-time quantum walk

A continuous-time quantum walk (CTQW) is a quantum walk on a given (simple) 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;[1] since many classical algorithms are based on (classical) 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 ${\displaystyle G}$ is a graph on ${\displaystyle n}$ vertices, and that ${\displaystyle t\in \mathbb {R} }$.

Continuous-time quantum walks

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.

Mixing matrices

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}$.

Periodic vertices

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

Perfect state transfer

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}$.

Periodic graphs

A graph ${\displaystyle G}$ itself is said to be periodic if there is a time ${\displaystyle t\neq 0}$ such that all of its vertices are periodic at time ${\displaystyle t}$.

A graph is periodic if and only if its (non-zero) eigenvalues are all rational multiples of each other.[2]

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 ${\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]

Perfect state transfer on products of graphs

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}$.

Perfect state transfer on walk-regular graphs

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.

References

1. Farhi, Edward; Gutmann, Sam (1 August 1998). "Quantum computation and decision trees". Physical Review A. American Physical Society (APS). 58 (2): 915–928. arXiv:quant-ph/9706062. doi:10.1103/physreva.58.915. ISSN 1050-2947.
2. Godsil, Chris (26 January 2011). "Periodic Graphs". The Electronic Journal of Combinatorics. 18 (1): P23. ISSN 1077-8926.
3. Zhan, Harmony; Godsil, Chris. "Periodic Vertices | Introduction". www.math.uwaterloo.ca. Retrieved 30 August 2017.

External links

• Quantum Walk on arxiv.org
• CTQW on Wolfram Demonstrations
• Quantum walk