This academic paper explores the resolution of the 3-SAT problem using a QAOA-like approach. The authors model the solution ranks of the 3-SAT problem, which, in this specific case, directly represent a solution. This modeling results in a compact circuit with fewer gates, enabling the modeling of large-sized 3-SAT problems. The authors demonstrate through numerical experimentation that their approach can solve instances composed of 91 clauses and 20 variables with an implementation based on Qiskit. The paper also discusses the broader context of SAT resolution and computational complexity theory.
Publication date: 2 Feb 2024
Project Page: Not Provided
Paper: https://arxiv.org/pdf/2402.00065
