---
_id: '8171'
abstract:
- lang: eng
  text: "The polynomial hierarchy plays a central role in classical complexity theory.
    Here, we define\r\na quantum generalization of the polynomial hierarchy, and initiate
    its study. We show that\r\nnot only are there natural complete problems for the
    second level of this quantum hierarchy, but that these problems are in fact hard
    to approximate. Using the same techniques, we\r\nalso obtain hardness of approximation
    for the class QCMA. Our approach is based on the\r\nuse of dispersers, and is
    inspired by the classical results of Umans regarding hardness of approximation
    for the second level of the classical polynomial hierarchy [Umans, FOCS 1999].\r\nThe
    problems for which we prove hardness of approximation for include, among others,
    a\r\nquantum version of the Succinct Set Cover problem, and a variant of the local
    Hamiltonian\r\nproblem with hybrid classical-quantum ground states."
article_type: original
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. Hardness of approximation for quantum problems. <i>Quantum
    Information &#38; Computation</i>. 2014;14(5-6):517-540.
  apa: Gharibian, S., &#38; Kempe, J. (2014). Hardness of approximation for quantum
    problems. <i>Quantum Information &#38; Computation</i>, <i>14</i>(5–6), 517–540.
  bibtex: '@article{Gharibian_Kempe_2014, title={Hardness of approximation for quantum
    problems}, volume={14}, number={5–6}, journal={Quantum Information &#38; Computation},
    author={Gharibian, Sevag and Kempe, Julia}, year={2014}, pages={517–540} }'
  chicago: 'Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum
    Problems.” <i>Quantum Information &#38; Computation</i> 14, no. 5–6 (2014): 517–40.'
  ieee: S. Gharibian and J. Kempe, “Hardness of approximation for quantum problems,”
    <i>Quantum Information &#38; Computation</i>, vol. 14, no. 5–6, pp. 517–540, 2014.
  mla: Gharibian, Sevag, and Julia Kempe. “Hardness of Approximation for Quantum Problems.”
    <i>Quantum Information &#38; Computation</i>, vol. 14, no. 5–6, 2014, pp. 517–40.
  short: S. Gharibian, J. Kempe, Quantum Information &#38; Computation 14 (2014) 517–540.
date_created: 2019-03-01T11:56:55Z
date_updated: 2023-02-28T11:02:47Z
department:
- _id: '623'
- _id: '7'
extern: '1'
external_id:
  arxiv:
  - '1209.1055'
intvolume: '        14'
issue: 5-6
keyword:
- Hardness of approximation
- polynomial time hierarchy
- succinct set cover
- quantum complexity
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1209.1055
oa: '1'
page: 517-540
publication: Quantum Information & Computation
publication_status: published
status: public
title: Hardness of approximation for quantum problems
type: journal_article
user_id: '71541'
volume: 14
year: '2014'
...