Approximation Algorithms for QMA-Complete Problems

S. Gharibian, J. Kempe, in: IEEE Annual Conference on Computational Complexity (CCC 2011), IEEE, 2011.

Conference Paper | Published | English
Author
;
Department
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.
Publishing Year
Proceedings Title
IEEE Annual Conference on Computational Complexity (CCC 2011)
Conference
2011 IEEE 26th Annual Conference on Computational Complexity (CCC)
Conference Location
San Jose, USA
LibreCat-ID

Cite this

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
Gharibian, S., & Kempe, J. (2011). Approximation Algorithms for QMA-Complete Problems. In IEEE Annual Conference on Computational Complexity (CCC 2011). San Jose, USA: IEEE. https://doi.org/10.1109/ccc.2011.15
@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} }
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.
S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” in IEEE Annual Conference on Computational Complexity (CCC 2011), San Jose, USA, 2011.
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.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data LibreCat

Sources

arXiv 1101.3884

Search this title in

Google Scholar
ISBN Search