Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Entropy

Winning a CHSH Game without Entangled Particles in a Finite Number of Biased Rounds: How Much Luck Is Needed?

Christoph Gallus, Paweł Błasiak, Emmanuel M. Pothos

Published May 21, 2023• 1 citation
Publisher

Abstract

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.

DOI
10.3390/e25050824

Related papers

Non-local games and communication complexity with noisy entanglement

Srijita Kundu, Olivier Lalonde

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.

quant-pharXiv:2609.05122•Sep 7, 2026•2 citations

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 News•Sep 17, 2014•29 citations

Loophole-free Bell test using electron spins in diamond: second experiment and additional analysis

Bas Hensen, Norbert Kalb, Machiel Blok +11 more

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.

arXiv:1603.05705•Scientific Reports•Aug 11, 2016•100 citations

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa +1 more

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., $\log n$ EPR-pairs), while we show that the winning probability of any classical strategy differs from $\frac{1}{2}$ by at most $O((\log n)/\sqrt{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/(\log n)^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.

arXiv:1012.5043•Theory of Computing•Jan 1, 2012•33 citations

Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman, Oded Regev, Giannicola Scarpa +1 more

Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. 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 quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√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 to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-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.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2011•48 citations

Analyzing asymmetric nonlocality experiments with relaxed conditions

Daniel Dilley

It is already known that one can always find a set of measurements on any two-qubit entangled state that will lead to a violation of the CHSH inequality. We provide an explicit state in terms of the angle between Alice's choice of measurements and the angle between Bob's choice of measurements, such that the CHSH inequality is always violated provided Alice's or Bob's choice of inputs are not collinear. We prove that inequalities with a corresponding Bell operator written as a linear combination of tensor products of Pauli matrices, excluding the identity, will generate the most nonlocal correlations using maximally entangled states in our experiment. From this result and a proposition from Horodecki et. al., we are able to construct the state that generates these optimal correlations. To achieve this state in a lab, one party must rotate their qubit using the orthogonal operation we provide and also rotate their Bloch sphere such that all their measurements lie in the same plane. We provide a comprehensive study of how Bell inequalities change when experiments introduce error via imperfect detection efficiency. The original cases of perfect efficiency are covered first and then a more realistic approach, when inefficient detectors are used, will follow. It is shown that less entanglement is needed to demonstrate more nonlocality in some Clasure-Horne-Shimony-Holt (CHSH) experiments when detector inefficiency is introduced. An example of this is shown for any given specific set of measurements in the CHSH Bell experiment. This occurs when one party has a detector of efficiency for each choice of input and the other party makes projective measurements. The efficiency can be pushed down to fifty percent while still violating the CHSH inequality, and for the experimental set-up illustrated, there is more nonlocality with less entanglement. Furthermore, it is shown that if the first party has an imperfect detector for only one choice of inputs rather than two, the efficiency can be brought down arbitrarily close to zero percent while still violating the CHSH inequality. Historically, nonlocality and entanglement were viewed as two equivalent resources, but recently this equality has come under question; these results further support this fundamental difference. Further more, we introduce Mermin's game in the case of relaxed conditions. The original constraints were that when the detectors in separate labs of a two-qubit experiment are in the same setting, then the results should be the same. We require that the outcomes are the same at least part of the time, given by some epsilon variable. Initially, one could find a maximum violation of one-fourth by allowing to parties to share the singlet state and have measurement settings one-hundred and twenty degrees apart from one another. By allowing some epsilon error in the perfect correlations regime, one can find a maximum violation of minus one plus the square root of two using the singlet state and measurement inputs that achieve Tsirelson's bound for the CHSH experiment. The reason is that we show Mermin's inequality is technically the CHSH inequality "in disguise", but with using constraints the CHSH experiment does not use. We derive Mermin's inequality under new conditions and give the projective measurements needed to violate maximally.

•Jan 1, 2019•0 citations
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)Ω(n)Ω(n) two-way communication lower bound for distilling nnn 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 nnn (e.g., log⁡n\log nlogn EPR-pairs), while we show that the winning probability of any classical strategy differs from 12\frac{1}{2}21​ by at most O((log⁡n)/n)O((\log n)/\sqrt{n})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 nnn-dimensional entanglement allows the game to be won with probability 1/(log⁡n)21/(\log n)^21/(logn)2, while the best winning probability without entanglement is 1/n1/n1/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.
Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. 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 quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√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 to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-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.
It is already known that one can always find a set of measurements on any two-qubit entangled state that will lead to a violation of the CHSH inequality. We provide an explicit state in terms of the angle between Alice's choice of measurements and the angle between Bob's choice of measurements, such that the CHSH inequality is always violated provided Alice's or Bob's choice of inputs are not collinear. We prove that inequalities with a corresponding Bell operator written as a linear combination of tensor products of Pauli matrices, excluding the identity, will generate the most nonlocal correlations using maximally entangled states in our experiment. From this result and a proposition from Horodecki et. al., we are able to construct the state that generates these optimal correlations. To achieve this state in a lab, one party must rotate their qubit using the orthogonal operation we provide and also rotate their Bloch sphere such that all their measurements lie in the same plane. We provide a comprehensive study of how Bell inequalities change when experiments introduce error via imperfect detection efficiency. The original cases of perfect efficiency are covered first and then a more realistic approach, when inefficient detectors are used, will follow. It is shown that less entanglement is needed to demonstrate more nonlocality in some Clasure-Horne-Shimony-Holt (CHSH) experiments when detector inefficiency is introduced. An example of this is shown for any given specific set of measurements in the CHSH Bell experiment. This occurs when one party has a detector of efficiency for each choice of input and the other party makes projective measurements. The efficiency can be pushed down to fifty percent while still violating the CHSH inequality, and for the experimental set-up illustrated, there is more nonlocality with less entanglement. Furthermore, it is shown that if the first party has an imperfect detector for only one choice of inputs rather than two, the efficiency can be brought down arbitrarily close to zero percent while still violating the CHSH inequality. Historically, nonlocality and entanglement were viewed as two equivalent resources, but recently this equality has come under question; these results further support this fundamental difference. Further more, we introduce Mermin's game in the case of relaxed conditions. The original constraints were that when the detectors in separate labs of a two-qubit experiment are in the same setting, then the results should be the same. We require that the outcomes are the same at least part of the time, given by some epsilon variable. Initially, one could find a maximum violation of one-fourth by allowing to parties to share the singlet state and have measurement settings one-hundred and twenty degrees apart from one another. By allowing some epsilon error in the perfect correlations regime, one can find a maximum violation of minus one plus the square root of two using the singlet state and measurement inputs that achieve Tsirelson's bound for the CHSH experiment. The reason is that we show Mermin's inequality is technically the CHSH inequality "in disguise", but with using constraints the CHSH experiment does not use. We derive Mermin's inequality under new conditions and give the projective measurements needed to violate maximally.