Approximation algorithms for QMA-complete problems

Sevag Gharibian, Julia Kempe

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


Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem and initiate its study. We present two main results. The first shows that a non-trivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one), gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora et al. [J. Comp. Sys. Sci. 58, p. 193 (1999)] to the quantum setting, and might be of independent interest.

Original languageEnglish (US)
Title of host publicationProceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011
Number of pages11
StatePublished - 2011
Event26th Annual IEEE Conference on Computational Complexity, CCC 2011 - San Jose, CA, United States
Duration: Jun 8 2011Jun 10 2011

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159


Other26th Annual IEEE Conference on Computational Complexity, CCC 2011
Country/TerritoryUnited States
CitySan Jose, CA


  • Approximation algorithms
  • Exhaustive sampling
  • Local Hamiltonian
  • QMA-complete

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Computational Mathematics


Dive into the research topics of 'Approximation algorithms for QMA-complete problems'. Together they form a unique fingerprint.

Cite this