---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
- foaf_Person:
foaf_givenName: Julia
foaf_name: Kempe, Julia
foaf_surname: Kempe
bibo_issue: 5-6
bibo_volume: 14
dct_date: 2014^xs_gYear
dct_language: eng
dct_subject:
- Hardness of approximation
- polynomial time hierarchy
- succinct set cover
- quantum complexity
dct_title: Hardness of approximation for quantum problems@
...