Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronics

A Hybrid Quantum–Classical Algorithm for k-SAT via Grover-Enhanced Local Search

Yingyu ZHANG

Published Oct 21, 2026• 0 citations
Publisher

Abstract

The $k$-SAT problem is a canonical NP-complete problem for which no efficient algorithm is known. This paper proposes a hybrid quantum–classical algorithm that employs Grover's algorithm as the inner local search of a randomized outer loop. Each outer iteration measures a random assignment, prepares a problem-dependent superposition over the Hamming ball of radius $r$ around it, and applies amplitude amplification to locate a satisfying assignment. Because the ball center is measured, the outer loop remains a classical repetition over independently sampled balls and contributes the inverse success probability rather than its square root; balancing this against the inner quadratic speedup shifts the optimal radius from $n/(k+1)$ to $n/(1+\sqrt{k})$ and yields the running time $(2-2/(1+\sqrt{k}))^{n}$, up to polynomial factors—$1.268^{n}$ for $k=3$, below the best known classical $1.307^{n}$. The contribution is not an asymptotic record—the best known quantum exponents for $k$-SAT, obtained by amplifying stronger classical solvers as black boxes, remain smaller—but a fully explicit, gate-level construction: the problem-dependent state over the Hamming ball and the $k$-SAT oracle are decomposed into elementary quantum gates, and the polynomial gate and qubit overheads are accounted for in full.

DOI
10.3390/electronics15204867

Related papers

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

Mingyou Wu

The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, $r_k n$. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small $k \ge 3$, any small $ε>0$ and sufficiently large n: $\cdot$ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with $m=Ω(n^{2+δ+ε})$ using $\mathcal{O}(n)$ iterations, and $\cdot$ k-local adiabatic quantum search enhances the bound to $m=Ω(n^{1+δ+ε})$ within an evolution time of $\mathcal{O}(n^2)$. In both cases, the circuit complexity of each iteration is $\mathcal{O}(n^k)$, and the efficiency is assured with overwhelming probability $1 - \mathcal{O}(\mathrm{erfc}(n^{δ/2}))$. By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when $m=Ω(n^{2+ε})$ based on the average-case complexity theory.

arXiv:2403.03237•Mar 5, 2024•1 citation

Opening the Black Box inside Grover’s Algorithm

Edwin Miles Stoudenmire, Xavier Waintal

Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024

arXiv:2303.11317•Physical Review X•Nov 1, 2024•27 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations

Hybrid Quantum Search Algorithms

Vahideh Eshaghian

This thesis presents two main projects focused on hybrid quantum search algorithms. The first, Particle-Guided Grover's Search, applies Bayesian inference to quantum search when the number of solutions is a priori unknown. It begins with a prior distribution that encodes our initial "beliefs" about the true number of solutions in the search space, and recursively updates these beliefs using Bayesian inference. Measurement outcomes of the quantum search that do not yield a solution are interpreted as "evidence", guiding the Bayesian update to determine the optimal number of Grover iterations for subsequent rounds. This approach leverages Particle Filtering -- a Bayesian filtering technique -- to avoid explicitly storing the entire prior distribution at each step. Instead of requiring O(N) memory, the method draws a set of "particles" from the prior and updates their associated weights as quantum search failures accumulate. Particle filtering also offers the advantage of incorporating information from all past failures, rather than only the most recent one. The algorithm's performance is benchmarked against a prior work. The second project, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, is focused on a class of hybrid k-SAT solvers. These solvers are based on a well-known random walk technique called Schoening's algorithm, which uses two sources of randomness to perform a local search over the space of all assignments for a k-SAT problem. In this project, we assume that these sources of randomness are encoded into a long bitstring, allowing the random walk to be interpreted as a deterministic function mapping each bitstring to either 0 or 1, depending on whether the walk successfully finds a satisfying assignment. This functional perspective enables us to pose the question: Given a bound on the coherence time of a quantum computer, which portion of the bitstring should we search coherently, and which portion should be left to classical search? We address this question by introducing a family of hybrid algorithms called "partial Groverizations", which strategically combine quantum and classical resources. We analyze the runtime performance of this family as a function of the available quantum coherence time. The results of this work have been published in IEEE Transactions on Quantum Engineering.

•Jan 1, 2025•0 citations

Quantangle-SAT: A Quantum SAT Solver Based on Entanglement and Equivalence Checking

Shang-Wei Lin, Ji-Qing Yan, Yean-Ru Chen +2 more

Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.

quant-pharXiv:2604.18218•Apr 21, 2026•0 citations

Runtime-coherence trade-offs for hybrid SAT-solvers

