Quantum Computing for Constraint Programming*

Constraint programming (CP) is a paradigm used to model and solve constraint satisfaction and combinatorial optimization problems. In CP, problems are modeled with constraints that describe acceptable solutions, and solved with backtracking tree search interleaved with logical inference. Motivated by recent advances in gate-model quantum computers and quantum algorithms, we investigate the application of quantum computing to CP. We introduce a quantum-accelerated filtering algorithm for the AllDifferent global constraint, leveraging quantum algorithms for graph problems, and demonstrate its applicability in accelerating other global constraints with a similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, providing preliminary resource estimates and a discussion of the tradeoffs therein. We conclude that CP is a promising candidate application for early fault-tolerant quantum computers.