Low-degree testing for quantum states, and a quantum entangled games PCP for QMA

Understand

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\geq2$, we give a test in which questions from the verifier are $O(\log n)$ bits long, and answers are $\mathrm{poly}(\log\log n)$ bits long.