All reports by Author Justin Yirka:

__
TR24-052
| 15th March 2024
__

Justin Yirka#### Even quantum advice is unlikely to solve PP

__
TR24-006
| 14th January 2024
__

Sabee Grewal, Justin Yirka#### The Entangled Quantum Polynomial Hierarchy Collapses

Justin Yirka

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

Sabee Grewal, Justin Yirka

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