  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.
