Exponential Improvement in Precision for Simulating Sparse Hamiltonians
| Speaker: | Andrew Childs |
|---|---|
| Affiliation: | University of Waterloo |
| Room: |
Mathematics 3 (M3) 3127 |
Abstract:
We
provide
a
quantum
algorithm
for
simulating
the
dynamics
of
sparse
Hamiltonians
with
complexity
sublogarithmic
in
the
inverse
error,
an
exponential
improvement
over
previous
methods.
Our
algorithm
is
based
on
a
significantly
improved
simulation
of
the
fractional-query
model
using
discrete
quantum
queries,
showing
that
fractional
queries
are
not
much
more
powerful
than
discrete
ones
even
for
very
small
error.
We
significantly
simplify
the
analysis
of
this
conversion,
avoiding
the
need
for
a
complex
fault
correction
procedure.
Our
simplification
relies
on
a
new
form
of
"oblivious
amplitude
amplification"
that
can
be
applied
even
though
the
reflection
about
the
input
state
is
unavailable.
We
also
prove
new
lower
bounds
showing
that
our
algorithm
is
optimal
as
a
function
of
the
error.
Based
on
joint
work
with
Dominic
Berry,
Richard
Cleve,
Robin
Kothari,
and
Rolando
Somma.