Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d.
Download
No fulltext has been uploaded.
Conference Paper
| Accepted
| 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
Proceedings Title
Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)
LibreCat-ID
Cite this
Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. In: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS).
Agarwal, A., Gharibian, S., Koppula, V., & Rudolph, D. (n.d.). Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS).
@inproceedings{Agarwal_Gharibian_Koppula_Rudolph, title={Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}, booktitle={Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}, author={Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian} }
Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds.” In Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d.
A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds.”
Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds.” Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS).