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