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

Abstract

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\ge 2$, 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. We show that for any constant $\epsilon \ge 0$, any strategy that succeeds with probability at least $1-\epsilon$ in the test must use a state that is within distance $O({\epsilon }^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 ${\mathbb{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 constructions of PCPs of proximity introduced by Ben-Sasson et al. (CCC'05), and crucially relies 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 Hamiltonian quantum PCP conjecture.

59 pages. Game sized reduced from quasipolynomial to polynomial, yielding improved complexity-theoretic results

References in corpus (5)

• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• Almost commuting matrices with respect to normalized Hilbert-Schmidt norm
• Robust self-testing for linear constraint system games
• The Parallel-Repeated Magic Square Game is Rigid
• Compression of Quantum Multi-Prover Interactive Proofs

Cited by in corpus (21)

• Self-testing of quantum systems: a review
• Warm-starting quantum optimization
• NLTS Hamiltonians from good quantum codes
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Towards local testability for quantum coding
• Device-independent certification of tensor products of quantum states using single-copy self-testing protocols
• Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis
• Quantum soundness of the classical low individual degree test
• Parallel Self-Testing of the GHZ State with a Proof by Diagrams
• Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
• Constant-sized correlations are sufficient to robustly self-test maximally entangled states with unbounded dimension
• A generalization of CHSH and the algebraic structure of optimal strategies
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• Sumcheck-based delegation of quantum computing to rational server
• Towards a quantum-inspired proof for IP = PSPACE
• Practical parallel self-testing of Bell states via magic rectangles
• Counterexamples in self-testing
• The membership problem for constant-sized quantum correlations is undecidable
• On Information-Theoretic Classical Verification of Quantum Computers
• Quantum dimension test using the uncertainty principle