Hardness of approximation for quantum problems

Understand

The polynomial hierarchy plays a central role in classical complexity theory.

• Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study.
• We show that not 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 these techniques, we also obtain hardness of approximation for the class QCMA.