Vahideh Eshaghian, Sören Wilkening, Johan Åberg +1 more

Many search-based quantum algorithms that achieve a theoretical speedup are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts.This raises the question of how to divide computational tasks into a collection of parallelizable sub-problems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the k-SAT problem. Our analysis is based on Schöning's algorithm, which solves instances of k-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for "natural" partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.

arXiv:2404.15235•Apr 23, 2024•0 citations
The kkk-SAT problem is a canonical NP-complete problem for which no efficient algorithm is known. This paper proposes a hybrid quantum–classical algorithm that employs Grover's algorithm as the inner local search of a randomized outer loop. Each outer iteration measures a random assignment, prepares a problem-dependent superposition over the Hamming ball of radius rrr around it, and applies amplitude amplification to locate a satisfying assignment. Because the ball center is measured, the outer loop remains a classical repetition over independently sampled balls and contributes the inverse success probability rather than its square root; balancing this against the inner quadratic speedup shifts the optimal radius from n/(k+1)n/(k+1)n/(k+1) to n/(1+k)n/(1+\sqrt{k})n/(1+k​) and yields the running time (2−2/(1+k))n(2-2/(1+\sqrt{k}))^{n}(2−2/(1+k​))n, up to polynomial factors—1.268n1.268^{n}1.268n for k=3k=3k=3, below the best known classical 1.307n1.307^{n}1.307n. The contribution is not an asymptotic record—the best known quantum exponents for kkk-SAT, obtained by amplifying stronger classical solvers as black boxes, remain smaller—but a fully explicit, gate-level construction: the problem-dependent state over the Hamming ball and the kkk-SAT oracle are decomposed into elementary quantum gates, and the polynomial gate and qubit overheads are accounted for in full.
Local Quantum Search Algorithm for Random kkk-SAT with Ω(n1+ε)Ω(n^{1+ε})Ω(n1+ε) Clauses
The random k-SAT instances undergo a "phase transition" from being generally satisfiable to unsatisfiable as the clause number m passes a critical threshold, rknr_k nrk​n. This causes a drastic reduction in the number of satisfying assignments, shifting the problem from being generally solvable on classical computers to typically insolvable. Beyond this threshold, it is challenging to comprehend the computational complexity of random k-SAT. In quantum computing, Grover's search still yields exponential time requirements due to the neglect of structural information. Leveraging the structure inherent in search problems, we propose the k-local quantum search algorithm, which extends quantum search to structured scenarios. Grover's search, by contrast, addresses the unstructured case where k=n. Given that the search algorithm necessitates the presence of a target, we specifically focus on the problem of searching the interpretation of satisfiable instances of k-SAT, denoted as max-k-SSAT. If this problem is solvable in polynomial time, then k-SAT can also be solved within the same complexity. We demonstrate that, for small k≥3k \ge 3k≥3, any small ε>0ε>0ε>0 and sufficiently large n: ⋅\cdot⋅ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with m=Ω(n2+δ+ε)m=Ω(n^{2+δ+ε})m=Ω(n2+δ+ε) using O(n)\mathcal{O}(n)O(n) iterations, and ⋅\cdot⋅ k-local adiabatic quantum search enhances the bound to m=Ω(n1+δ+ε)m=Ω(n^{1+δ+ε})m=Ω(n1+δ+ε) within an evolution time of O(n2)\mathcal{O}(n^2)O(n2). In both cases, the circuit complexity of each iteration is O(nk)\mathcal{O}(n^k)O(nk), and the efficiency is assured with overwhelming probability 1−O(erfc(nδ/2))1 - \mathcal{O}(\mathrm{erfc}(n^{δ/2}))1−O(erfc(nδ/2)). By modifying this algorithm capable of solving all instances of max-k-SSAT, we further prove that max-k-SSAT is polynomial on average when m=Ω(n2+ε)m=Ω(n^{2+ε})m=Ω(n2+ε) based on the average-case complexity theory.
Grover’s algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. It involves an “oracle” (external quantum subroutine), which must be specified for a given application and whose internal structure is not part of the formal scaling of the quadratic quantum speedup guaranteed by the algorithm. Grover’’s algorithm also requires exponentially many calls to the quantum oracle (approximately 2 n calls where n is the number of qubits) to succeed, raising the question of its implementation on both noisy and error-corrected quantum computers. In this work, we construct a quantum-inspired algorithm executable on a classical computer that performs Grover’s task in a linear number of calls to (simulations of) the oracle—an exponentially smaller number than Grover’s algorithm—and demonstrate this algorithm explicitly for Boolean satisfiability problems. The complexity of our algorithm depends on the cost to simulate the oracle once, which may or may not be exponential, depending on its internal structure. Indeed, Grover’s algorithm does not have an quantum speedup as soon as one is given access to the “source code” of the oracle, which may reveal an internal structure of the problem. Our findings illustrate this point explicitly, as our algorithm exploits the structure of the quantum circuit used to program the quantum computer to speed up the search. There are still problems where Grover’s algorithm would provide an asymptotic speedup if it could be run accurately for large enough sizes. Our quantum-inspired algorithm provides lower bounds, in terms of the quantum-circuit complexity, for the quantum hardware to beat classical approaches for these problems. These estimates, combined with the unfavorable scaling of the success probability of Grover’s algorithm, which in the presence of noise decays as the exponential of the exponential of the number of qubits, makes a practical speedup unrealistic even under extremely optimistic assumptions of the evolution of both hardware quality and availability. Published by the American Physical Society 2024
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
This thesis presents two main projects focused on hybrid quantum search algorithms. The first, Particle-Guided Grover's Search, applies Bayesian inference to quantum search when the number of solutions is a priori unknown. It begins with a prior distribution that encodes our initial "beliefs" about the true number of solutions in the search space, and recursively updates these beliefs using Bayesian inference. Measurement outcomes of the quantum search that do not yield a solution are interpreted as "evidence", guiding the Bayesian update to determine the optimal number of Grover iterations for subsequent rounds. This approach leverages Particle Filtering -- a Bayesian filtering technique -- to avoid explicitly storing the entire prior distribution at each step. Instead of requiring O(N) memory, the method draws a set of "particles" from the prior and updates their associated weights as quantum search failures accumulate. Particle filtering also offers the advantage of incorporating information from all past failures, rather than only the most recent one. The algorithm's performance is benchmarked against a prior work. The second project, Runtime--Coherence Trade-offs for Hybrid SAT Solvers, is focused on a class of hybrid k-SAT solvers. These solvers are based on a well-known random walk technique called Schoening's algorithm, which uses two sources of randomness to perform a local search over the space of all assignments for a k-SAT problem. In this project, we assume that these sources of randomness are encoded into a long bitstring, allowing the random walk to be interpreted as a deterministic function mapping each bitstring to either 0 or 1, depending on whether the walk successfully finds a satisfying assignment. This functional perspective enables us to pose the question: Given a bound on the coherence time of a quantum computer, which portion of the bitstring should we search coherently, and which portion should be left to classical search? We address this question by introducing a family of hybrid algorithms called "partial Groverizations", which strategically combine quantum and classical resources. We analyze the runtime performance of this family as a function of the available quantum coherence time. The results of this work have been published in IEEE Transactions on Quantum Engineering.
Satisfiability (SAT) is a central problem in computer science, and advances in SAT-solving algorithms have a far-reaching impact across many fields. Recent works have proposed quantum SAT solvers based on Grover's algorithm, a quantum search technique. However, Grover-based approaches face a key limitation: they typically require prior knowledge of the number of satisfying assignments of the target Boolean formula. This information is unavailable in most practical settings. Quantum counting can be used to estimate this quantity, but it incurs a computational overhead that is several orders of magnitude higher than Grover search. In this paper, we propose a novel quantum SAT solver based on entanglement and equivalence checking. Our method does not assume prior knowledge of the number of solutions and is computationally more efficient than quantum counting. Although the worst case time complexity is inevitably exponential, we prove that the expected time complexity of our approach is only constant time O(1) over random Boolean functions. Experimental results also support our theoretical claim.
Many search-based quantum algorithms that achieve a theoretical speedup are not practically relevant since they require extraordinarily long coherence times, or lack the parallelizability of their classical counterparts.This raises the question of how to divide computational tasks into a collection of parallelizable sub-problems, each of which can be solved by a quantum computer with limited coherence time. Here, we approach this question via hybrid algorithms for the k-SAT problem. Our analysis is based on Schöning's algorithm, which solves instances of k-SAT by performing random walks in the space of potential assignments. The search space of the walk allows for "natural" partitions, where we subject only one part of the partition to a Grover search, while the rest is sampled classically, thus resulting in a hybrid scheme. In this setting, we argue that there exists a simple trade-off relation between the total runtime and the coherence-time, which no such partition based hybrid-scheme can surpass. For several concrete choices of partitions, we explicitly determine the specific runtime coherence-time relations, and show saturation of the ideal trade-off. Finally, we present numerical simulations which suggest additional flexibility in implementing hybrid algorithms with optimal trade-off.