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 the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use 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]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.
The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization,
QCPH , uses classical proofs, and the second,
QPH , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level,
QΣ3 , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for
QMA(2) , the variant of Quantum Merlin-Arthur (
QMA ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if
QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in
Ppppp ). Second, because
QMA(2)⊆QΣ3 ,
QMA(2) is strictly contained in NEXP unless
QMA(2)=QΣ3 (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').
The Polynomial-Time Hierarchy (
PH) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however, despite the fact that at least \emph{four} definitions of quantum
PH exist, it has been challenging to prove analogues for these of even basic facts from
PH. This work studies three quantum-verifier based generalizations of
PH, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings (
QCPH) and quantum mixed states (
QPH) as proofs, and one of which is new to this work, utilizing quantum pure states (
pureQPH) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for
QCPH. Then, for our new class
pureQPH, we show one-sided error reduction for
pureQPH, as well as the first bounds relating these quantum variants of
PH, namely
QCPH⊆pureQPH⊆EXPPP.
In this work, we study the computational complexity of quantum determinants, a
q-deformation of matrix permanents: Given a complex number
q on the unit circle in the complex plane and an
n×n matrix
X, the
q-permanent of
X is defined as
Perq(X)=∑σ∈Snqℓ(σ)X1,σ(1)…Xn,σ(n), where
ℓ(σ) is the inversion number of permutation
σ in the symmetric group
Sn on
n elements. The function family generalizes determinant and permanent, which correspond to the cases
q=−1 and
q=1 respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive
m-th root of unity
q for odd prime power
m=pk, exactly computing
q-permanent is
ModpP-hard. This implies that an efficient algorithm for computing
q-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing
q-permanent can be achieved using an oracle that approximates to within a polynomial multiplicative error and a membership oracle for a finite set of algebraic integers. From this, an efficient approximation algorithm would also imply a collapse of the polynomial hierarchy. By random self-reducibility, computing
q-permanent remains to be hard for a wide range of distributions satisfying a property called the strong autocorrelation property. Specifically, this is proved via a reduction from
1-permanent to
q-permanent for
O(1/n2) points
z on the unit circle. Since the family of permanent functions shares common algebraic structure, various techniques developed for the hardness of permanent can be generalized to
q-permanents.