---
_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: <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>'
  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>
  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} }'
  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>.
  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>.'
  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>.
  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'
...