Title: The quantum information cost of forgetting classical information
Speaker: | Dave Touchette |
Affiliation: | University of Waterloo, IQC |
Room: | MC 5501 |
Abstract:
In
the
basic
communication
complexity
setup,
Alice
and
Bob
are
given
classical
inputs
x
and
y,
respectively,
and
they
want
to
compute
a
bipartite
function
f(x,
y)
while
minimizing
the
amount
of
communication
they
must
exchange.
In
the
closely
related
information
complexity
setting,
we
are
instead
interested
in
the
least
amount
of
information
that
Alice
and
Bob
must
leak
to
each
other
about
their
respective
inputs
in
order
to
compute
the
function
f(x,
y).
This
information
complexity
paradigm
has
proven
to
be
a
powerful
tool
for
obtaining
communication
complexity
lower
bounds
in
both
the
classical
and
quantum
settings.
In
quantum
protocols,
it
is
possible
for
Alice
and
Bob
to
forget
information
they
have
learned
about
each
other’s
classical
input.
In
this
talk,
we
explore
the
many
consequences
of
this
ability
of
quantum
protocols
to
forget
information
for
defining
a
quantum
notion
of
information
cost.