BQP, meet NP: Search-to-decision reductions and approximate counting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gharibian, Sevag, Kamminga, Jonas
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the complexity of estimating ground state entanglement and free energy
by: Gharibian, Sevag, et al.
Published: (2025)

The 7 faces of quantum NP
by: Gharibian, Sevag
Published: (2023)

Hardness of approximation for ground state problems
by: Gharibian, Sevag, et al.
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
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)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
by: Rudolph, Dorian, et al.
Published: (2024)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
by: Aldi, Marco, et al.
Published: (2024)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

On the Complexity of Pure-State Consistency of Local Density Matrices
by: Kamminga, Jonas, et al.
Published: (2024)

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

The Complexity of Translationally Invariant Problems beyond Ground State Energies
by: Watson, James D., et al.
Published: (2020)

How hard is it to verify a classical shadow?
by: Karaiskos, Georgios, et al.
Published: (2025)

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

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

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

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

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

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

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

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

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

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

Quantum embedding of graphs for subgraph counting
by: Adhikari, Bibhas
Published: (2026)

StoqMA vs. MA: the power of error reduction
by: Aharonov, Dorit, et al.
Published: (2020)

Low-degree approximation of QAC$^0$ circuits
by: Montanaro, Ashley, et al.
Published: (2024)

Non-signalling parallel repetition using de Finetti reductions
by: Arnon, Rotem, et al.
Published: (2014)

Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
by: Zhan, Junpeng
Published: (2023)

Efficient approximate unitary designs from random Pauli rotations
by: Haah, Jeongwan, et al.
Published: (2024)

Quantum Search With Generalized Wildcards
by: Cornelissen, Arjan, et al.
Published: (2025)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
by: Morimae, Tomoyuki, et al.
Published: (2025)

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

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
by: He, Entong
Published: (2024)

Multimarked Spatial Search by Continuous-Time Quantum Walk
by: Lugão, Pedro H. G., et al.
Published: (2022)

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
by: Wu, Mingyou
Published: (2024)

Incompressibility and spectral gaps of random circuits
by: Chen, Chi-Fang, et al.
Published: (2024)