@inproceedings{1fd6d241c63e49e08c9d37f59ea7d5d9,

title = "Approximation algorithms for QMA-complete problems",

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.",

keywords = "Approximation algorithms, Exhaustive sampling, Local Hamiltonian, QMA-complete",

author = "Sevag Gharibian and Julia Kempe",

note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 26th Annual IEEE Conference on Computational Complexity, CCC 2011 ; Conference date: 08-06-2011 Through 10-06-2011",

year = "2011",

doi = "10.1109/CCC.2011.15",

language = "English (US)",

isbn = "9780769544113",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "178--188",

booktitle = "Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011",

}