Approximation Algorithms for QMA-Complete Problems

S. Gharibian, J. Kempe, SIAM Journal on Computing 41 (2012) 1028–1050.

Journal Article | 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 (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial 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, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.
Publishing Year
Journal Title
SIAM Journal on Computing
Volume
41
Issue
4
Page
1028-1050
LibreCat-ID

Cite this

Gharibian S, Kempe J. Approximation Algorithms for QMA-Complete Problems. SIAM Journal on Computing. 2012;41(4):1028-1050. doi:10.1137/110842272
Gharibian, S., & Kempe, J. (2012). Approximation Algorithms for QMA-Complete Problems. SIAM Journal on Computing, 41(4), 1028–1050. https://doi.org/10.1137/110842272
@article{Gharibian_Kempe_2012, title={Approximation Algorithms for QMA-Complete Problems}, volume={41}, DOI={10.1137/110842272}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Kempe, Julia}, year={2012}, pages={1028–1050} }
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” SIAM Journal on Computing 41, no. 4 (2012): 1028–50. https://doi.org/10.1137/110842272.
S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,” SIAM Journal on Computing, vol. 41, no. 4, pp. 1028–1050, 2012.
Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete Problems.” SIAM Journal on Computing, vol. 41, no. 4, Society for Industrial & Applied Mathematics (SIAM), 2012, pp. 1028–50, doi:10.1137/110842272.

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