2024/03/15 by Yirka, Justin
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2403.09994
We give a corrected proof that if PP ⊆ BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson 2006 arXiv:cs/0504048]. This recovers the related unconditional claim that PP does not have circuits of any fixed size nk even with quantum advice. We do so by proving that YQP*, an oblivious version of (QMA ∩ coQMA), is contained in APP, and so is PP-low.