The acrobatics of BQP

DOI10.4230/LIPICS.CCC.2022.20MaRDI QIDQ6568363zbMATH OpenFDO

Authors Scott Aaronson, Devon Ingram, William Kretschmer

Publication date 5 July 2024

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2022.20

zbMATH Keywords

BQPforrelationoracle separationspolynomial hierarchyquery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(7)

• Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
• The entangled quantum polynomial hierarchy collapses
• On the physical basis for the incomparability of NP and BQP
• BQP, meet NP: search-to-decision reductions and approximate counting
• Parity vs. \(\text{AC}^0\) with simple quantum preprocessing
• Quantum polynomial hierarchies: Karp-Lipton, error reduction, and lower bounds
• On the efficiency of generic, quantum cryptographic constructions

This page was built for publication: The acrobatics of BQP

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