Universal computation by multi-particle quantum walk
| Speaker: | David Gosset |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
A
quantum
walk
is
a
time-homogeneous
quantum-mechanical
process
on
a
graph
defined
by
analogy
to
classical
random
walk.
The
quantum
walker
is
a
particle
that
moves
from
a
given
vertex
to
adjacent
vertices
in
quantum
superposition.
Here
we
consider
a
generalization
of
quantum
walk
to
systems
with
more
than
one
walker.
A
continuous-time
multi-particle
quantum
walk
is
generated
by
a
time-independent
Hamiltonian
with
a
term
corresponding
to
a
single-particle
quantum
walk
for
each
particle,
along
with
an
interaction
term.
Multi-particle
quantum
walk
includes
a
broad
class
of
interacting
many-body
systems
such
as
the
Bose-Hubbard
model
and
systems
of
fermions
or
distinguishable
particles
with
nearest-neighbor
interactions.
We
show
that
multi-particle
quantum
walk
is
capable
of
universal
quantum
computation.
Since
it
is
also
possible
to
efficiently
simulate
a
multi-particle
quantum
walk
of
the
type
we
consider
using
a
universal
quantum
computer,
this
model
exactly
captures
the
power
of
quantum
computation.
In
principle
our
construction
could
be
used
as
an
architecture
for
building
a
scalable
quantum
computer
with
no
need
for
time-dependent
control.
Joint
work
with
Andrew
M.
Childs
and
Zak
Webb.