{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:52Z","timestamp":1759638832762,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,9,17]],"date-time":"2014-09-17T00:00:00Z","timestamp":1410912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2014,9,17]]},"abstract":"<jats:p>The main objective of this paper is to provide illustrative examples of distributed computing problems for which it is possible to design tight lower bounds for quantum algorithms without having to manipulate concepts from quantum mechanics, at all. As a case study, we address the following class of 2-player problems. Alice (resp., Bob) receives a boolean x (resp., y) as input, and must return a boolean a (resp., b) as output. A game between Alice and Bob is defined by a pair (?, f) of boolean functions. The objective of Alice and Bob playing game (?, f) is, for every pair (x, y) of inputs, to output values a and b, respectively, satisfying ?(a, b) = f(x, y), in absence of any communication between the two players, but in presence of shared resources. The ability of the two players to solve the game then depends on the type of resources they share. It is known that, for the so-called CHSH game, i.e., for the game a ? b = x ? y, the ability for the players to use entangled quantum bits (qubits) helps. We show that, apart from the CHSH game, quantum correlations do not help, in the sense that, for every game not equivalent to the CHSH game, there exists a classical protocol (using shared randomness) whose probability of success is at least as large as the one of any protocol using quantum resources. This result holds for both worst case and average case analysis. It is achieved by considering a model stronger than quantum correlations, the non-signaling model, which subsumes quantum mechanics, but is far easier to handle.<\/jats:p>","DOI":"10.1145\/2670418.2670440","type":"journal-article","created":{"date-parts":[[2014,9,19]],"date-time":"2014-09-19T12:27:17Z","timestamp":1411129637000},"page":"82-104","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["What can be computed without communications?"],"prefix":"10.1145","volume":"45","author":[{"given":"Heger","family":"Arfaoui","sequence":"first","affiliation":[{"name":"CNRS and University Paris Diderot"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[{"name":"CNRS and University Paris Diderot"}]}],"member":"320","published-online":{"date-parts":[[2014,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31104-8_12"},{"key":"e_1_2_1_3_1","volume-title":"Local Decision and Verification with Bounded--Size Outputs. In proc. 15th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS)","author":"Arfaoui H.","year":"2013","unstructured":"H. Arfaoui , P. Fraigniaud , and A. Pelc . Local Decision and Verification with Bounded--Size Outputs. In proc. 15th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS) , 2013 . H. Arfaoui, P. Fraigniaud, and A. Pelc. Local Decision and Verification with Bounded--Size Outputs. In proc. 15th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), 2013."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536432"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022101"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.140401"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_2_1_9_1","first-page":"18771907","article-title":"Quantum pseudo-telepathy","volume":"5","author":"Brassard G.","year":"2005","unstructured":"G. Brassard , A. Broadbent , and A. Tapp . Quantum pseudo-telepathy . Foundations of Physics 5 : 18771907 , 2005 . G. Brassard, A. Broadbent, and A. Tapp. Quantum pseudo-telepathy. Foundations of Physics 5:18771907, 2005.","journal-title":"Foundations of Physics"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412717"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.82.665"},{"key":"e_1_2_1_12_1","first-page":"120","volume-title":"Distributed Quantum Computing. In proc 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 2747","author":"Buhrman H.","year":"2003","unstructured":"H. Buhrman and H. R\u00f6hrig . Distributed Quantum Computing. In proc 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 2747 , pp. 120 , 2003 . H. Buhrman and H. R\u00f6hrig. Distributed Quantum Computing. In proc 28th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 2747, pp. 120, 2003."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00417500"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-012-9353-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412718"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400788"},{"issue":"082107","key":"e_1_2_1_18_1","article-title":"No nonlocal box is universal","volume":"48","author":"Dupuis F.","year":"2007","unstructured":"F. Dupuis , N. Gisin , A. Hasidim , A. Allan M\u00e9thot , and H. Pilpel . No nonlocal box is universal . J. Math. Phys. 48 ( 082107 ), 2007 . F. Dupuis, N. Gisin, A. Hasidim, A. Allan M\u00e9thot, and H. Pilpel. No nonlocal box is universal. J. Math. Phys. 48(082107), 2007.","journal-title":"J. Math. Phys."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.47.777"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281128"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.17"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2075029.2075074"},{"key":"e_1_2_1_24_1","volume-title":"An Impossibility Result for Run-Time Monitoring. Submitted","author":"Fraigniaud P.","year":"2013","unstructured":"P. Fraigniaud , S. Rajsbaum , and C. Travers . An Impossibility Result for Run-Time Monitoring. Submitted , 2013 . P. Fraigniaud, S. Rajsbaum, and C. Travers. An Impossibility Result for Run-Time Monitoring. Submitted, 2013."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.28.938"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v54:1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813164.1813197"},{"key":"e_1_2_1_28_1","first-page":"293","article-title":"and Weber, T. A general argument against superluminal transmission through the quantum mechanical measurement process Lett","volume":"27","author":"Rimini G. C.","year":"1980","unstructured":"Ghirardi, G. C. and Rimini , A . and Weber, T. A general argument against superluminal transmission through the quantum mechanical measurement process Lett . Nuovo Cimento 27 : 293 -- 298 , 1980 . Ghirardi, G. C. and Rimini, A. and Weber, T. A general argument against superluminal transmission through the quantum mechanical measurement process Lett. Nuovo Cimento 27:293--298, 1980.","journal-title":"Nuovo Cimento"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011811"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed computing: A locality-sensitive approach","author":"Peleg D.","year":"2000","unstructured":"D. Peleg . Distributed computing: A locality-sensitive approach . SIAM , 2000 . D. Peleg. Distributed computing: A locality-sensitive approach. SIAM, 2000."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02058098"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2670418.2670440","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2670418.2670440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:20Z","timestamp":1750231160000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2670418.2670440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,17]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9,17]]}},"alternative-id":["10.1145\/2670418.2670440"],"URL":"https:\/\/doi.org\/10.1145\/2670418.2670440","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2014,9,17]]},"assertion":[{"value":"2014-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}