
Volume 21 (2025)
Article 7 pp. 1-13
[Note]
Even Quantum Advice is Unlikely to Solve PP
Received: May 29, 2024
Revised: September 4, 2025
Published: October 2, 2025
Revised: September 4, 2025
Published: October 2, 2025
Keywords: circuit complexity, quantum computing, counting hierarchy, quantum advice, oblivious proofs
Categories: quantum computing, circuit complexity, counting hierarchy, quantum advice, oblivious proofs, note
ACM Classification: F.1.3
AMS Classification: 68Q15, 68Q12, 68Q06
Abstract: [Plain Text Version]
We give a corrected proof that if $\mathsf{PP} \subseteq \mathsf{BQP/qpoly}$ (probabilistic polynomial time can be efficiently simulated by quantum circuits with quantum advice), then the Counting Hierarchy collapses, as originally claimed by Aaronson (CCC'06). This recovers the related unconditional claim that $\mathsf{PP}$ does not have circuits of any fixed-polynomial size $n^k$ even with quantum advice. Our result is based on proving that $\mathsf{YQP^*}$, an oblivious version of $\mathsf{QMA}\cap\mathsf{coQMA}$, is contained in $\mathsf{APP}$, a $\mathsf{PP}$-low subclass of $\mathsf{PP}$ with an arbitrarily small but nonzero promise gap.