A Caltech Library Service

Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA

Natarajan, Anand and Vidick, Thomas (2018) Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 731-742. ISBN 9781538642306.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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(loglogn) 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 Fq, 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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2018 IEEE. AN was supported by NSF CAREER Grant CCF-1452616. TV was supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-10495, a CIFAR Azrieli Global Scholar award, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). Parts of this work was completed while both authors were hosted at the Institut Henri Poincaré in Paris, as part of the special semester on Analysis in Quantum Information Theory (Fall 2017), supported by NSF Grant DMS-1700168. The hospitality of the IHP is gratefully acknowledged.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-10495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Record Number:CaltechAUTHORS:20190201-143229217
Persistent URL:
Official Citation:A. Natarajan and T. Vidick, "Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA," 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), Paris, 2018, pp. 731-742. doi: 10.1109/FOCS.2018.00075
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:92584
Deposited By: George Porter
Deposited On:01 Feb 2019 22:55
Last Modified:16 Nov 2021 03:51

Repository Staff Only: item control page