ACM Symposium on Principles of Distributed Computing (PODC)

Brief announcement

Heger Arfaoui, Pierre Fraigniaud

Published Jul 16, 2012• 0 citations

Abstract

When playing the boolean game (δ,f), two players, upon reception of respective inputs x and y, must respectively output a and b satisfying δ(a, b)=f(x, y), in absence of any communication. It is known that, for δ(a, b)=a ⊕ b, the ability for the players to use entangled quantum bits (qbits) helps. In this paper, we show that, for δ different from the exclusive-or operator, quantum correlations do not help. This result is an invitation to revisit the theory of distributed checking, a.k.a. distributed verification, currently sticked to the usage of decision functions δ based on the AND-operator, hence potentially preventing us from using the potential benefit of quantum effects.

DOI: 10.1145/2332432.2332446

Related papers

What can be computed without communications?

Heger Arfaoui, Pierre Fraigniaud

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.

ACM SIGACT NewsSep 17, 201414 citations

How Quantum Entanglement Helps to Coordinate Non-Communicating Players

G.V. Klimovitch

We consider a coalitional game with the same payoff for all players. To maximize the payoff, the players need to use one collective strategy, if all players are in certain states, and the other strategy otherwise. The current state of each player changes according to external conditions and is not known to the other players. In one example of such a game, quantum entanglement between players results in the optimal payoff thrice the maximal payoff for unentangled players.

arXiv:quant-ph/0405093May 17, 20041 citation

The Impossibility of Pseudo-Telepathy Without Quantum Entanglement

Viktor Galliard, Stefan Wolf, Alain Tapp

Imagine that Alice and Bob, unable to communicate, are both given a 16-bit string such that the strings are either equal, or they differ in exactly 8 positions. Both parties are then supposed to output a 4-bit string in such a way that these short strings are equal if and only if the original longer strings given to them were equal as well. It is known that this task can be fulfilled without failure and without communication if Alice and Bob share 4 maximally entangled quantum bits. We show that, on the other hand, they CANNOT win the same game with certainty if they only share classical bits, even if it is an unlimited number. This means that for fulfilling this particular distributed task, quantum entanglement can completely replace communication. This phenomenon has been called pseudo-telepathy. The results of this paper complete the analysis of the first proposed game of this type between two players.

arXiv:quant-ph/0211011Nov 4, 200220 citations

Secure bits with quantum pseudo-telepathy

Tobias AmbÃ ⁄ hl

Motivated by the concept of quantum pseudo-telepathy games as well as by quantum key distribution protocols such as [1], the security of which is based on the non-signaling principle, we try to answer the question wheather it is possible to generate a perfectly secure, shared bit between two parties by a single usage of quantum correlations and a performance of local operations on the input and output.We provide both parties with some prior shared entanglement and the possibility of postselection, e.g.discard of inputs and outputs, aiming to prevent any eavesdropper bound by the non-signaling condition from successfully performing an attack.After, in a first step, defining the framework and setting up the requirements we are going to see that quantum mechanics does not allow for a physical simulation of such correlations.For the case of binary output we will even see that, in order to make perfectly correlated bits perfectly secure, we would need maximal nonlocal correlations which also prohibits a quantum physical representation.

Jan 1, 20090 citations

Absolute nonlocality via distributed computing without communication

Łukasz Czekaj, Marcin Pawłowski, Tamás Vértesi +3 more

Understanding the role that quantum entanglement plays as a resource in various information processing tasks is one of the crucial goals of quantum information theory. Here we propose an alternative perspective for studying quantum entanglement: distributed computation of functions without communication between nodes. To formalize this approach, we propose identity games. Surprisingly, despite no signaling, we obtain that nonlocal quantum strategies beat classical ones in terms of winning probability for identity games originating from certain bipartite and multipartite functions. Moreover we show that, for a majority of functions, access to general nonsignaling resources boosts success probability two times in comparison to classical ones for a number of large enough outputs. Because there are no constraints on the inputs and no processing of the outputs in the identity games, they detect very strong types of correlations: absolute nonlocality.

arXiv:1408.0993Physical Review ASep 18, 20151 citation

The Role of Correlation in Quantum and Classical Games

Simon J. D. Phoenix, Faisal Shah Khan

We use the example of playing a 2-player game with entangled quantum objects to investigate the effect of quantum correlation. We find that for simple game scenarios it is classical correlation that is the central feature and that these simple quantum games are not sensitive to the quantum part of the correlation. In these games played with quantum objects it is possible to transform a game such as Prisoner's Dilemma into the game of Chicken. We show that this behaviour, and the associated enhanced equilibrium payoff over playing the game with quantum objects in non-entangled states, is entirely due to the classical part of the correlation. Generalizing these games to the pure strategy 2-player quantum game where the players have finite strategy sets and a projective joint measurement is made on the output state produced by the players, we show that a given quantum game of this form can always be reproduced by a classical model, such as a communication channel. Where entanglement is a feature of the these 2-player quantum games the matrix of expected outcomes for the players can be reproduced by a classical channel with correlated noise.

arXiv:1209.5332Sep 24, 20120 citations