---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
- foaf_Person:
foaf_givenName: Julia
foaf_name: Kempe, Julia
foaf_surname: Kempe
bibo_doi: 10.1109/ccc.2011.15
dct_date: 2011^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/9781457701795
dct_language: eng
dct_publisher: IEEE@
dct_title: Approximation Algorithms for QMA-Complete Problems@
...