A lattice problem in quantum NP

D. Aharonov, O. Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider coGapSVP√n, a gap version of the shortest vector in a lattice problem. This problem is known to be in AM ∩ coNP but is not known to be in NP or in MA. We prove that it lies inside QMA, the quantum analogue of NP. This is the first non-trivial upper bound on the quantum complexity of a lattice problem. The proof relies on two novel ideas. First, we give a new characterization of QMA, called QMA+ formulation allows us to circumvent a problem which arises commonly in the context of QMA: the prover might use entanglement between different copies of the same state in order to cheat. The second idea involves using estimations of autocorrelation functions for verification. We make the important observation that autocorrelation functions are positive definite functions and using properties of such functions we severely restrict the prover's possibility to cheat. We hope that these ideas will lead to further developments in the field.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
PublisherIEEE Computer Society
Number of pages10
ISBN (Print)0769520405
StatePublished - 2003
Event44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States
Duration: Oct 11 2003Oct 14 2003


Other44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
Country/TerritoryUnited States


  • Algorithm design and analysis
  • Autocorrelation
  • Computer science
  • Cryptography
  • Lattices
  • Polynomials
  • Quantum computing
  • Quantum mechanics
  • Upper bound

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'A lattice problem in quantum NP'. Together they form a unique fingerprint.

Cite this