Continuous-time quantum walk – Wikipedia
Quantum random walk dictated by a time-varying unitary matrix that relies on the Hamiltonian
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.
Recent Comments