Talk Slides
Generally only the slides from the most recent version of any
particular talk are listed here. If you'd like a different set of
slides, feel free to
email me.
-
Testing non-isometry is QMA-complete
The problem of determining when a circuit implements an operation
that is close to an isometry is shown to characterize the complexity
class QMA of problems verifiable with a quantum computer. This is
the problem of determining the purity of the
output of the circuit, minimized over pure input states.
You might also be interested in a poster related to this talk.
-
Distinguishability of quantum channels
This talk provides an overview of the computational problem of
distinguishing two quantum channels, given as quantum circuits that
use ancilla and may make measurements during the computation. This
problem for general channels, as well as channels from a few
restricted classes, is PSPACE-complete.
-
Distinguishability of random unitary channels
(see also a longer version
which focuses on a closely related result)
This talk presents a reduction that transforms a general quantum
channels to a mixed-unitary channel (a convex combination of
unitary channels). This reduction preserves many of the properties
of the channel. Consequences of this technique include a proof that
distinguishing mixed-unitary channels is no easier than the general
case (which is QIP-complete), as well as a proof that the additivity
of the minimum output entropy holds for all channels if and only if
it holds for mixed-unitary channels.
Presented at the
2009 Workshop on Quantum Information Processing (QIP) in Sante Fe.
-
Distinguishing short quantum computations
This talk extends the QIP-hardness of distinguishing quantum channels to
the case where the channels are given as mixed-state circuits of
logarithmic depth. This implies that even circuits that can be
implemented in a very short amount of time can be computationally
infeasible to distinguish.
Presented at the
2008 Symposium on Theoretical Aspects of Computer Science
(STACS) in Bordeaux.
-
The overlap number of a graph
Based on joint work with Lorna Stewart.
This talk
introduces a new graph parameter: the size of a minimum overlap
representation. This is closely related to the intersection number,
which is exactly the size of a minimum edge clique cover. No such
characterization for the overlap number is known. Constructions of
minimum overlap representations for some very simple graphs are
given.
Presented at the
2006 SIAM Conference on Discrete Mathematics in Victoria.
-
On the hardness of distinguishing mixed-state quantum
computations
Based on joint work with John Watrous.
The problem considered in this talk is: given two quantum
channels, implemented as mixed-state circuits, decide if the two
channels are distinguishable, i.e. if there is an input on which
they produce nearly orthogonal states, or if the two circuits always
produce states that are close together. This problem is shown to be
complete for the class QIP of problems having quantum interactive
proof systems.
Presented at the 2005 IEEE Conference on Computational Complexity in
San Jose.