Cover Image

The Acrobatics of BQP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aaronson, Scott, Ingram, DeVon, Kretschmer, William
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Why Philosophers Should Care About Computational Complexity
by: Aaronson, Scott
Published: (2011)

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
by: Zschetzsche, Lilith, et al.
Published: (2026)

BQP, meet NP: Search-to-decision reductions and approximate counting
by: Gharibian, Sevag, et al.
Published: (2024)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
by: Jackson, Andrew
Published: (2024)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
by: Grewal, Sabee, et al.
Published: (2025)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
Published: (2021)

Quantum Mass Production Theorems
by: Kretschmer, William
Published: (2022)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

Pseudoentanglement Ain't Cheap
by: Grewal, Sabee, et al.
Published: (2024)

Plethysm is in #BQP
by: Christandl, Matthias, et al.
Published: (2026)

Quantum-Computable One-Way Functions without One-Way Functions
by: Kretschmer, William, et al.
Published: (2024)

Quantum Cryptography in Algorithmica
by: Kretschmer, William, et al.
Published: (2022)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

Improved Stabilizer Estimation via Bell Difference Sampling
by: Grewal, Sabee, et al.
Published: (2023)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

Two prover perfect zero knowledge for MIP*
by: Mastel, Kieran, et al.
Published: (2024)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
by: Gay, William, et al.
Published: (2026)

The membership problem for constant-sized quantum correlations is undecidable
by: Fu, Honghao, et al.
Published: (2021)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

The NPA hierarchy does not always attain the commuting operator value
by: Fanizza, Marco, et al.
Published: (2025)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

The dihedral hidden subgroup problem
by: Chen, Imin, et al.
Published: (2021)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
by: Rosenthal, Gregory
Published: (2021)

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
by: Dutta, Suman, et al.
Published: (2021)

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
by: Cardoso, Ricardo Rivera, et al.
Published: (2025)

More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Operator
by: Tang, Letian
Published: (2025)

Commuting Local Hamiltonians Beyond 2D
by: Bostanci, John, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Peaked quantum advantage using error correction
by: Deshpande, Abhinav, et al.
Published: (2025)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
by: Grier, Daniel, et al.
Published: (2025)

Graphical Tests of Causality
by: Baumeler, Ämin, et al.
Published: (2025)