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

Exponential Quantum Speedup for 3-SAT via Qutrit Amplitude Encoding

Leonardo Bohac

Published Jan 3, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.5281/zenodo.18141483

Related papers

Finding solutions to MaxSAT in a quantum computer

Leonardo Clemente, Salvador Elías Venegas-Andraca

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.

•Jul 10, 2024•0 citations

Quantum Local Density of States for Random k-SAT: An Amplitude-Estimation Primitive and a Clause-Width Regime for Quantum Advantage

Michail Gerogiannis, Dimitris Ntalaperas, Nikos Konofaos

Abstract The present work introduces the Local Density of States (LDOS) primitive forBoolean satisfiability (SAT). For a Boolean formula on n variables and m clausesof width k, a window of ℓ free variables, and a random assignment of the remain-ing n − ℓ variables, the residual satisfying fraction p is the proportion of the2ℓ window assignments that satisfy the formula. The present work estimatesp on a gate-based quantum computer by amplitude estimation on a clause-by-clause phase-flip oracle, and averages p over random windows to form the LDOSsignature, consisting of its mean, its variance, and its positivity fraction, theprobability that a window remains satisfiable. It is proven that p is estimableto relative precision ε with O(mk/(ε√p)) gates, optimal up to logarithmicfactors. This estimation advantage inherits the known Grover-versus-classical k-SAT decision crossover and appears only at clause width four and above; atclause width three the best known classical algorithm is faster, and no advan-tage is claimed. The principal conceptual result recasts the positivity fractionas a structural lens on the geometry of the solution set. An exact reformulationshows that its leading behaviour is a counting effect, fixed by the window frac-tion and the clause width and carrying no dependence on the freezing transitionof random SAT; a dedicated sweep of the window fraction is required to isolateany freezing-specific signal, and a preliminary classical experiment confirms thecounting-driven behaviour. The present work asserts no quantum-versus-classicalhardness separation.

•Aug 31, 2026•0 citations

Amplitude amplification-inspired QAOA: improving the success probability for solving 3SAT

Alexander Mandl, Johanna Barzen, Marvin Bechtold +2 more

Abstract The Boolean satisfiability problem (SAT), in particular 3SAT with its bounded clause size, is a well-studied problem since a wide range of decision problems can be reduced to it. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices in the near future due to its simple quantum ansatz. However, although QAOA generally exhibits a high approximation ratio, there are 3SAT problem instances where the algorithm’s success probability when obtaining a satisfying variable assignment from the approximated solution drops sharply compared to the approximation ratio. To address this problem, in this paper, we present variants of the algorithm that are inspired by the amplitude amplification algorithm to improve the success probability for 3SAT. For this, (i) three amplitude amplification-inspired QAOA variants are introduced and implemented, (ii) the variants are experimentally compared with a standard QAOA implementation, and (iii) the impact on the success probability and ansatz complexity is analyzed. The experiment results show that an improvement in the success probability can be achieved with only a moderate increase in circuit complexity.

arXiv:2303.01183•Quantum Science and Technology•Dec 11, 2023•8 citations

Performance of a measurement-driven 'adiabatic-like' quantum 3-SAT solver

Simon C. Benjamin

I describe one quantum approach to solving 3-satisfiability (3-SAT), the well known problem in computer science. The approach is based on repeatedly measuring the truth value of the clauses forming the 3-SAT proposition using a non-orthogonal basis. If the basis slowly evolves then there is a strong analogy to adiabatic quantum computing, although the approach is entirely circuit-based. To solve a 3-SAT problem of n variables requires a quantum register of $n$ qubits, or more precisely rebits i.e. qubits whose phase need only be real. For cases of up to n=26 qubits numerical simulations indicate that the algorithm runs fast, outperforming Grover's algorithm and having a scaling with n that is superior to the best reported classical algorithms. There are indications that the approach has an inherent robustness versus imperfections in the elementary operations.

arXiv:1509.00667•Sep 2, 2015•1 citation

On Efficiently Solvable Cases of Quantum k-SAT

