Quantum-accelerated Global Constraint FilteringMotivated by recent advances in quantum algorithms and gate-model quantum computation, we introduce quantum-accelerated filtering algorithms for global constraints in constraint programming. We adapt recent work in quantum algorithms for graph problems and identify quantum subroutines that accelerate the main domain consistency algorithms for the all different constraint and the global cardinality constraint (gcc). The subroutines are based on quantum algorithms for finding maximum matchings and strongly connected components in graphs, and provide speedups over the best classical algorithms. We detail both complete and bounded-probability frameworks for quantum-accelerated global constraint filtering algorithms within backtracking search.
Document ID
20205003667
Acquisition Source
Ames Research Center
Document Type
Conference Paper
Authors
Kyle E C Booth (Universities Space Research Association Columbia, Maryland, United States)
Bryan O'Gorman (University of California, Berkeley Berkeley, California, United States)
Jeffrey Marshall (Universities Space Research Association Columbia, Maryland, United States)
Stuart Hadfield (Universities Space Research Association Columbia, Maryland, United States)
Eleanor Rieffel (Ames Research Center Mountain View, California, United States)
Date Acquired
June 18, 2020
Subject Category
Computer Operations And Hardware
Meeting Information
Meeting: 26th International Conference on Principles and Practice of Constraint Programming