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.