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

edit

Suppose that   is a graph on   vertices, and that  .

Continuous-time quantum walks

edit

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

edit

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

edit

A vertex   on   is said to periodic at time   if  .

Perfect state transfer

edit

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 (at time t).

A set   of pairs of distinct vertices on   is said to admit perfect state transfer (at time  ) if each pair of vertices in   admits perfect state transfer at time  .

A set   of vertices on   is said to admit perfect state transfer (at time  ) if for all   there is a   such that   and   admit perfect state transfer at time  .

Periodic graphs

edit

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 (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

edit

Necessary conditions

edit

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

Perfect state transfer on products of graphs

edit

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

edit

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.

References

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