# Quantum-Inspired Approximations to Constraint Satisfaction Problems

arXiv: https://arxiv.org/abs/2212.04016 · HTML: https://mlsanity.com/paper/2212.04016/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 48 references that are in the map.
- First posted on arXiv 8 Dec 2022.

## Builds on (most cited first, 5 of 5)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [On the Complexity of Random Satisfiability Problems with Planted Solutions](https://mlsanity.com/paper/1311.4821/) (2013)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [FourierSAT: A Fourier Expansion-Based Algebraic Framework for Solving Hybrid Boolean Constraints](https://mlsanity.com/paper/1912.01032/) (2019)

## Abstract (arXiv)

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.