Abstract
The class \(\mathrm {MIP}^*\) of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Very little is known in terms of the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. in 2006. This hierarchy converges to a value, the field-theoretic value, that is only known to coincide with the provers’ maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes’ embedding conjecture. No bounds on the rate of convergence are known.
We introduce a rounding scheme for the hierarchy, establishing that any solution to its \(N\)-th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by \(O(\ell ^2/\sqrt{N})\) in operator norm, where \(\ell \) is the number of possible answers per prover.
Our rounding scheme motivates the introduction of a variant of quantum multiprover interactive proof systems, called \(\mathrm {MIP}_\delta ^*\), in which the soundness property is required to hold against provers allowed to operate on the same Hilbert space as long as the commutator of operations performed by distinct provers has norm at most \(\delta \). Our rounding scheme implies the upper bound \(\mathrm {MIP}_\delta ^* \subseteq \mathrm {DTIME}(\exp (\exp ({{\mathrm{poly}}})/\delta ^2))\). In terms of lower bounds we establish that \(\mathrm {MIP}^*_{2^{-{{\mathrm{poly}}}}}\) contains \(\mathrm {NEXP}\) with completeness \(1\) and soundness \(1-2^{-{{\mathrm{poly}}}}\). We discuss connections with the mathematical literature on approximate commutation and applications to device-independent cryptography.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501–555 (1998)
Aravind, P.K.: The magic squares and Bell’s theorem. Technical report (2002 arXiv:quant-ph/0206070
Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM 45(1), 70–122 (1998)
John, S.: Bell. On the Einstein-Podolsky-Rosen paradox. Physics 1, 195–200 (1964)
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity 1, 3–40 (1991)
Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: How to remove intractability assumptions. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 113–131 (1988)
Bancal, J.-D., Sheridan, L., Scarani, V.: More randomness from the same data. New Journal of Physics 16(3), 033011 (2014)
Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880–884 (1969)
Cleve, R., Høyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proc. 19th IEEE Conf. on Computational Complexity (CCC 2004), pp. 236–249. IEEE Computer Society (2004)
Colbeck, R., Kent, A.: Private randomness expansion with untrusted devices. Journal of Physics A: Mathematical and ..., 1–11 (2011)
Connes, A.: Classification of injective factors cases \(ii_1\), \(ii_\infty \), \(iii_\lambda \), \(\lambda \ne 1\). Annals of Mathematics 104(1), 73–115 (1976)
Doherty, A.C., Liang, Y-C., Toner, B., Wehner, S.: The quantum moment problem and bounds on entangled multi-prover games. In: Proc. 23rd IEEE Conf. on Computational Complexity (CCC 2008), pp. 199–210 (2008)
Exel, R., Loring, T.: Almost commuting unitary matrices. In: Proceedings of the American Mathematical Society 106(4), 913–915 (1989)
Einstein, A., Podolsky, B., Rosen, N.: Can quantum-mechanical description of physical reality be considered complete? Physical Review 47, 777–780 (1935)
Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268–292 (1996)
Ito, T., Kobayashi, H., Matsumoto, K.: Oracularization and two-prover one-round interactive proofs against nonlocal strategies. In: Proc. 24th IEEE Conf. on Computational Complexity (CCC 2009), pp. 217–228. IEEE Computer Society (2009)
Ito, T., Vidick, T., A multi-prover interactive proof for NEXP sound against entangled provers. In: Proc. 53rd FOCS, pp. 243–252 (2012)
Junge, M., Navascues, M., Palazuelos, C., Perez-Garcia, D., Scholz, V.B., Werner, R.F.: Connes’ embedding problem and tsirelson’s problem. J. Math. Physics 52(1) (2011)
Kirchberg, E.: On non-semisplit extensions, tensor products and exactness of group \({C}^*\)-algebras. Inventiones mathematicae 112(1), 449–489 (1993)
Kobayashi, H., Matsumoto, K.: Quantum multi-prover interactive proof systems with limited prior entanglement. Journal of Computer and System Sciences 66(3), 429–450 (2003)
Kempe, J., Regev, O., Toner, B.: Unique games with entangled provers are easy. SIAM J. Comput. 39(7), 3207–3229 (2010)
Laurent, M.: A comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre relaxations for 0–1 Programming. Mathematics of Operations Research 28(3), 470–496 (2003)
Ll. Masanes. Extremal quantum correlations for n parties with two dichotomic observables per site. Technical report (2005). arXiv:quant-ph/0512100
Miller, C.A., Shi, Y.: Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. In: Proc. 46th STOC. ACM New York (2014)
Navascués, M., Pironio, S., Acín, A.: Bounding the set of quantum correlations. Phys. Rev. Lett. 98, 010401 (2007)
Navascués, M., Pironio, S., Acín, A.: A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(073013) (2008)
Ozawa, N.: Tsirelson’s problem and asymptotically commuting unitary matrices. Journal of Mathematical Physics 54(3) (2013)
Pironio, S., Acín, A., Massar, S.: Random numbers certified by Bell’s theorem. Nature, 1–26 (2010)
Pál, K.F., Vértesi, T.: Maximal violation of a bipartite three-setting, two-outcome Bell inequality using infinite-dimensional quantum systems. Phys. Rev. A 82, 022116 (2010)
Silman, J., Pironio, S., Massar, S.: Device-independent randomness generation in the presence of weak cross-talk. Phys. Rev. Lett. 110, 100504 (2013)
Scholz, V.B., Werner, R.F.: Tsirelson’s problem. Technical report (2008). arXiv:0812.4305v1 [math-ph]
Vidick, T.: Three-player entangled XOR games are NP-hard to approximate. In: Proc. 54th FOCS (2013)
Voiculescu, D.: Asymptotically commuting finite rank unitary operators without commuting approximants. Acta Sci. Math. (Szeged) 45, 429–431 (1983)
Yang, T.H., Vertesi, T., Bancal, J-D., Scarani, V., Navascues, M.: Robust and Versatile Black-Box Certification of Quantum Devices. Phys. Rev. Lett. 113(4), (July 22, 2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Coudron, M., Vidick, T. (2015). Interactive Proofs with Approximately Commuting Provers. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_29
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)