Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, ArXiv:2401.01633 (2024).
Download
No fulltext has been uploaded.
Preprint
| English
Author
Agarwal, Avantika;
Gharibian, SevagLibreCat ;
Koppula, Venkata;
Rudolph, Dorian
Abstract
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}}$.
Publishing Year
Journal Title
arXiv:2401.01633
LibreCat-ID
Cite this
Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. arXiv:240101633. Published online 2024.
Agarwal, A., Gharibian, S., Koppula, V., & Rudolph, D. (2024). Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. In arXiv:2401.01633.
@article{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}, journal={arXiv:2401.01633}, author={Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}, year={2024} }
Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds.” ArXiv:2401.01633, 2024.
A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds,” arXiv:2401.01633. 2024.
Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds.” ArXiv:2401.01633, 2024.