Search-Driven Clause Learning for Product-State Quantum k k -SAT (PRODSAT-QSAT)

Samuel González-Castillo, Joon Hyung Lee, Alfons Laarman · 2026

Read Search-Driven Clause Learning for Product-State Quantum k k -SAT (PRODSAT-QSAT) by Samuel González-Castillo, Joon Hyung Lee, Alfons Laarman (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20038.txt.

Introduction

González-Castillo, Lee, and Laarman build a clause-learning solver for product-state quantum satisfiability. The task asks if a set of local projectors admits a state that factors across qubits. Their method borrows the conflict-driven style of classical SAT solvers. Each qubit's Bloch sphere is split into finitely many regions. A sound theory solver checks if any state in a region can meet a constraint. When it proves none can, it emits a blocking clause. Enough clauses can prove no product state works at all.

Catalog record

CREATORSamuel González-Castillo, Joon Hyung Lee, Alfons Laarman
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48305
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20038

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Search-Driven Clause Learning for Product-State Quantum k k -SAT (PRODSAT-QSAT) Samuel González-Castillo, Joon Hyung Lee, Alfons Laarman Abstract We study PRODSAT-QSAT( k k ): given rank-one k k -local projectors, determine whether a quantum k k -SAT instance admits a satisfying product state. We present a CDCL-style refutation framework that searches a finite partition of each qubit’s Bloch sphere while a sound theory solver checks region feasibility using a geometric over-approximation of the projection amplitudes for each constraint. When the theory solver proves that no state in a region can satisfy a constraint, it produces a sound conflict clause that blocks that region; accumulated blocking clauses can yield a global result of product-state unsatisfiability (UN-PRODSAT). We formalise the problem, prove the soundness of the clause-learning rule, and describe a practical algorithm and implementation. 1 Introduction Quantum k -SAT ( k -QSAT) asks whether there exists an n -qubit state annihilated by a set of local projectors \Pi_{j} . Equivalently, given a Hamiltonian H\coloneq\sum_{j}\Pi_{j} , the problem asks whether H is frustration-free, i.e., if its ground energy is zero. The subject is a quantum analog of the classical problem of k -SAT, but much less explored. There have been successful discoveries. It was first studied by Kitaev [ 12 ] . 2 -QSAT has been proven to be easy to solve in [ 4 , 6 ] . The condition to have product state solutions and the algorithm to have such solutions have been proven in [ 15 ] , which still leaves many questions to explore. For instance, the algorithm given in [ 15 ] is doubly exponential. It also opens questions about the phase beyond product state phase, namely entangled state and UNSAT. In analogy to how k -SAT is NP-complete for k\geq 3 , k -QSAT is QMA-complete for k\geq 3 , as shown in [ 8 ] . Even for small sizes, heuristic solvers must navigate a nonconvex, high-dimensional landscape. From an algorithmic perspective, it is natural to seek satisfiable states within structured ansätze. In this work we focus on the product-state ansatz, which is both physically meaningful and algorithmically tractable. Specifically, we aim to certify the absence of product state solutions (UN-PRODSAT) of a finite size k -QSAT leveraging the principle of conflict-driven clause learning (CDCL) [ 9 , 16 ] . The product state is defined as follows: \left|\psi\right\rangle=\bigotimes_{j=1}^{n}\left|\psi_{j}\right\rangle,\qquad\left|\psi_{j}\right\rangle\in\mathbb{C}^{2},\ \left\|\left|\psi_{j}\right\rangle\right\|=1. (1) We develop a clause-learning framework for this setting, that helps guide a dichotomic search over the state space. The key idea is to discretize the single-qubit manifold into finitely many regions and let a CDCL SAT solver [ 9 , 16 , 17 ] search over regions while a continuous theory solver checks feasibility inside a region using interval arithmetic. When feasibility fails, a sound conflict clause can be produced. Problem definition. Fix n qubits. For each constraint j\in[m] , let S_{j}\subseteq[n] be a subset with \left|S_{j}\right|=k and let \Pi_{j} be a rank-one projector supported on S_{j} : \Pi_{j}\;=\;\left|v_{j}\right\rangle\left\langle v_{j}\right|,\qquad\left|v_{j}\right\rangle\in(\mathbb{C}^{2})^{\otimes k},\ \left\|\left|v_{j}\right\rangle\right\|=1. For a global state \left|\psi\right\rangle\in(\mathbb{C}^{2})^{\otimes n} , let \left|\psi_{S_{j}}\right\rangle denote the projected state on S_{j} . We interpret \Pi_{j} as excluding the local state \left|v_{j}\right\rangle : a global state \left|\psi\right\rangle satisfies constraint j if and only if \Pi_{j}\left|\psi\right\rangle=0\quad\Longleftrightarrow\quad\left\langle v_{j}\,\middle|\,\psi_{S_{j}}\right\rangle=0. Definition 1 (PRODSAT-QSAT( k )) . Given rank-one k -local projectors \Pi_{1},\dots,\Pi_{m} , decide whether there exists a product state \left|\psi\right\rangle=\bigotimes_{j=1}^{n}\left|\psi_{j}\right\rangle such that \Pi_{j}\left|\psi\right\rangle=0 for all j\in[m] . Contributions. • We formalize PRODSAT-QSAT( k ) and an algorithm architecture tailored to certify product-state unsatisfiability. • We give a sound clause-learning rule based on interval exclusion of zero from projection amplitudes. • We propose practical rules for clause learning and provide an implementation of our algorithm. In particular, we introduce a theory solver (Algorithm 1 ) that can detect product-state unsatisfiability of individual QSAT( k ) constraints in a family of regions in the product state space. Building on this, we use our clause-learning framework to define an algorithm (Algorithm 3 ) that is backed by the following result: Theorem 1 . Fix k and consider a QSAT( k ) instance. Algorithm 3 runs, in the worst-case scenario, in exponential time in the number of qubits. It returns UN-PRODSAT if it can certify that its input instance is UN-PRODSAT. Otherwise, it returns MAYBE( A , \rho ), where A and \rho are the sums of, respectively, the area and the maximum modulus squared of the set over-approximations constructed by the theory solver. In the result above, the parameters A and \rho act as heuristic indicators of how likely the instance is to be PRODSAT when the algorithm cannot certify that it is UN-PRODSAT. Smaller values of those parameters would imply a higher likelihood. Paper outline. • In Section 2 , we develop the geometric tools used by the theory solver. • In Section 3 , we introduce the theory solver (Algorithm 1 ) and discuss and prove its soundness guarantees (summarised in Proposition 1 ). • In Section 4 , we discuss the overall CDCL-based architecture and the clause-learning rule, and we prove Theorem 1 . • In Section 5 , we discuss our implementation and share empirical observations. • Finally, we summarise our results in Section 6 . 2 Geometric preliminaries With a product state \left|\psi\right\rangle , write each single-qubit state (up to global phase) in Bloch coordinates: \left|\psi_{j}\right\rangle=\left|\Psi(\theta_{j},\varphi_{j})\right\rangle\;=\;\cos(\theta_{j}/2)\left|0\right\rangle+e^{i\varphi_{j}}\sin(\theta_{j}/2)\left|1\right\rangle,\qquad\theta_{j}\in[0,\pi],\ \varphi_{j}\in[0,2\pi). For a constraint \Pi_{i}=\left|v_{i}\right\rangle\left\langle v_{i}\right| supported on S_{i}=\{i_{1},\dots,i_{k}\} , \Pi_{i}\left|\psi\right\rangle=0 is equivalent to \left\langle v_{i}\right|\cdot\bigotimes_{j\in S_{i}}\left|\Psi(\theta_{j},\varphi_{j})\right\rangle. Given some complex numbers p_{1},\ldots,p_{\ell} (with \ell\geq 2 ), we write \operatorname{poly}[p_{1},\ldots,p_{\ell}] to denote the polygon in the complex plane with edges [p_{1},p_{2}],\ldots,[p_{\ell-1},p_{\ell}],[p_{\ell},p_{1}] . Notice how we consider segments to be polygons (when \ell=2 ). Moreover, given any real numbers r_{0},r_{1},\varphi_{0},\varphi_{1} with 0\leq r_{0}\leq r_{1} and \varphi_{0}\leq\varphi_{1} , we will consider the annular sector \operatorname{Ann}(r_{0},r_{1};\varphi_{0},\varphi_{1})\coloneq[r_{0},r_{1}]e^{i[\varphi_{0},\varphi_{1}]}, which is depicted in Figure 1(a) . Given any two sets A,B\subseteq\mathbb{C} , we define their Minkowski sum and product to be, respectively, A\oplus B\coloneq\{a+b\mid a\in A,b\in B\},\qquad A\odot B\coloneq\{a\cdot b\mid a\in A,b\in B\}. Moreover, for any set A\subseteq\mathbb{C} , we write \operatorname{conv}A to denote its convex hull : the smallest convex subset of \mathbb{C} containing A . Of course, in particular, for any points p_{1},\ldots,p_{n}\in\mathbb{C} , we have [ 14 ] \operatorname{conv}\{p_{1},\ldots,p_{\ell}\}\coloneq\left\{\sum_{r=1}^{\ell}\lambda_{r}p_{r}\,\middle|\,\lambda_{r}\in\mathbb{R}_{\geq 0},\sum_{r=1}^{\ell}\lambda_{r}=1\right\}, and, if \operatorname{poly}[p_{1},\ldots,p_{\ell}] is a convex polygon, then \operatorname{poly}[p_{1},\ldots,p_{\ell}]=\operatorname{conv}\{p_{1},\ldots,p_{\ell}\} . If a state \left|\psi\right\rangle of the form \left|\psi(\theta,\varphi)\right\rangle satisfies \theta\in[\theta_{0},\theta_{1}] and \varphi\in[\varphi_{0},\varphi_{1}] , then \left\langle 0\,\middle|\,\psi\right\rangle\in\cos([\theta_{0}/2,\theta_{1}/2]),\qquad\left\langle 1\,\middle|\,\psi\right\rangle\in\sin([\theta_{0}/2,\theta_{1}/2])e^{i[\varphi_{0},\varphi_{1}]}, hence the amplitude \left\langle 0\,\middle|\,\psi\right\rangle lies in the interval [s_{0},s_{1}]\coloneq\cos([\theta_{0}/2,\theta_{1}/2]) , which can be identified as the annular sector \operatorname{Ann}(s_{0},s_{1};0,0) , whereas the amplitude \left\langle 1\,\middle|\,\psi\right\rangle lies in the annular sector \operatorname{Ann}(r_{0},r_{1};\varphi_{0},\varphi_{1}) with [r_{0},r_{1}]\coloneq\sin([\theta_{0}/2,\theta_{1}/2]) . Therefore, both amplitudes take values in annular sectors. Computing the Minkowski product of annular sectors is very straightforward, as the following result shows. Lemma 1 . Let \operatorname{Ann}(r_{0},r_{1},\varphi_{0},\varphi_{1}) and \operatorname{Ann}(s_{0},s_{1},\theta_{0},\theta_{1}) be annular sectors. Their Minkowski product can be computed as \operatorname{Ann}(r_{0},r_{1},\varphi_{0},\varphi_{1})\odot\operatorname{Ann}(s_{0},s_{1},\theta_{0},\theta_{1})=\operatorname{Ann}(r_{0}s_{0},r_{1}s_{1},\varphi_{0}+\theta_{0},\varphi_{1}+\theta_{1}). Proof. Taking into account that addition and multiplication are continuous and monotone, we only need to consider the fact that closed intervals are connected and compact, and that, for any real numbers r,s,\theta,\varphi , we have r\exp(i\varphi)\cdot s\exp(i\theta)=rs\exp(i(\varphi+\theta)) . ∎ r_{1}e^{i\varphi_{0}} r_{1}e^{i\varphi_{1}} r_{0}e^{i\varphi_{0}} r_{0}e^{i\varphi_{1}} (a) Annular sector \operatorname{Ann}(r_{0},r_{1};\varphi_{0},\varphi_{1}) . A D C B O (b) Representation of the polygonal enclosure (in red) of an annular

Read the complete text