Image de couverture de livre

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Wu, Mingyou
Format:	Preprint
Publié:	2024
Sujets:	Quantum Physics Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
par: González-Castillo, Samuel, et autres
Publié: (2026)

Quantum k-SAT Related Hypergraph Problems
par: Kremer, Simon-Luca, et autres
Publié: (2025)

Hamiltonians whose low-energy states require $Ω(n)$ T gates
par: Coble, Nolan J., et autres
Publié: (2023)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
par: Cardoso, Ricardo Rivera, et autres
Publié: (2025)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
par: Laakkonen, Tuomas, et autres
Publié: (2022)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
par: Rudolph, Dorian, et autres
Publié: (2024)

Quantum Advantages in (n,d)->1 Random Access Codes
par: Ambainis, Andris, et autres
Publié: (2015)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
par: Riazanov, Artur, et autres
Publié: (2025)

SAT, Gadgets, Max2XOR, and Quantum Annealers
par: Ansótegui, Carlos, et autres
Publié: (2024)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
par: Yao, Penghui, et autres
Publié: (2023)

Quantum Search With Generalized Wildcards
par: Cornelissen, Arjan, et autres
Publié: (2025)

Basic Quantum Algorithms
par: Portugal, Renato
Publié: (2022)

Random Unitaries in Constant (Quantum) Time
par: Foxman, Ben, et autres
Publié: (2025)

An Efficient Quantum Factoring Algorithm
par: Regev, Oded
Publié: (2023)

Pseudo-deterministic Quantum Algorithms
par: Aaronson, Hugo, et autres
Publié: (2026)

Efficient Algorithms for Quantum Hashing
par: Zinnatullin, Ilnar, et autres
Publié: (2025)

New Quantum Algorithms for Computing Quantum Entropies and Distances
par: Wang, Qisheng, et autres
Publié: (2022)

Quantum Event Learning and Gentle Random Measurements
par: Watts, Adam Bene, et autres
Publié: (2022)

Quantum Algorithms in a Superposition of Spacetimes
par: Shmueli, Omri
Publié: (2024)

Fourier Spectrum of Noisy Quantum Algorithms
par: Girish, Uma
Publié: (2025)

Multimarked Spatial Search by Continuous-Time Quantum Walk
par: Lugão, Pedro H. G., et autres
Publié: (2022)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
par: Lykov, Danylo, et autres
Publié: (2022)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
par: Schreiber, Franz J., et autres
Publié: (2025)

Quantum Algorithms for Approximate Graph Isomorphism Testing
par: Kulkarni, Prateek P.
Publié: (2026)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
par: Czégel, András, et autres
Publié: (2025)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
par: Rosenthal, Gregory
Publié: (2021)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
par: Fefferman, Bill, et autres
Publié: (2024)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
par: Li, Zhengyu, et autres
Publié: (2023)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
par: He, Kun, et autres
Publié: (2018)

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
par: Dutta, Suman, et autres
Publié: (2021)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
par: Mataraarachchi, Ranitha, et autres
Publié: (2026)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
par: Buhrman, Harry, et autres
Publié: (2024)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
par: Chen, Kean, et autres
Publié: (2024)

Raising the Bar: An Asymptotic Comparison of Classical and Quantum Shortest Path Algorithms
par: Do, Phuc Hao, et autres
Publié: (2025)

Algorithmic Randomness and Probabilistic Laws
par: Barrett, Jeffrey A., et autres
Publié: (2023)

The Power of Lorentz Quantum Computer
par: Zhang, Qi, et autres
Publié: (2024)

A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream
par: Kordonowy, Steven, et autres
Publié: (2026)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
par: Weggemans, Jordi, et autres
Publié: (2023)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
par: Chia, Nai-Hui, et autres
Publié: (2025)

Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
par: Zhang, Bingzhi, et autres
Publié: (2025)