Approximation algorithms for QMA-complete problems

Sevag Gharibian, Julia Kempe

Research output: Contribution to journalArticlepeer-review


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 (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial 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, Karger, and Karpinski [J. Comput. System Sci., 58(1999), p. 193] to the quantum setting and might be of independent interest.

Original languageEnglish (US)
Pages (from-to)1028-1050
Number of pages23
JournalSIAM Journal on Computing
Issue number4
StatePublished - 2012


  • Approximation algorithm
  • Constraint satisfaction
  • Local Hamiltonian
  • QMA-complete

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


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

Cite this