Even quantum advice is unlikely to solve PP

DOI10.4086/TOC.2025.V021A007MaRDI QIDQ6860909zbMATH OpenFDO

Authors Justin Yirka

Publication date 10 February 2026

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4086/TOC.2025.V021A007

zbMATH Keywords

circuit complexitycounting hierarchyoblivious proofsquantum advicequantum computing

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68)

Cites work

• A full characterization of quantum advice
• A note on the circuit complexity of PP
• Algebraic methods for interactive proof systems
• Complexity limitations on quantum computation
• Computational Complexity
• How hard is it to approximate the Jones polynomial?
• scientific article; zbMATH DE number 1405686 (Why is no real title available?)
• Input-oblivious proof systems and a uniform complexity perspective on P/poly
• Nonuniform ACC circuit lower bounds
• Oblivious Symmetric Alternation
• PP-lowness and a simple definition of AWPP
• Quantum Arthur-Merlin games
• Quantum computing, postselection, and probabilistic polynomial-time
• The learnability of quantum states

This page was built for publication: Even quantum advice is unlikely to solve \(\mathsf{PP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6860909)