---
_id: '50273'
abstract:
- lang: eng
  text: "The Polynomial-Time Hierarchy ($\\mathsf{PH}$) is a staple of classical\r\ncomplexity
    theory, with applications spanning randomized computation to circuit\r\nlower
    bounds to ''quantum advantage'' analyses for near-term quantum computers.\r\nQuantumly,
    however, despite the fact that at least \\emph{four} definitions of\r\nquantum
    $\\mathsf{PH}$ exist, it has been challenging to prove analogues for\r\nthese
    of even basic facts from $\\mathsf{PH}$. This work studies three\r\nquantum-verifier
    based generalizations of $\\mathsf{PH}$, two of which are from\r\n[Gharibian,
    Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings\r\n($\\mathsf{QCPH}$)
    and quantum mixed states ($\\mathsf{QPH}$) as proofs, and one\r\nof which is new
    to this work, utilizing quantum pure states\r\n($\\mathsf{pureQPH}$) as proofs.
    We first resolve several open problems from\r\n[GSSSY22], including a collapse
    theorem and a Karp-Lipton theorem for\r\n$\\mathsf{QCPH}$. Then, for our new class
    $\\mathsf{pureQPH}$, we show one-sided\r\nerror reduction for $\\mathsf{pureQPH}$,
    as well as the first bounds relating\r\nthese quantum variants of $\\mathsf{PH}$,
    namely $\\mathsf{QCPH}\\subseteq\r\n\\mathsf{pureQPH} \\subseteq \\mathsf{EXP}^{\\mathsf{PP}}$."
author:
- first_name: Avantika
  full_name: Agarwal, Avantika
  last_name: Agarwal
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Venkata
  full_name: Koppula, Venkata
  last_name: Koppula
- first_name: Dorian
  full_name: Rudolph, Dorian
  id: '57863'
  last_name: Rudolph
citation:
  ama: 'Agarwal A, Gharibian S, Koppula V, Rudolph D. Quantum Polynomial Hierarchies:
    Karp-Lipton, error reduction, and lower  bounds. In: <i>Proceedings of 49th International
    Symposium on Mathematical Foundations of Computer Science (MFCS)</i>. Vol 306.
    ; 2024:7-17. doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>'
  apa: 'Agarwal, A., Gharibian, S., Koppula, V., &#38; Rudolph, D. (2024). Quantum
    Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds. <i>Proceedings
    of 49th International Symposium on Mathematical Foundations of Computer Science
    (MFCS)</i>, <i>306</i>(7), 7–17. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">https://doi.org/10.4230/LIPIcs.MFCS.2024.7</a>'
  bibtex: '@inproceedings{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial
    Hierarchies: Karp-Lipton, error reduction, and lower  bounds}, volume={306}, DOI={<a
    href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>},
    number={7}, 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}, year={2024}, pages={7–17} }'
  chicago: 'Agarwal, Avantika, Sevag Gharibian, Venkata Koppula, and Dorian Rudolph.
    “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower  Bounds.”
    In <i>Proceedings of 49th International Symposium on Mathematical Foundations
    of Computer Science (MFCS)</i>, 306:7–17, 2024. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">https://doi.org/10.4230/LIPIcs.MFCS.2024.7</a>.'
  ieee: 'A. Agarwal, S. Gharibian, V. Koppula, and D. Rudolph, “Quantum Polynomial
    Hierarchies: Karp-Lipton, error reduction, and lower  bounds,” in <i>Proceedings
    of 49th International Symposium on Mathematical Foundations of Computer Science
    (MFCS)</i>, 2024, vol. 306, no. 7, pp. 7–17, doi: <a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>.'
  mla: 'Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error
    Reduction, and Lower  Bounds.” <i>Proceedings of 49th International Symposium
    on Mathematical Foundations of Computer Science (MFCS)</i>, vol. 306, no. 7, 2024,
    pp. 7–17, doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2024.7">10.4230/LIPIcs.MFCS.2024.7</a>.'
  short: 'A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th
    International Symposium on Mathematical Foundations of Computer Science (MFCS),
    2024, pp. 7–17.'
date_created: 2024-01-07T20:09:32Z
date_updated: 2026-05-15T08:39:23Z
department:
- _id: '7'
- _id: '623'
doi: 10.4230/LIPIcs.MFCS.2024.7
external_id:
  arxiv:
  - '2401.01633'
intvolume: '       306'
issue: '7'
language:
- iso: eng
page: 7-17
publication: Proceedings of 49th International Symposium on Mathematical Foundations
  of Computer Science (MFCS)
publication_status: published
status: public
title: 'Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds'
type: conference
user_id: '71541'
volume: 306
year: '2024'
...