What can be computed without communications?

Heger Arfaoui 1 Pierre Fraigniaud 1, 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : 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.
Type de document :
Article dans une revue
ACM SIGACT News, Association for Computing Machinery (ACM), 2014, 45 (3), pp.82-104. 〈10.1145/2670418.2670440〉
Liste complète des métadonnées

Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 12 janvier 2015 - 10:11:02
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral




Heger Arfaoui, Pierre Fraigniaud. What can be computed without communications?. ACM SIGACT News, Association for Computing Machinery (ACM), 2014, 45 (3), pp.82-104. 〈10.1145/2670418.2670440〉. 〈hal-01102110〉



Consultations de la notice