@inproceedings{8176,
  abstract     = {{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.}},
  author       = {{Gharibian, Sevag and Kempe, Julia}},
  booktitle    = {{IEEE Annual Conference on Computational Complexity (CCC 2011)}},
  isbn         = {{9781457701795}},
  location     = {{San Jose, USA}},
  publisher    = {{IEEE}},
  title        = {{{Approximation Algorithms for QMA-Complete Problems}}},
  doi          = {{10.1109/ccc.2011.15}},
  year         = {{2011}},
}