Title: Algorithms and complexity for quantum advantage
| Speaker: | David Gosset |
| Affiliation: | IBM - T.J. Watson Research Center |
| Room: | QNC 0101 |
Abstract:
There
is
strong
evidence
that
a
sufficiently
large
fault-tolerant
quantum
computer
would
solve
certain
computational
problems
exponentially
faster
than
any
classical
computer.
How
can
quantum
algorithms
and
complexity
theory
help
guide
the
way
forward
in
our
current
era
of
small
and
noisy
quantum
computers?
A
quantum
computer
without
error
correction
will
likely
be
limited
to
implementing
short
depth
quantum
circuits.
In
the
first
part
of
the
talk
I
will
describe
a
linear
algebra
problem
which
is
solved
by
a
constant-depth
quantum
circuit
but
provably
cannot
be
solved
by
any
classical
circuit
of
less
than
logarithmic
depth.
This
constitutes
an
unconditional
separation
between
constant
depth
quantum
circuits
and
their
classical
counterparts.
Classical
simulation
algorithms
can
be
used
to
verify
small
quantum
computers
and
to
help
demarcate
the
classically
easy
and
hard
regimes.
In
the
second
part
of
the
talk
I
will
describe
a
classical
algorithm
that
can
be
used
to
simulate
quantum
circuits
over
the
Clifford+T
gate
set
with
mildly
exponential
scaling
in
the
number
of
T
gates.
Finally,
I
will
discuss
how
quantum
computer
science
is
intimately
linked
with
our
understanding
of
physical
systems
and
the
complexity
of
simulating
them.
I
will
describe
how
a
universal
quantum
computer
is
equivalent
in
computational
power
to
a
quantum
many-body
system
consisting
of
indistinguishable
particles
which
move
and
interact
on
the
vertices
of
a
graph.