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.
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.
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.
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 give a test that can distinguish efficiently between product states of n quantum systems and states that are far from product. If applied to a state | ψ 〉 whose maximum overlap with a product state is 1 − ε , the test passes with probability 1 − Θ ( ε ), regardless of n or the local dimensions of the individual systems. The test uses two copies of | ψ 〉. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: QMA( k ) = QMA(2) for k ≥ 2. Building on a previous result of Aaronson et al., this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of Õ (√ n ) qubits. We also show how QMA(2) with log-sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalization of classical linearity testing.
We give a test that can distinguish efficiently between product states of n quantum systems and states which are far from product. If applied to a state |φ) whose maximum overlap with a product state is 1- ε, the test passes with probability 1-Θ(ε), regardless of n or the local dimensions of the individual systems. The test uses two copies of |φ). We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarising channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(k)=QMA(2) for k ≥ 2. Building on a previous result of Aaronson et al, this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of Õ(√n) qubits. Among other consequences, this result implies complexity-theoretic obstructions to finding a polynomial-time algorithm to determine separability of mixed quantum states, even up to constant error, and also to proving "weak" variants of the additivity conjecture for quantum channels. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalisation of classical linearity testing.
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.
We show that the maximum success probability of players sharing quantum entanglement in a two-player game with classical questions of logarithmic length and classical answers of constant length is NP-hard to approximate to within constant factors. As a corollary, the inclusion NEXP⊆MIP∗, first shown in [IV12] with three provers, holds with two provers only. The proof is based on a simpler, improved analysis of the low-degree test Raz and Safra (STOC'97) against two entangled provers.