Cover Image

A Relativizing MIP for BQP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aaronson, Scott, Natarajan, Anand, Tal, Avishay, Villanyi, Agi
Format:	Preprint
Published:	2026
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Acrobatics of BQP
by: Aaronson, Scott, et al.
Published: (2021)

The Computational Advantage of MIP* Vanishes in the Presence of Noise
by: Dong, Yangjing, 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)

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

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

Improved Lower Bounds for QAC0
by: Joshi, Malvika Raj, et al.
Published: (2025)

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)

The status of the quantum PCP conjecture (games version)
by: Natarajan, Anand, et al.
Published: (2024)

Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)

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

Succinct Perfect Zero-knowledge for MIP*
by: Fu, Honghao, et al.
Published: (2025)

Classical Commitments to Quantum States
by: Gunn, Sam, et al.
Published: (2024)

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

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)

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

Rounding Almost Commuting Hamiltonians
by: Faisal, Islam, et al.
Published: (2026)

Exponential Quantum Advantage for Simulating Open Classical Systems
by: Villanyi, Agi, et al.
Published: (2025)

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

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by: Filmus, Yuval, et al.
Published: (2020)

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

Finding dense sub-lattices as low-energy states of a Hamiltonian
by: Barberà-Rodríguez, Júlia, et al.
Published: (2023)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

A Critical Comment on 'Entropy Computing: A Paradigm for Optimization in Open Photonic Systems'
by: Moosavian, Ali Hamed, et al.
Published: (2026)

A Quantum Unique Games Conjecture
by: Mousavi, Hamoon, et al.
Published: (2024)

A Cautionary Note on Quantum Oracles
by: Agarwal, Avantika, et al.
Published: (2025)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

A Criterion for Post-Selected Quantum Advantage
by: Karamchedu, Chaitanya, et al.
Published: (2024)

A Note on the Complexity of the Spectral Gap Problem
by: Yirka, Justin
Published: (2025)

A sharp interaction-degree threshold for simulating QAOA
by: Āboliņš, Ralfs, et al.
Published: (2026)

A simplified version of the quantum OTOC$^{(2)}$ problem
by: King, Robbie, et al.
Published: (2025)

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

A full dichotomy for Holant$^c$, inspired by quantum computation
by: Backens, Miriam
Published: (2022)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
by: Mehraban, Saeed, et al.
Published: (2023)

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
by: Guseynov, Nikita, et al.
Published: (2026)