March 14, 2024Open Access

Even quantum advice is unlikely to solve PP

Key Points

Key points are not available for this paper at this time.

Abstract

We give a corrected proof that if PP BQP/qpoly, then the Counting Hierarchy collapses, as originally claimed by Aaronson CCC'06 arXiv: cs/0504048. This recovers the related unconditional claim that PP does not have circuits of any fixed size nᵏ 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.

Read Full Paperexternally

Mark Helpful

Bookmark

Relay

View Full Paper

Cite This Study

Justin Yirka (Thu,) studied this question.

synapsesocial.com/papers/68e7411ab6db6435876baaf0 https://doi.org/https://doi.org/10.48550/arxiv.2403.09994

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

1Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy2025
2Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians2024
3The status of the quantum PCP conjecture (games version)2024 · 1 citations
4Pure-Circuit: Tight Inapproximability for PPAD2024 · 3 citations
5The Propositional Proof System of APX₁: Formalizing Razborov-Smolensky Below APC₁2026

Mark Helpful

Bookmark

Relay

View Full Paper