Theory of Computing
-------------------
Title     : Even Quantum Advice is Unlikely to Solve PP
Authors   : Justin Yirka
Volume    : 21
Number    : 7
Pages     : 1-13
URL       : https://theoryofcomputing.org/articles/v021a007

Abstract
--------

We give a corrected proof that if PP \subseteq 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 PP does not have
circuits of any fixed-polynomial size n^k even with quantum advice.
Our result is based on proving that YQP^*, an oblivious version of
QMA\cap coQMA, is contained in APP, a PP-low subclass of PP with
an arbitrarily small but nonzero promise gap.