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.
-
Quantum Commitments from Complexity Assumptions
Bit commitment schemes are essential to modern cryptography, but
building information-theoretically secure schemes is impossible,
even with quantum information. We consider building commitment
schemes from worst-case complexity assumptions. If QSZK is not in
QMA we a give computationally-binding and statistically-hiding
auxiliary-input commitment scheme. We also show that assuming PSPACE
is not in QMA, secure auxiliary-input bit-commitment schemes using
quantum advice exist.
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.
-
Hard Problems in a Quantum World
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 survey some
of the problems we know to be hard for quantum models of computation
and give some idea of how these results can be applied outside of
complexity theory. I will focus on problems related to
understanding the behaviour of a quantum system or a quantum channel
when given only a compact description of it. These problems can be
viewed as restricted versions of state and process tomography. This
talk also discusses the problems of estimating the ground state of a local
Hamiltonian, determining when a channel is close to a unitary
operation, distinguishing two channels, and testing the security of
a quantum encryption system.
Presented at the Centre for Quantum Technologies at the University of
Kwanzulu-Natal in Durban.
-
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.
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 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.