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 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.
Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.
Local Quantum Search Algorithm for Random k-SAT with Ω(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, 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.
Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximum-satisfiability (MAX-SAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in real-world scenarios, this problem is typically infeasible even when using state-of-the-art algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealing-based solutions. We present the overall approach and compare results from the D-Wave quantum annealer against the best-known classical algorithms such as the Hamze-de Freitas-Selby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.
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+k) and yields the running time (2−2/(1+k))n, up to polynomial factors—1.268n for k=3, below the best known classical 1.307n. 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.
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.
Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is to decide whether a particular type of local Hamiltonian has a ground state with zero energy. We consider random quantum k-SAT formulas with n variables and m = αn clauses, and ask at what value of αthese formulas cease to be satisfiable. We show that the threshold for random quantum 3-SAT is at most 3.594. For comparison, convincing arguments from statistical physics suggest that the classical 3-SAT threshold is α\approx 4.267. For larger k, we show that the quantum threshold is a constant factor smaller than the classical one. Our bounds work by determining the generic rank of the satisfying subspace for certain gadgets, and then using the technique of differential equations to analyze various algorithms that partition the hypergraph into a collection of these gadgets. Our use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.