Quantum-Inspired Approximations to Constraint Satisfaction Problems
This work addresses constraint satisfaction problems for researchers in algorithms and optimization, offering an incremental improvement by applying quantum-inspired methods to enhance solver performance.
The paper tackles constraint satisfaction problems by introducing new algorithms that use Boolean Fourier analysis to approximate satisfying configurations, inspired by quantum amplitude amplification, and demonstrates competitive performance against local solvers for Boolean satisfiability (SAT).
Two contrasting algorithmic paradigms for constraint satisfaction problems are successive local explorations of neighboring configurations versus producing new configurations using global information about the problem (e.g. approximating the marginals of the probability distribution which is uniform over satisfying configurations). This paper presents new algorithms for the latter framework, ultimately producing estimates for satisfying configurations using methods from Boolean Fourier analysis. The approach is broadly inspired by the quantum amplitude amplification algorithm in that it maximally increases the amplitude of the approximation function over satisfying configurations given sequential refinements. We demonstrate that satisfying solutions may be retrieved in a process analogous to quantum measurement made efficient by sparsity in the Fourier domain, and present a complete solver construction using this novel approximation. Freedom in the refinement strategy invites further opportunities to design solvers in an evolutionary computing framework. Results demonstrate competitive performance against local solvers for the Boolean satisfiability (SAT) problem, encouraging future work in understanding the connections between Boolean Fourier analysis and constraint satisfaction.