# Low-degree testing for quantum states. (arXiv:1801.03821v1 [quant-ph])

For any integer $n\geq 2$ we construct a one-round two-player game $G_n$,

with communication that scales poly-logarithmically with $n$, having the

following properties. First, there exists an entangled strategy that wins with

probability $1$ in $G_n$ and in which the players' outcomes are determined by

performing generalized Pauli measurements on their respective share of an

$n$-qudit maximally entangled state, with qudits of local dimension $q =

\mathrm{poly}\log(n)$. Second, any strategy that succeeds with probability at

least $1-\varepsilon$ in $G_n$ must be within distance $O((\log

n)^c\varepsilon^{1/d})$, for universal constants $c,d\geq 1$, of the perfect

strategy, up to local isometries. This is an exponential improvement on the

size of any previously known game certifying $\Omega(n)$ qudits of entanglement

with comparable robustness guarantees. The construction of the game $G_n$ is

based on the classical test for low-degree polynomials of Raz and Safra, which

we extend to the quantum regime.

Combining this game with a variant of the sum-check protocol, we obtain the

following consequences. First, we show that is QMA-hard, under randomized

reductions, to approximate up to a constant factor the maximum acceptance

probability of a multiround, multiplayer entangled game with

$\mathrm{poly}\log(n)$ bits of classical communication. Second, we give a

quasipolynomial reduction from the multiplayer games quantum PCP conjecture to

the constraint satisfaction quantum PCP conjecture. Third, we design a

multiplayer protocol with polylogarithmic communication and constant

completeness-soundness gap for deciding the minimal energy of a class of

frustration-free nonlocal Hamiltonians up to inverse polynomial accuracy.