Approximation Algorithms for QMA-Complete Problems
Gharibian, Sevag
Kempe, Julia
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.
IEEE
2011
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/8176
Gharibian S, Kempe J. Approximation Algorithms for QMA-Complete Problems. In: <i>IEEE Annual Conference on Computational Complexity (CCC 2011)</i>. IEEE; 2011. doi:<a href="https://doi.org/10.1109/ccc.2011.15">10.1109/ccc.2011.15</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1109/ccc.2011.15
info:eu-repo/semantics/altIdentifier/isbn/9781457701795
info:eu-repo/semantics/altIdentifier/arxiv/1101.3884
info:eu-repo/semantics/openAccess