- Time
- 1:30 – 2:20pm, Tuesday, October 12, 2010
- Place
- CSE 305
- Speaker
- Aram Harrow, University of Washington
## Abstract

If quantum states of many systems are analogous to probability
distributions over many variables, then product states are the
analogue of independent distributions. Our first result is a test
that uses two copies of a quantum state and estimates whether the
state is close to a product state or far from any product state. This
allows us to resolve several questions related to multi-prover quantum
Merlin-Arthur proof systems, showing that soundness amplification is
possible and that 2 provers are equivalent to a polynomial number of
provers. These results in turn imply the computational hardness of
problems such as estimating the largest singular value of a 3-index
tensor and estimating the distortion of certain metric space
embeddings.

This talk is based on arXiv:1001.0017 (to appear in FOCS 2010), which
is joint work with Ashley Montanaro. No quantum knowledge will be
assumed, although hopefully I'll introduce some along the way.