BQP and the polynomial hierarchy
From MaRDI portal
Publication:2875140
DOI10.1145/1806689.1806711zbMath1293.68130OpenAlexW2000070319WikidataQ56387576 ScholiaQ56387576MaRDI QIDQ2875140
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1806689.1806711
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (24)
Dynamical structure factors of dynamical quantum simulators ⋮ Collapse of the hierarchy of constant-depth exact quantum circuits ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ Following forrelation -- quantum algorithms in exploring Boolean functions' spectra ⋮ Time evolution of complexity: a critique of three methods ⋮ Commuting quantum circuits and complexity of Ising partition functions ⋮ An efficient quantum algorithm for spectral estimation ⋮ Introducing nega-forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Quantum algorithms for similarity measurement based on Euclidean distance ⋮ Quantum algorithm design: techniques and applications ⋮ Randomness buys depth for approximate counting ⋮ Fourier 1-norm and quantum speed-up ⋮ Advice Coins for Classical and Quantum Computation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing ⋮ Quantum Property Testing for Bounded-Degree Graphs ⋮ Classical vs quantum random oracles ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Quantum versus randomized communication complexity, with efficient players
This page was built for publication: BQP and the polynomial hierarchy
