Oracle Separation of BQP and PH

DOI10.1145/3530258MaRDI QIDQ5889791zbMATH OpenOpenAlexWikidataFDO

Authors Ran Raz, Avishay Tal

Publication date 27 April 2023

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

bounded depth circuitsBQPoracle separationpolynomial hierarchy

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Oracle separation of BQP and PH
• BQP and the polynomial hierarchy
• A stochastic calculus approach to the oracle separation of \(\mathsf{BQP}\) and \(\mathsf{PH} \)
• Oracle separations between quantum and non-interactive zero-knowledge classes
• Quantum lower bound for recursive Fourier sampling

Cited in

(10)

• Time evolution of complexity: a critique of three methods
• scientific article; zbMATH DE number 1796950 (Why is no real title available?)
• A stochastic calculus approach to the oracle separation of \(\mathsf{BQP}\) and \(\mathsf{PH} \)
• Certified randomness from quantum supremacy
• On the need for large quantum depth
• Elementary quantum recursion schemes that capture quantum polylogarithmic-time computability of quantum functions
• On the physical basis for the incomparability of NP and BQP
• A signature scheme constructed from zero knowledge argument of knowledge for the subgraph isomorphism problem
• Oracle separations for non-adaptive collapse-free quantum computing
• Testing isomorphism of Boolean functions over finite abelian groups

This page was built for publication: Oracle Separation of BQP and PH

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