A quantum product-state test with applications to complexity

1:30 – 2:20pm, Tuesday, October 12, 2010
CSE 305
Aram Harrow, University of Washington


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.