We give a corrected proof that if PP \subseteq BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson, CCC 2006]. This recovers the related unconditional claim that PP does not have circuits of any fixed size n^k even with quantum advice. We do so by proving that YQP*, ... more >>>

We introduce the entangled quantum polynomial hierarchy QEPH as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entangled with each other. We prove QEPH collapses to its second level. In fact, we show that a polynomial number of alternations collapses to just two. ... more >>>