Thomas Vidick - The computational complexity of multiple entangled provers

MIT postdoc, Thomas Vidick lectures on the computational complexity of multiple entangled provers, during the "Recent Progress in Quantum Algorithms" conference. The event was hosted by The Institute for Quantum Computing, and The Perimeter Institute and was held in Waterloo, Ontario, April 11-13th, 2012. Abstract: Ever since its introduction, the computational complexity of the class MIP* of languages having multi-prover interactive proofs with entangled provers has been wide open. While its classical analogue, MIP, was characterized by Babai, Fortnow and Lund in the celebrated equality MIP=NEXP , it was not known whether the introduction of entanglement could lead to a collapse of this equality. We show that MIP* contains NEXP, that is, entanglement does not weaken the power of multi-prover interactive proof systems. Our work also leads to the first constant-factor hardness results on the complexity of multi-player entangled games. Our proof technique is based on an analysis of Babai, Fortnow, and Lund's "multilinearity test" in the presence of entangled provers. I will discuss entangled-prover proof systems and give an overview of our results in the simpler setting of Blum, Luby and Rubinfeld's linearity test, suggesting an answer to the question: what does it mean to say that entangled-prover strategies are "close to linear"? Based on joint work with Tsuyoshi Ito. Find out more about IQC! Website - https://uwaterloo.ca/institute-for-qu... Facebook - https://www.facebook.com/QuantumIQC Twitter - https://twitter.com/QuantumIQC