Vern Paulsen, University of Waterloo
"Complexity and Capacity Bounds for Operator Systems and Quantum Channels"
This
is
based
on
joint
work
with
R.
Levine
and
I.
Todorov.
Shannon
introduced
the
concept
of
the
one-shot
zero-error
capacity
of
a
classical
channel
and
proved
that
each
such
channel
had
a
graph
affiliated
with
it
so
that
the
one-shot
zero-error
capacity
was
the
independence
number
of
the
graph.
The
zero-error
capacity
is
then
obtained
by
taking
the
k-th
root
of
the
strong
product
of
the
graph
with
itself
k
times
and
taking
the
supremum
over
k.
Shannon
admittedly
couldn’t
compute
this
value
for
many
graphs,
but
then
Lovasz
introduced
his
theta
function
of
a
graph
as
a
computable
upper
bound.
The
Lovasz
theta
bound
is
still
the
best
known
bound
for
this
capacity.
Dean,
Severini,
and
Winter
studied
Shannon’s
ideas
for
quantum
channels
and
proved
that
each
quantum
channel
has
affiliated
with
it
an
operator
system
such
that
the
one-shot
zero-error
capacity
of
the
channel
is
the "independence
number”
of
the
operator
system.
They
then
argued
that
the
analogue
of
Shannon’s
capacity
is
to
take
the
k-th
root
of
the
independence
number
of
the
tensor
product
of
the
operator
system
with
itself
k
times
and
take
the
supremum
over
k.
They
then
introduced
the
analogue
of
the
Lovasz
theta
function
for
an
operator
system.
In
this
talk
we
will
review
these
ideas
and
then
introduce
our
new
idea
of
the
"complexity"
of
an
operator
system
and
show
that
this
gives
another
bound
on
the
zero-error
capacity
of
the
quantum
channel.
We
will
present
several
different
linear
algebraic
characterizations
of
complexity.
We
will
then
show
that
there
are
some
operator
systems
and
quantum
channels
for
which
our
complexity
based
bound
is
better
than
the
Lovasz
bound.
MC 5417