Oracle separation of BQP and PH

DOI10.1145/3313276.3316315zbMath1433.68152OpenAlexW2952315951MaRDI QIDQ5212743

Avishay Tal, Ran Raz

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3313276.3316315

zbMATH Keywords

polynomial hierarchybounded-depth circuitsBQPoracle separation

Mathematics Subject Classification ID

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

Related Items

Dynamical structure factors of dynamical quantum simulators, Unnamed Item, Unnamed Item, Verifying quantum computations at scale: A cryptographic leash on quantum devices, Sumcheck-based delegation of quantum computing to rational server, Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates, Towards quantum computing based community detection, Quantum versus randomized communication complexity, with efficient players