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.
A team of students has been given a challenging physics exam: find the ground energy of a complicated, n-spin system. Even if they succeed, how can the examiners be sure that their answer is correct without physically measuring all n spins of the ground state, or worse, having to read a description of the 2n components of its wavefunction? The main result of this thesis is a protocol such that, if the examiners are allowed to separately interrogate multiple students, they can be confident that the students possess the n-spin ground state as well as learn its energy to high precision, after exchanging just O(log(n)) bits of classical communication with the students! The protocol and its analysis combine classical computer science techniques for efficiently checking proofs with Bell inequalities. Stated more formally, the main result of this thesis is a multi-prover interactive proof protocol, in which a classical verifier exchanging only O(log(n)) bits of classical communication with 7 untrusted, entangled provers can certify that they share between them an encoding of an n-qubit quantum state Ib), and estimate its energy under a local Hamiltonian H to high (1/ poly(n)) precision. As a consequence, we show that, under poly-time randomized reductions, it is QMA-hard to estimate the entangled value of a nonlocal game up to constant error, proving the quantum entangled games PCP conjecture of Fitzsimons and Vidick. Our main technical innovations are two constructions of robust self-tests for entanglement: two-player nonlocal games where to succeed with probability E-close to 1, the players must share a state that is [delta] = poly([epsilon])-close in trace distance to n EPR pairs. These tests are robust in that [delta] is independent of the number n of EPR pairs being tested. Our techniques draw heavily on the original, "algebraic" proof of the PCP theorem in classical complexity theory, and in particular, each of our robust self-tests is based on a classical locally-testable error correcting code: the first on the Hadamard code and the associated linearity test of Blum, Luby, and Rubinfeld, and the second on Reed-Muller code and the associated low-degree test of Raz and Safra.
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.