Marco Aldi, Niel de Beaudrap, Sevag Gharibian +1 more

The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.

Mathematical Foundations of Computer Science•Jan 1, 2018•1 citation

Different Strategies for Optimization Using the Quantum Adiabatic Algorithm

Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin +2 more

We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution.

arXiv:1401.7320•Jan 28, 2014•66 citations
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.
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.
Abstract The present work introduces the Local Density of States (LDOS) primitive forBoolean satisfiability (SAT). For a Boolean formula on n variables and m clausesof width k, a window of ℓ free variables, and a random assignment of the remain-ing n − ℓ variables, the residual satisfying fraction p is the proportion of the2ℓ window assignments that satisfy the formula. The present work estimatesp on a gate-based quantum computer by amplitude estimation on a clause-by-clause phase-flip oracle, and averages p over random windows to form the LDOSsignature, consisting of its mean, its variance, and its positivity fraction, theprobability that a window remains satisfiable. It is proven that p is estimableto relative precision ε with O(mk/(ε√p)) gates, optimal up to logarithmicfactors. This estimation advantage inherits the known Grover-versus-classical k-SAT decision crossover and appears only at clause width four and above; atclause width three the best known classical algorithm is faster, and no advan-tage is claimed. The principal conceptual result recasts the positivity fractionas a structural lens on the geometry of the solution set. An exact reformulationshows that its leading behaviour is a counting effect, fixed by the window frac-tion and the clause width and carrying no dependence on the freezing transitionof random SAT; a dedicated sweep of the window fraction is required to isolateany freezing-specific signal, and a preliminary classical experiment confirms thecounting-driven behaviour. The present work asserts no quantum-versus-classicalhardness separation.
Abstract The Boolean satisfiability problem (SAT), in particular 3SAT with its bounded clause size, is a well-studied problem since a wide range of decision problems can be reduced to it. The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate for solving 3SAT for Noisy Intermediate-Scale Quantum devices in the near future due to its simple quantum ansatz. However, although QAOA generally exhibits a high approximation ratio, there are 3SAT problem instances where the algorithm’s success probability when obtaining a satisfying variable assignment from the approximated solution drops sharply compared to the approximation ratio. To address this problem, in this paper, we present variants of the algorithm that are inspired by the amplitude amplification algorithm to improve the success probability for 3SAT. For this, (i) three amplitude amplification-inspired QAOA variants are introduced and implemented, (ii) the variants are experimentally compared with a standard QAOA implementation, and (iii) the impact on the success probability and ansatz complexity is analyzed. The experiment results show that an improvement in the success probability can be achieved with only a moderate increase in circuit complexity.
I describe one quantum approach to solving 3-satisfiability (3-SAT), the well known problem in computer science. The approach is based on repeatedly measuring the truth value of the clauses forming the 3-SAT proposition using a non-orthogonal basis. If the basis slowly evolves then there is a strong analogy to adiabatic quantum computing, although the approach is entirely circuit-based. To solve a 3-SAT problem of n variables requires a quantum register of nnn qubits, or more precisely rebits i.e. qubits whose phase need only be real. For cases of up to n=26 qubits numerical simulations indicate that the algorithm runs fast, outperforming Grover's algorithm and having a scaling with n that is superior to the best reported classical algorithms. There are indications that the approach has an inherent robustness versus imperfections in the elementary operations.
The constraint satisfaction problems k-SAT and Quantum k-SAT (k-QSAT) are canonical NP-complete and QMA_1-complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with one-sided error. Whereas k-SAT has been well-studied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry; we hope these prove useful elsewhere.
We present the results of a numerical study, with 20 qubits, of the performance of the Quantum Adiabatic Algorithm on randomly generated instances of MAX 2-SAT with a unique assignment that maximizes the number of satisfied clauses. The probability of obtaining this assignment at the end of the quantum evolution measures the success of the algorithm. Here we report three strategies which consistently increase the success probability for the hardest instances in our ensemble: decreasing the overall evolution time, initializing the system in excited states, and adding a random local Hamiltonian to the middle of the evolution.