Quantum games, such as the CHSH game, are used to illustrate the puzzle and power of entanglement. These games are played over many rounds and in each round, the participants, Alice and Bob, each receive a question bit to which they each have to give an answer bit, without being able to communicate during the game. When all possible classical answering strategies are analyzed, it is found that Alice and Bob cannot win more than 75% of the rounds. A higher percentage of wins arguably requires an exploitable bias in the random generation of the question bits or access to "non-local" resources, such as entangled pairs of particles. However, in an actual game, the number of rounds has to be finite and question regimes may come up with unequal likelihood, so there is always a possibility that Alice and Bob win by pure luck. This statistical possibility has to be transparently analyzed for practical applications such as the detection of eavesdropping in quantum communication. Similarly, when Bell tests are used in macroscopic situations to investigate the connection strength between system components and the validity of proposed causal models, the available data are limited and the possible combinations of question bits (measurement settings) may not be controlled to occur with equal likelihood. In the present work, we give a fully self-contained proof for a bound on the probability to win a CHSH game by pure luck without making the usual assumption of only small biases in the random number generators. We also show bounds for the case of unequal probabilities based on results from McDiarmid and Combes and numerically illustrate certain exploitable biases.
Quantum games, such as the CHSH game, are used to illustrate the puzzle and power of entanglement. These games are played over many rounds and in each round, the participants, Alice and Bob, each receive a question bit to which they each have to give an answer bit, without being able to communicate during the game. When all possible classical answering strategies are analyzed, it is found that Alice and Bob cannot win more than 75% of the rounds. A higher percentage of wins arguably requires an exploitable bias in the random generation of the question bits or access to "non-local" resources, such as entangled pairs of particles. However, in an actual game, the number of rounds has to be finite and question regimes may come up with unequal likelihood, so there is always a possibility that Alice and Bob win by pure luck. This statistical possibility has to be transparently analyzed for practical applications such as the detection of eavesdropping in quantum communication. Similarly, when Bell tests are used in macroscopic situations to investigate the connection strength between system components and the validity of proposed causal models, the available data are limited and the possible combinations of question bits (measurement settings) may not be controlled to occur with equal likelihood. In the present work, we give a fully self-contained proof for a bound on the probability to win a CHSH game by pure luck without making the usual assumption of only small biases in the random number generators. We also show bounds for the case of unequal probabilities based on results from McDiarmid and Combes and numerically illustrate certain exploitable biases.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows:
1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy.
2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime.
3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an Ω(n) two-way communication lower bound for distilling n EPR pairs from noisy EPR pairs, in the same nontrivial noise regime.
4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness.
5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.
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.
The recently reported violation of a Bell inequality using entangled electronic spins in diamonds (Hensen et al., Nature 526, 682-686) provided the first loophole-free evidence against local-realist theories of nature. Here we report on data from a second Bell experiment using the same experimental setup with minor modifications. We find a violation of the CHSH-Bell inequality of 2.35 ± 0.18, in agreement with the first run, yielding an overall value of S = 2.38 ± 0.14. We calculate the resulting P-values of the second experiment and of the combined Bell tests. We provide an additional analysis of the distribution of settings choices recorded during the two tests, finding that the observed distributions are consistent with uniform settings for both tests. Finally, we analytically study the effect of particular models of random number generator (RNG) imperfection on our hypothesis test. We find that the winning probability per trial in the CHSH game can be bounded knowing only the mean of the RNG bias. This implies that our experimental result is robust for any model underlying the estimated average RNG bias, for random bits produced up to 690 ns too early by the random number generator.
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work. The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a strategy using a maximally entangled state with local dimension n (e.g., logn EPR-pairs), while we show that the winning probability of any classical strategy differs from 21 by at most O((logn)/n). The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows the game to be won with probability 1/(logn)2, while the best winning probability without entanglement is 1/n. This near-linear ratio is almost optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players. An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity, pages 157--166, 2011.
Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy's paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1−O(d−c) for some c≥0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1−Ω(d−2). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1−Ω(d−2). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.
Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy’s paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1 − O(d−c ) for some c ≥ 0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1 − Ω(d−2 ). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1 − Ω(d−2 ). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.