Quantum-accelerated 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 augmented with logical inference. In this paper, we show how quantum algorithms can accelerate CP, at both the levels of inference and search. Leveraging existing quantum algorithms, we introduce a quantum-accelerated filtering algorithm for the alldifferent global constraint and discuss its applicability to a broader family of global constraints with similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, including a novel hybrid classical-quantum backtracking search method. This work suggests that CP is a promising candidate application for early fault-tolerant quantum computers and beyond.

约束规划（CP）是一种用于对约束满足和组合优化问题进行建模和求解的范式。在约束规划中，问题通过描述可接受解的约束进行建模，并通过结合逻辑推理的回溯树搜索来求解。在本文中，我们展示了量子算法如何在推理和搜索两个层面加速约束规划。利用现有的量子算法，我们针对全局全不同约束引入了一种量子加速过滤算法，并讨论了其对具有类似结构的更广泛的全局约束族的适用性。我们提出了在经典和量子回溯搜索方案中整合量子过滤算法的框架，包括一种新颖的混合经典 - 量子回溯搜索方法。这项工作表明，约束规划是早期容错量子计算机及以后的有前景的候选应用。