Quantum-accelerated constraint programming

Abstract

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 $\text{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.

published in Quantum

References in corpus (19)

• Quantum Algorithms Revisited
• Quantum random access memory
• Tight bounds on quantum searching
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Quantum Algorithm for Finding the Minimum
• On the robustness of bucket brigade quantum RAM
• Quantum query complexity of some graph problems
• Nested quantum search and NP-complete problems
• The alldifferent Constraint: A Survey
• Fault tolerant resource estimation of quantum random-access memories
• Quantum SDP-Solvers: Better upper and lower bounds
• Applying quantum algorithms to constraint satisfaction problems
• Experimental realization of 105-qubit random access quantum memory
• Quantum speedup of branch-and-bound algorithms
• Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
• Quantum Walks and Electric Networks
• Quantum Speedup Based on Classical Decision Trees
• Improved quantum backtracking algorithms using effective resistance estimates
• Hybrid divide-and-conquer approach for tree search algorithms

Cited by in corpus (7)

• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• A "thoughtful" Local Friendliness no-go theorem: a prospective experiment with new assumptions to suit
• Tower: Data Structures in Quantum Superposition
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device