Finding solutions to MaxSAT in a quantum computer

Abstract We introduce a quantum algorithm designed to encode a 3-MaxSAT instance f(z) comprising n Boolean variables and m clauses. In the initial stage, we construct an unitary operator F ∈ SU(2n) whose corresponding eigenvalues are phase-encoded to reflect the total count of non-satisfiable clauses observed when evaluating f(z) under a truth assignment (a potential solution) ϕj . Our second stage consists in combining F along Quantum Phase Estimation to map the induced phase shifts into measurable quantum states in only O(mlog(m)) time due to commuting properties of F. Our objective is to identify a state |ϕj⟩ with the smallest phase shift induced by F. Such eigenstate |ϕj⟩ directly corresponds to the truth assignment minimizing the count of non-satisfiable clauses, thereby constituting our solution for f(z). We demonstrate how we can use this encoding along with Amplitude Amplification to find such solutions to MaxSAT in O(mlog(m)1.414n) time. In perspective, this search algorithm may represent an exponential speedup over MaxSAT algorithms, whose complexity grows exponentially as a function of the number of clauses.