Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
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(log logn) 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 F q , 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.
2-s2.0-85059817723
Center for Theoretical Physics
California Institute of Technology
2018-11-30
9781538642306
2018-October
8555153
731
742
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
Paris, France | 2018-10-07 - 2018-10-09 | ||
| Funder | Funding(s) | Grant Number | Grant URL |
NSF Physics Frontiers Center | PHY-1125565 | ||
Gordon and Betty Moore Foundation | GBMF-12500028 | ||
AFOSR | FA9550-16-1-0495 | ||
| Show more | |||