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

Quantum Physics [Submitted on 20 Mar 2026] Search-Driven Clause Learning for Product-State Quantum k-SAT (PRODSAT-QSAT) Samuel González-Castillo, Joon Hyung Lee, Alfons Laarman We study PRODSAT-QSAT(k): given rank-one k-local projectors, determine whether a quantum 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 overapproximation 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. Comments: 17 pages plus references, 3 figures, 2 tables, Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Logic in Computer Science (cs.LO) Cite as: arXiv:2603.20038 [quant-ph]   (or arXiv:2603.20038v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.20038 Focus to learn more Submission history From: Joon Hyung Lee [view email] [v1] Fri, 20 Mar 2026 15:22:27 UTC (1,001 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.CC cs.LO References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)