Bell-inequality violations establish that two systems share some quantum entanglement. We give a simple test to certify that two systems share an asymptotically large amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that play many games, in sequence or in parallel, our test requires only one or two CHSH games. One system is directed to play a CHSH game on a random specified qubit i , and the other is told to play games on qubits {i,j} , without knowing which index is i .The test is robust: a success probability within δ of optimal guarantees distance O(n5/2δ) from n EPR states. However, the test does not tolerate constant δ ; it breaks down for δ=Ω~(1/n) . We give an adversarial strategy that succeeds within delta of the optimum probability using only O~(δ−2) EPR states.
Bell-inequality violations establish that two systems share some quantum entanglement. We give a simple test to certify that two systems share an asymptotically large amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that play many games, in sequence or in parallel, our test requires only one or two CHSH games. One system is directed to play a CHSH game on a random specified qubit i , and the other is told to play games on qubits {i,j} , without knowing which index is i .The test is robust: a success probability within δ of optimal guarantees distance O(n5/2δ) from n EPR states. However, the test does not tolerate constant δ ; it breaks down for δ=Ω~(1/n) . We give an adversarial strategy that succeeds within delta of the optimum probability using only O~(δ−2) EPR states.
We introduce a simple two-player test which certifies that the players apply tensor products of Pauli σX and σZ observables on the tensor product of n EPR pairs. The test has constant robustness: any strategy achieving success probability within an additive of the optimal must be poly(ε)-close, in the appropriate distance measure, to the honest n-qubit strategy. The test involves 2n-bit questions and 2-bit answers. The key technical ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld.
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.
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.
We show that given an explicit description of a multiplayer game, with a classical verifier and a constant number of players, it is QMA-hard, under randomized reductions, to distinguish between the cases when the players have a strategy using entanglement that succeeds with probability 1 in the game, or when no such strategy succeeds with probability larger than 1/2. This proves the “games quantum PCP conjecture” of Fitzsimons and the second author (ITCS'15), albeit under randomized reductions. The core component in our reduction is a construction of a family of two-player games for testing n-qubit maximally entangled states. For any integer n ≥ 2, we give such a game in which questions from the verifier are O(log n) bits long, and answers are poly(loglogn) bits long. We show that for any constant ε ≥ 0, any strategy that succeeds with probability at least 1 - ε in the test must use a state that is within distance δ(ε) = O(εc) from a state that is locally equivalent to a maximally entangled state on n qubits, for some universal constant c > 0. The construction is based on the classical plane-vs-point test for multivariate low-degree polynomials of Raz and Safra (STOC'97). We extend the classical test to the quantum regime by executing independent copies of the test in the generalized Pauli X and Z bases over Fq, where q is a sufficiently large prime power, and combine the two through a test for the Pauli twisted commutation relations. Our main complexity-theoretic result is obtained by combining this family of games with techniques from the classical PCP literature. More specifically, we use constructions of PCPs of proximity introduced by Ben-Sasson et al. (CCC'05), and crucially rely on a linear property of such PCPs. Another consequence of our results is a deterministic reduction from the games quantum PCP conjecture to a suitable formulation of the constraint satisfaction quantum PCP conjecture.
Alice and Bob each have half of a pair of entangled qubits. Bob measures his half and then passes his qubit to a second Bob who measures again and so on. The goal is to maximize the number of Bobs that can have an expected violation of the Clauser-Horne-Shimony-Holt (CHSH) Bell inequality with the single Alice. This scenario was introduced in [R. Silva et al., Phys. Rev. Lett. 114, 250401 (2015)PRLTAO0031-900710.1103/PhysRevLett.114.250401] where the authors mentioned evidence that when the Bobs act independently and with unbiased inputs then at most two of them can expect to violate the CHSH inequality with Alice. Here we show that, contrary to this evidence, arbitrarily many independent Bobs can have an expected CHSH violation with the single Alice. Our proof is constructive and our measurement strategies can be generalized to work with a larger class of two-qubit states that includes all pure entangled two-qubit states. Since violation of a Bell inequality is necessary for device-independent tasks, our work represents a step towards an eventual understanding of the limitations on how much device-independent randomness can be robustly generated from a single pair of qubits.
It is well known that the violation of Bell's inequality in the form given by Clauser, Horne, Shimony, and Holt (CHSH) in two-qubit systems requires entanglement, but not vice versa, i.e., there are entangled states which do not violate the CHSH inequality. Here we compare some standard entanglement measures with violations of the CHSH inequality (as given by the Horodecki measure) for two-qubit states generated by Monte Carlo simulations. We describe states that have extremal entanglement according to the negativity, concurrence, and relative entropy of entanglement for a given value of the CHSH violation. We explicitly find these extremal states by applying the generalized method of Lagrange multipliers based on the Karush-Kuhn-Tucker conditions. The found minimal and maximal states define the range of entanglement accessible for any two-qubit states that violate the CHSH inequality by the same amount. We also find extremal states for the concurrence versus negativity by considering only such states which do not violate the CHSH inequality. Furthermore, we describe an experimentally efficient linear-optical method to determine the highest Horodecki degree of the CHSH violation for arbitrary mixed states of two polarization qubits. By assuming to have access simultaneously to two copies of the states, our method requires only six discrete measurement settings instead of nine settings, which are usually considered.