ECCC-Report TR24-052https://eccc.weizmann.ac.il/report/2024/052Comments and Revisions published for TR24-052en-usWed, 29 May 2024 05:22:04 +0300
Revision 1
| Even quantum advice is unlikely to solve PP |
Justin Yirka
https://eccc.weizmann.ac.il/report/2024/052#revision1We give a corrected proof that if PP $\subseteq$ BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by [Aaronson 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*, an oblivious version of (QMA $\cap$ coQMA), is contained in APP, and so is PP-low.
Wed, 29 May 2024 05:22:04 +0300https://eccc.weizmann.ac.il/report/2024/052#revision1
Paper TR24-052
| Even quantum advice is unlikely to solve PP |
Justin Yirka
https://eccc.weizmann.ac.il/report/2024/052We 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*, an oblivious version of (QMA $\cap$ coQMA), is contained in APP, and so is PP-low.
Sun, 17 Mar 2024 13:45:15 +0200https://eccc.weizmann.ac.il/report/2024/052