Cover Image

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schreiber, Franz J., Kramer, Maximilian J., Nietner, Alexander, Eisert, Jens
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

Free Fermion Distributions Are Hard to Learn
by: Nietner, Alexander
Published: (2023)

On the average-case complexity of learning output distributions of quantum circuits
by: Nietner, Alexander, et al.
Published: (2023)

Interactive proofs for verifying (quantum) learning and testing
by: Caro, Matthias C., et al.
Published: (2024)

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

Classical Verification of Quantum Learning
by: Caro, Matthias C., et al.
Published: (2023)

Verifiable measurement-based quantum random sampling with trapped ions
by: Ringbauer, Martin, et al.
Published: (2023)

Exact spectral gaps of random one-dimensional quantum circuits
by: Deneris, Andrew E., et al.
Published: (2024)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
by: Pirnay, Niklas, et al.
Published: (2022)

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

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Derandomised tensor product gap amplification for quantum Hamiltonians
by: Bergamaschi, Thiago, et al.
Published: (2025)

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

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

An efficient quantum parallel repetition theorem and applications
by: Bostanci, John, et al.
Published: (2023)

The computational two-way quantum capacity
by: Meyer, Johannes Jakob, et al.
Published: (2026)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

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

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

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

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

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
by: Daskin, Ammar
Published: (2024)

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)

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

Does there exist a quantum fingerprinting protocol without coherent measurements?
by: Hasegawa, Atsuya, et al.
Published: (2025)

Complexity of quantum circuits via sensitivity, magic, and coherence
by: Bu, Kaifeng, et al.
Published: (2022)

Tomography of parametrized quantum states
by: Schreiber, Franz J., et al.
Published: (2024)

Approximation algorithms for noncommutative CSPs
by: Culf, Eric, et al.
Published: (2023)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
by: Gall, François Le, et al.
Published: (2023)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

Bell sampling from quantum circuits
by: Hangleiter, Dominik, et al.
Published: (2023)

Fast quantum algorithm for differential equations
by: Bagherimehrab, Mohsen, et al.
Published: (2023)

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

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

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
by: Krovi, Hari
Published: (2024)

Computational relative entropy
by: Meyer, Johannes Jakob, et al.
Published: (2025)

Quasi-quantum states and the quasi-quantum PCP theorem
by: Arad, Itai, et al.
Published: (2024)

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

Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry
by: Kramer, Maximilian J., et al.
Published: (2026)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)