publication . Preprint . 2016

Certifying the absence of quantum nonlocality

Miller, Carl A.; Shi, Yaoyun;
Open Access English
  • Published: 02 Aug 2016
Abstract
Quantum nonlocality is an inherently non-classical feature of quantum mechanics and manifests itself through violation of Bell inequalities for nonlocal games. We show that in a fairly general setting, a simple extension of a nonlocal game can certify instead the absence of quantum nonlocality. Through contraposition, our result implies that a super-classical performance for such a game ensures that a player's output is unpredictable to the other player. Previously such output unpredictability was known with respect to a third party.
Subjects
arXiv: Computer Science::Computer Science and Game Theory
ACM Computing Classification System: TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSComputingMilieux_PERSONALCOMPUTING
free text keywords: Quantum Physics
Funded by
NSF| AF: CIF: Small: Theoretical Problems in Quantum Cmputation and Cmmunication
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1216729
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| PFI:AIR - TT: Prototyping Untrusted-Device Quantum Cryptography
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1500095
,
NSF| AF: Small: Theory and Applications of Untrusted Quantum Devices
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1318070
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| STARSS: TTP Option: Small: A Quantum Approach to Hardware Security: from Theory to Optical Implementation
Download from

by US NSF Awards 1500095, 1216729, 1526928, and 848 (2011), http://dx.doi.org/10.1137/090751293, URL 1318070. http://dx.doi.org/10.1137/090751293.

[14] U. Vazirani and T. Vidick, in Proceedings of The 5th

(2014), arXiv:1210.1810v2.

[15] T. Vidick, in Proceedings - Annuel IEEE Symposium on

∗ carlmi@umich.edu Foundations of Computer Science (FOCS) (2013), pp.

† shiyy@umich.edu 766-755. [1] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and [16] J. Kaniewski and S. Wehner, Device-independent twoS. Wehner, Rev. Mod. Phys. 86, 419 86 (2014). party cryptography secure against sequential attacks, [2] R. Colbeck, Ph.D. thesis, University of Cambridge arXiv:1601.06752 (2016).

(2006), arXiv:0911.3814. [17] J. Riberio, L. P. Thinh, J. Kaniewski, J. Helsen, and [3] S. Pironio, A. Ac´ın, S. Massar, A. Boyer de la Giroday, S. Wehner, Device-independence for two-party cryptograD. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, phy and position verification, arXiv:1606.08750 (2016).

L. Luo, T. A. Manning, et al., Nature 464, 1021 (2010). [18] M. McKague, Interactive proofs for bqp via self-tested [4] R. Colbeck and A. Kent, Journal of Physics A: Math- graph states, arXiv:1309.5675v2 (2015).

ematical and Theoretical 44, 095305 (2011), URL [19] B. Tsirelson, Bell inequalities and operator algebras, http://stacks.iop.org/1751-8121/44/i=9/a=095305. http://www.tau.ac.il/~tsirel/download/bellopalg.pdf. [5] U. V. Vazirani and T. Vidick, in Proceedings of [20] V. B. Scholz and R. F. Werner (2008), the 44th Symposium on Theory of Computing Con- arXiv:0812.4305v1.

ference, STOC 2012, New York, NY, USA, May 19 [21] M. McKague, T. H. Yang, and V. Scarani, - 22, 2012, edited by H. J. Karloff and T. Pitassi Journal of Physics A: Mathematical and (ACM, 2012), pp. 61-76, ISBN 978-1-4503-1245-5, URL Theoretical 45, 455304 (2012), URL http://dl.acm.org/citation.cfm?id=2213977. http://stacks.iop.org/1751-8121/45/i=45/a=455304. [6] S. Pironio and S. Massar, Phys. [22] B. W. Reichardt, F. Unger, and U. Vazirani, Nature 496, Rev. A 87, 012336 (2013), URL 456 (2013).

http://link.aps.org/doi/10.1103/PhysRevA.87.012336. [23] C. A. Miller and Y. Shi, in 8th Conference on the [7] S. Fehr, R. Gelles, and C. Schaffner, Theory of Quantum Computation, Communication Phys. Rev. A 87, 012335 (2013), URL and Cryptography, TQC 2013, May 21-23, 2013, http://link.aps.org/doi/10.1103/PhysRevA.87.012335. Guelph, Canada, edited by S. Severini and F. G. S. L. [8] M. Coudron, T. Vidick, and H. Yuen, in Proceedings of Brand˜ao (Schloss Dagstuhl - Leibniz-Zentrum fuer APPROX 2013 and RANDOM 2013 (Springer, 2013), Informatik, 2013), vol. 22 of LIPIcs, pp. 254-262, ISBN vol. 8096 of Lecture Notes in Computer Science, pp. 468- 978-3-939897-55-2, full version: arXiv:1207.1819, URL 483. http://drops.dagstuhl.de/opus/portals/lipics/index.php?sem [9] M. Coudron and H. Yuen, in Proceedings of the 46th An- [24] N. Ozawa, Journal of Mathematical Physics 54 (2013).

nual ACM Symposium on Theory of Computing (2014), [25] M. Coudron and T. Vidick, Proceedings of the 42nd Interpp. 427-436. national Colloquium on Automata, Languages, and Pro[10] C. A. Miller and Y. Shi, in Proceedings of the 46th Annual gramming (ICALP) (2015), chap. Interactive Proofs with ACM Symposium on Theory of Computing (2014), pp. Approximately Commuting Provers, pp. 355-366.

417-426. [26] D. Unruh, J. ACM 62, 49:1 (2015), ISSN 0004-5411, URL [11] C. A. Miller and Y. Shi, Universal security for random- http://doi.acm.org/10.1145/2817206.

ness expansion from the spot-checking protocol (2015), [27] R. Gallego, L. E. Wurflinger, R. Chaves, A. Acin, and arXiv:1411.6608. M. Navascues, New Journal of Physics 16 (2014). [12] M. Pawlowski, Physical Review A 82, 032313 (2010). [28] F. J. Curchod, M. Johansson, M. J. Hoban, P. Wittek, [13] J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and A. Acin, Unbounded randomness certification using and T. Vidick, SIAM Journal on Computing 40, sequences of measurements, arXiv:1510.03394v1 (2015).

Any information missing or wrong?Report an Issue