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.

Hard Quantum Problems
Computational hardness results give us a way to identify problems
that are difficult to solve as well as a way to understand the power
of different models of computation. In the talk I will review some of
the problems we know to be hard for quantum models of computation and
give some idea of what these results mean outside of complexity
theory. Many of these problems are related to understanding the
behaviour of a quantum system or a quantum channel when given only a
compact description of it. Examples include the problem of deciding
how close a given channel is to unitary, or whether it is possible to
distinguish the output states of two quantum circuits. These problems
can be viewed as restricted versions of state and process tomography,
and hardness results for them tell us when a completely general
approach is unlikely to work, i.e. when we need to use additional
structure present in a specific instance to find a solution.

Quantum Commitments from Complexity Assumptions
Based on joint work with André Chailloux and Iordanis Kerenidis.
Bit commitment schemes are essential to modern cryptography, but
building informationtheoretically secure schemes is impossible,
even with quantum information. We consider building commitment
schemes from worstcase complexity assumptions. If QSZK is not in
QMA we a give computationallybinding and statisticallyhiding
auxiliaryinput commitment scheme. We also show that assuming PSPACE
is not in QMA, secure auxiliaryinput bitcommitment schemes using
quantum advice exist.
Presented at the
JapanSingapore Workshop on Multiuser Quantum Networks in Singapore.
A simlar talk was presented at the
2011 International Colloquium on Automata, Languages and Programming
(ICALP)
in Zürich.
You might also be interested in a poster related to this talk.

Testing quantum circuits and detecting insecure encryption
The computational problem of testing the behaviour of quantum circuits is shown to be hard
for the class QMA of problems that can be verified efficiently with a quantum computer.
This result generalizes techniques previously used to prove the hardness of other problems on quantum circuits.
We use this result to show the QMAcompleteness of a weak version of the problem of detecting the insecurity
of a symmetrickey quantum encryption system or alternately the problem of determining when
a quantum channel is not private.
Presented at the
2012 Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)
in Tokyo.
You might also be interested in a poster related to this talk.

Testing nonisometry is QMAcomplete
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.
Presented at the
2010 Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)
in Leeds.
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 PSPACEcomplete.

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 mixedunitary 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 mixedunitary channels is no easier than the general
case (which is QIPcomplete), as well as a proof that the additivity
of the minimum output entropy holds for all channels if and only if
it holds for mixedunitary channels.
Presented at the
2009 Workshop on Quantum Information Processing (QIP) in Sante Fe.

Distinguishing short quantum computations
This talk extends the QIPhardness of distinguishing quantum channels to
the case where the channels are given as mixedstate 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 mixedstate quantum
computations
Based on joint work with John Watrous.
The problem considered in this talk is: given two quantum
channels, implemented as mixedstate 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.