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.

Article web page: