--- _id: '8176' abstract: - lang: eng text: 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: - first_name: Sevag full_name: Gharibian, Sevag id: '71541' last_name: Gharibian orcid: 0000-0002-9992-3379 - first_name: Julia full_name: Kempe, Julia last_name: Kempe citation: ama: 'Gharibian S, Kempe J. Approximation Algorithms for QMA-Complete Problems. In: IEEE Annual Conference on Computational Complexity (CCC 2011). IEEE; 2011. doi:10.1109/ccc.2011.15' apa: Gharibian, S., & Kempe, J. (2011). Approximation Algorithms for QMA-Complete Problems. IEEE Annual Conference on Computational Complexity (CCC 2011). 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), San Jose, USA. https://doi.org/10.1109/ccc.2011.15 bibtex: '@inproceedings{Gharibian_Kempe_2011, title={Approximation Algorithms for QMA-Complete Problems}, DOI={10.1109/ccc.2011.15}, booktitle={IEEE Annual Conference on Computational Complexity (CCC 2011)}, publisher={IEEE}, author={Gharibian, Sevag and Kempe, Julia}, year={2011} }' chicago: Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” In IEEE Annual Conference on Computational Complexity (CCC 2011). IEEE, 2011. https://doi.org/10.1109/ccc.2011.15. ieee: 'S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” presented at the 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), San Jose, USA, 2011, doi: 10.1109/ccc.2011.15.' mla: Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011, doi:10.1109/ccc.2011.15. short: 'S. Gharibian, J. Kempe, in: IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011.' conference: location: San Jose, USA name: 2011 IEEE 26th Annual Conference on Computational Complexity (CCC) date_created: 2019-03-01T12:06:18Z date_updated: 2023-02-28T11:04:02Z department: - _id: '623' - _id: '7' doi: 10.1109/ccc.2011.15 extern: '1' external_id: arxiv: - '1101.3884' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1101.3884 oa: '1' publication: IEEE Annual Conference on Computational Complexity (CCC 2011) publication_identifier: isbn: - '9781457701795' publication_status: published publisher: IEEE status: public title: Approximation Algorithms for QMA-Complete Problems type: conference user_id: '71541' year: '2011' ...