Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Information and Computation

Hardness of approximation for quantum problems

GharibianSevag, KempeJulia

Published Apr 1, 2014• 0 citations
Publisher

Abstract

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...
DOI
10.5555/2638661.2638669

Related papers

Hardness of approximation for quantum problems

Sevag Gharibian, Julia Kempe

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.

Quantum Information and Computation•May 1, 2014•3 citations

BQP and the polynomial hierarchy

Scott Aaronson

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

ACM Symposium on Theory of Computing (STOC)•Jun 5, 2010•255 citations

Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

Sevag Gharibian, Miklós Sántha, Jamie Sikora +2 more

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, $$\rm{QCPH}$$ , uses classical proofs, and the second, $$\rm{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, $$\rm{Q\Sigma_3}$$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $$\rm{QMA(2)}$$ , the variant of Quantum Merlin-Arthur ( $$\rm{QMA}$$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $$\rm{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 $${\rm P}^{{\rm pp}^{{\rm pp}}}$$ ). Second, because $$\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$$ , $$\rm{QMA(2)}$$ is strictly contained in NEXP unless $$\rm{QMA(2)}=\rm{Q\Sigma_3}$$ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').

arXiv:1805.11139•Computational Complexity•Sep 20, 2022•25 citations

Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds

Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1 more

The Polynomial-Time Hierarchy ($\mathsf{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 $\mathsf{PH}$ exist, it has been challenging to prove analogues for these of even basic facts from $\mathsf{PH}$. This work studies three quantum-verifier based generalizations of $\mathsf{PH}$, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings ($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one of which is new to this work, utilizing quantum pure states ($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided error reduction for $\mathsf{pureQPH}$, as well as the first bounds relating these quantum variants of $\mathsf{PH}$, namely $\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$.

arXiv:2401.01633•Leibniz international proceedings in informatics•Jan 1, 2024•9 citations

The Computational Complexity of Quantum Determinants

Hung, Shih-Han, En-Jui Kuo

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\times n$ matrix $X$, the $q$-permanent of $X$ is defined as $$\mathrm{Per}_q(X) = \sum_{σ\in S_n} q^{\ell(σ)}X_{1,σ(1)}\ldots X_{n,σ(n)},$$ where $\ell(σ)$ is the inversion number of permutation $σ$ in the symmetric group $S_n$ 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=p^k$, exactly computing $q$-permanent is $\mathsf{Mod}_p\mathsf{P}$-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/n^2)$ 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.

arXiv:2302.08083•Feb 16, 2023•4 citations

Quantum complexity theory tools, goals and challenges

Jozef Gruska

Analysis of methods and results of quantum complexity theory and their contribution for better understanding of main theoretical and practical problems in quantum information processing.

•Jan 1, 2005•0 citations
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\rm{QCPH}QCPH , uses classical proofs, and the second, QPH\rm{QPH}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\rm{Q\Sigma_3}QΣ3​ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for QMA(2)\rm{QMA(2)}QMA(2) , the variant of Quantum Merlin-Arthur ( QMA\rm{QMA}QMA ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH\rm{QCPH = QPH}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{\rm P}^{{\rm pp}^{{\rm pp}}}Ppppp ). Second, because QMA(2)⊆QΣ3\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}QMA(2)⊆QΣ3​ , QMA(2)\rm{QMA(2)}QMA(2) is strictly contained in NEXP unless QMA(2)=QΣ3\rm{QMA(2)}=\rm{Q\Sigma_3}QMA(2)=QΣ3​ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').
The Polynomial-Time Hierarchy (PH\mathsf{PH}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\mathsf{PH}PH exist, it has been challenging to prove analogues for these of even basic facts from PH\mathsf{PH}PH. This work studies three quantum-verifier based generalizations of PH\mathsf{PH}PH, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings (QCPH\mathsf{QCPH}QCPH) and quantum mixed states (QPH\mathsf{QPH}QPH) as proofs, and one of which is new to this work, utilizing quantum pure states (pureQPH\mathsf{pureQPH}pureQPH) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for QCPH\mathsf{QCPH}QCPH. Then, for our new class pureQPH\mathsf{pureQPH}pureQPH, we show one-sided error reduction for pureQPH\mathsf{pureQPH}pureQPH, as well as the first bounds relating these quantum variants of PH\mathsf{PH}PH, namely QCPH⊆pureQPH⊆EXPPP\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}QCPH⊆pureQPH⊆EXPPP.
In this work, we study the computational complexity of quantum determinants, a qqq-deformation of matrix permanents: Given a complex number qqq on the unit circle in the complex plane and an n×nn\times nn×n matrix XXX, the qqq-permanent of XXX is defined as Perq(X)=∑σ∈Snqℓ(σ)X1,σ(1)…Xn,σ(n),\mathrm{Per}_q(X) = \sum_{σ\in S_n} q^{\ell(σ)}X_{1,σ(1)}\ldots X_{n,σ(n)},Perq​(X)=∑σ∈Sn​​qℓ(σ)X1,σ(1)​…Xn,σ(n)​, where ℓ(σ)\ell(σ)ℓ(σ) is the inversion number of permutation σσσ in the symmetric group SnS_nSn​ on nnn elements. The function family generalizes determinant and permanent, which correspond to the cases q=−1q=-1q=−1 and q=1q=1q=1 respectively. For worst-case hardness, by Liouville's approximation theorem and facts from algebraic number theory, we show that for primitive mmm-th root of unity qqq for odd prime power m=pkm=p^km=pk, exactly computing qqq-permanent is ModpP\mathsf{Mod}_p\mathsf{P}Modp​P-hard. This implies that an efficient algorithm for computing qqq-permanent results in a collapse of the polynomial hierarchy. Next, we show that computing qqq-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 qqq-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 111-permanent to qqq-permanent for O(1/n2)O(1/n^2)O(1/n2) points zzz 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 qqq-permanents.