pdf icon
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
Download article from ToC site:
[PDF (332K)] [PS (1201K)] [Source ZIP]
Keywords: circuit complexity, quantum computing, counting hierarchy, quantum advice, oblivious proofs
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.