Planted-solution SAT and Ising benchmarks from integer factorization

Quantum Physics [Submitted on 10 Apr 2026] Planted-solution SAT and Ising benchmarks from integer factorization Itay Hen We present a family of planted-solution benchmark instances for satisfiability (SAT) solvers and Ising optimization derived from integer factorization. Given two primes p and q, the construction encodes the arithmetic constraints of N = p \times q as a conjunctive normal form (CNF) formula whose satisfying assignments correspond to valid factorizations of~N. The known pair (p,q) serves as a built-in ground truth, enabling unambiguous verification of solver output. We show that for two d-bit primes the total number of carry contractions is on the order of d^4. Empirical benchmarks with SAT solvers show that median runtime grows exponentially in the bit-length of the factors over the range tested. The construction provides a scalable, structured, and verifiable benchmark family controlled by a single parameter, accompanied by open-source generation software. Comments: 11 pages; 4 figures Subjects: Quantum Physics (quant-ph); Logic in Computer Science (cs.LO) Cite as: arXiv:2604.09837 [quant-ph]   (or arXiv:2604.09837v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.09837 Focus to learn more Submission history From: Itay Hen [view email] [v1] Fri, 10 Apr 2026 19:09:24 UTC (173 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 Change to browse by: cs 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?)