---
res:
  bibo_abstract:
  - "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}}$.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Avantika
      foaf_name: Agarwal, Avantika
      foaf_surname: Agarwal
  - foaf_Person:
      foaf_givenName: Sevag
      foaf_name: Gharibian, Sevag
      foaf_surname: Gharibian
      foaf_workInfoHomepage: http://www.librecat.org/personId=71541
    orcid: 0000-0002-9992-3379
  - foaf_Person:
      foaf_givenName: Venkata
      foaf_name: Koppula, Venkata
      foaf_surname: Koppula
  - foaf_Person:
      foaf_givenName: Dorian
      foaf_name: Rudolph, Dorian
      foaf_surname: Rudolph
      foaf_workInfoHomepage: http://www.librecat.org/personId=57863
  bibo_doi: 10.4230/LIPIcs.MFCS.2024.7
  bibo_issue: '7'
  bibo_volume: 306
  dct_date: 2024^xs_gYear
  dct_language: eng
  dct_title: 'Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds@'
...