Cover Image

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cardoso, Ricardo Rivera, Meiburg, Alex, Nagaj, Daniel
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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)

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

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Bounds on Eventually Universal Quantum Gate Sets
by: Karamchedu, Chaitanya, et al.
Published: (2025)

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

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

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

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
by: González-Castillo, Samuel, et al.
Published: (2026)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
by: Schreiber, Franz J., et al.
Published: (2025)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
by: Delavenne, Hugo, et al.
Published: (2024)

On Bounded Advice Classes
by: Marshall, Simon, et al.
Published: (2024)

Quantum Threshold is Powerful
by: Grier, Daniel, et al.
Published: (2024)

The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
by: Grilo, Alex Bredariol, et al.
Published: (2024)

Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
by: Schleich, Philipp, et al.
Published: (2024)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

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

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

Fast simulation of planar Clifford circuits
by: Gosset, David, et al.
Published: (2020)

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

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

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)

On the Complexity of the Succinct State Local Hamiltonian Problem
by: Waite, Gabriel, et al.
Published: (2025)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
by: Waite, Gabriel
Published: (2025)

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

The Round Complexity of Proofs in the Bounded Quantum Storage Model
by: Grilo, Alex B., et al.
Published: (2024)

Hardness results for decoding the surface code with Pauli noise
by: Fischer, Alex, et al.
Published: (2023)

Quantum Algorithms in a Superposition of Spacetimes
by: Shmueli, Omri
Published: (2024)

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

Complexity Classification of Product State Problems for Local Hamiltonians
by: Kallaugher, John, et al.
Published: (2024)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)

The Complexity of Stoquastic Sparse Hamiltonians
by: Grilo, Alex B., et al.
Published: (2026)

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

New Quantum Algorithms for Computing Quantum Entropies and Distances
by: Wang, Qisheng, et al.
Published: (2022)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
by: Grillo, Sebastian Alberto, et al.
Published: (2026)

How to Verify that a Small Device is Quantum, Unconditionally
by: Malavolta, Giulio, et al.
Published: (2025)

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