Many important computer science problems can be reduced to the clause-satisfaction problem. We are given
n Boolean variables
xk and
m clauses
cj where each clause is a function of values of some
xk. We want to find an assignment
i of
xk for which all
m clauses are satisfied. Let
fj(i) be a binary function, which is 1 if the
jth clause is satisfied by the assignment
i, else
fj(i)=0. Then the solution is
r for which
f(i=r)=1, where
f(i) is the and function of all
fj(i). In quantum computing, Grover's algorithm can be used to find
r. A crucial component of this algorithm is the selective phase inversion
Ir of the solution state encoding
r.
Ir is implemented by computing
f(i) for all
i in superposition which requires computing and of all
m binary functions
fj(i). Hence there must be coupling between the computation circuits for each
fj(i). In this paper, we present an alternative quantum search algorithm which relaxes the requirement of such couplings. Hence it offers implementation advantages for clause-satisfaction problems.
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.
Every variable in a 3-SAT clause plays one of three roles—positive, negative, or absent—matching the three basis states of a qutrit. We build on this correspondence: a formula with M clauses on n variables is encoded as a register of nM qutrits, a parameterised unitary circuit is applied, and the resulting qutrit values are measured. Any classical strategy may then be applied to the outcomes; the one we study partitions them into M clause windows, each checked as a candidate satisfying assignment. For product circuits these windows are provably independent, yielding a closed-form success probability. Exhaustive optimisation over all structurally distinct four-variable formulas with up to twelve clauses, reaching 564,954 satisfiable canonical forms at M=12, reveals a window for quantum advantage: the worst-case witness probability stays between 0.39 and 0.48 across the entire tested frontier, even when the hardest formula has a unique satisfying assignment. The hardest instances fall into a small library of combinatorial motifs—non-affine blocks, all-but-one blocks, free-variable factors, and pinned-variable factors—whose structure explains how success probability is distributed across the ensemble. At the largest tested clause counts, the ensemble of windows drives the success probability upward again—the ensemble fights back. We conjecture that this optimised witness probability does not decrease exponentially with the number of clauses.
The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in
O(m2) for an E3-CNF Boolean formula with
m clauses and in the worst case runs in
O(n6) for an E3-CNF Boolean formula with
n inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of
1−ε for small
ε>0 using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied 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,
rkn. 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≥3, any small
ε>0 and sufficiently large n:
⋅ k-local quantum search achieves general efficiency on random instances of max-k-SSAT with
m=Ω(n2+δ+ε) using
O(n) iterations, and
⋅ k-local adiabatic quantum search enhances the bound to
m=Ω(n1+δ+ε) within an evolution time of
O(n2). In both cases, the circuit complexity of each iteration is
O(nk), and the efficiency is assured with overwhelming probability
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+ε) based on the average-case complexity theory.