Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
 
conference paper

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

Natarajan, Anand
•
Vidick, Thomas  orcid-logo
Thorup, Mikkel
November 30, 2018
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018)

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(log logn) 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 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 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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/FOCS.2018.00075
Scopus ID

2-s2.0-85059817723

Author(s)
Natarajan, Anand

Center for Theoretical Physics

Vidick, Thomas  orcid-logo

California Institute of Technology

Editors
Thorup, Mikkel
Date Issued

2018-11-30

Publisher

IEEE Computer Society

Published in
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
ISBN of the book

9781538642306

Book part number

2018-October

Article Number

8555153

Start page

731

End page

742

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018)

Paris, France

2018-10-07 - 2018-10-09

FunderFunding(s)Grant NumberGrant URL

NSF Physics Frontiers Center

PHY-1125565

Gordon and Betty Moore Foundation

GBMF-12500028

AFOSR

FA9550-16-1-0495

Show more
Available on Infoscience
November 21, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256156
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés