Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-052 | 29th May 2024 05:21

Even quantum advice is unlikely to solve PP

RSS-Feed




Revision #1
Authors: Justin Yirka
Accepted on: 29th May 2024 05:22
Downloads: 81
Keywords: 


Abstract:

We 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.



Changes to previous version:

Added exposition and corrected arithmetic errors in v2.


Paper:

TR24-052 | 15th March 2024 05:28

Even quantum advice is unlikely to solve PP





TR24-052
Authors: Justin Yirka
Publication: 17th March 2024 13:45
Downloads: 263
Keywords: 


Abstract:

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*, an oblivious version of (QMA $\cap$ coQMA), is contained in APP, and so is PP-low.



ISSN 1433-8092 | Imprint