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

Finding solutions to MaxSAT in a quantum computer

Leonardo Clemente, Salvador Elías Venegas-Andraca

Published Jul 10, 2024• 0 citations
Publisher

Abstract

Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.

DOI
10.21203/rs.3.rs-4609871/v1

Related papers

Quantum search algorithm tailored to clause-satisfaction problems

Avatar Tulsi

Many important computer science problems can be reduced to the clause-satisfaction problem. We are given $n$ Boolean variables ${x}_{k}$ and $m$ clauses ${c}_{j}$ where each clause is a function of values of some ${x}_{k}$. We want to find an assignment $i$ of ${x}_{k}$ for which all $m$ clauses are satisfied. Let ${f}_{j}(i)$ be a binary function, which is 1 if the $j\mathrm{th}$ clause is satisfied by the assignment $i$, else ${f}_{j}(i)=0$. Then the solution is $r$ for which $f(i=r)=1$, where $f(i)$ is the and function of all ${f}_{j}(i)$. In quantum computing, Grover's algorithm can be used to find $r$. A crucial component of this algorithm is the selective phase inversion ${I}_{r}$ of the solution state encoding $r$. ${I}_{r}$ is implemented by computing $f(i)$ for all $i$ in superposition which requires computing and of all $m$ binary functions ${f}_{j}(i)$. Hence there must be coupling between the computation circuits for each ${f}_{j}(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.

arXiv:1503.06395•Physical Review A•May 22, 2015•4 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

Exponential Quantum Speedup for 3-SAT via Qutrit Amplitude Encoding

Leonardo Bohac

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.

•Jan 3, 2026•0 citations

A linear time quantum algorithm for 3SAT

Zachary B. Walters

A quantum algorithm for the NP complete problem of satisfying boolean formulas with three variables per clause (3SAT) is presented. Departing from traditional models of quantum computation, this algorithm makes extensive use of irreversible operations to incoherently transfer population from states which do not solve some problem of interest to states which do. Provided that a solution exists, the algorithm yields exponential decay of nonsolution probability, at a rate controlled by the user.

•Sep 29, 2015•0 citations

A Polynomial Time Bounded-error Quantum Algorithm for Boolean Satisfiability

Ahmed Younes, Jonathan E. Rowe

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(m^2)$ for an E3-CNF Boolean formula with $m$ clauses and in the worst case runs in $O(n^6)$ 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.

arXiv:1507.05061•Jul 16, 2015•5 citations

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•3 citations
Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.
Many important computer science problems can be reduced to the clause-satisfaction problem. We are given nnn Boolean variables xk{x}_{k}xk​ and mmm clauses cj{c}_{j}cj​ where each clause is a function of values of some xk{x}_{k}xk​. We want to find an assignment iii of xk{x}_{k}xk​ for which all mmm clauses are satisfied. Let fj(i){f}_{j}(i)fj​(i) be a binary function, which is 1 if the jthj\mathrm{th}jth clause is satisfied by the assignment iii, else fj(i)=0{f}_{j}(i)=0fj​(i)=0. Then the solution is rrr for which f(i=r)=1f(i=r)=1f(i=r)=1, where f(i)f(i)f(i) is the and function of all fj(i){f}_{j}(i)fj​(i). In quantum computing, Grover's algorithm can be used to find rrr. A crucial component of this algorithm is the selective phase inversion Ir{I}_{r}Ir​ of the solution state encoding rrr. Ir{I}_{r}Ir​ is implemented by computing f(i)f(i)f(i) for all iii in superposition which requires computing and of all mmm binary functions fj(i){f}_{j}(i)fj​(i). Hence there must be coupling between the computation circuits for each fj(i){f}_{j}(i)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)O(m^2)O(m2) for an E3-CNF Boolean formula with mmm clauses and in the worst case runs in O(n6)O(n^6)O(n6) for an E3-CNF Boolean formula with nnn 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−ε1-ε1−ε for small ε>0ε>0ε>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.
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.