NASA Logo, National Aeronautics and Space Administration

+NASA Home

+Ames Home

Quantum Artificial Intelligence Laboratory Team Publishes Quantum Computing and Constraint Programming Paper
Intelligent Systems Division Banner

Quantum Artificial Intelligence Laboratory Team Publishes Quantum Computing and Constraint Programming Paper

Members of the Quantum Artificial Intelligence Laboratory (QuAIL) at NASA Ames Research Center, together with a former NASA fellowship holder and QuAIL group member now at IBM, have recently published an article entitled, “Quantum-Accelerated Constraint Programming”, in the open source journal Quantum. The paper investigates the impact gate model quantum computing can have on the Constraint programming (CP) paradigm and shows how quantum algorithms can accelerate CP at both the levels of inference and search. The authors propose frameworks for the integration of quantum 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.

BACKGROUND: CP is a backtracking search-based paradigm used for modeling and solving constraint satisfaction and discrete optimization problems, and often competes head-to-head with integer programming approaches. Many leading optimization groups have developed CP modeling/solving software, including IBM and Google. CP search algorithms employ logical inference subroutines at each node in the search to prune values from the domains of the variables that provably will not participate in solutions. The efficacy of CP search, then, is highly dependent on the efficiency of the underlying domain-pruning algorithms. These domain-pruning subproblems provide an elegant mechanism for carving off portions of complex problems into smaller ones that can be solved by a quantum co-processor.

NASA PROGRAM FUNDING: NASA Advanced Explorations Systems Program. Dr. Kyle Booth, Dr. Jeffrey Marshall, and Dr. Stuart Hadfield are supported by the NASA Academic Mission Services (NAMS, contract number NNA16BD14C); Dr. Bryan O’Gorman was supported by a NASA Space Technology Research Fellowship and the National Science Foundation (NSF) Quantum Leap Challenges Institute (QLCI) Program (grant number OMA-2016245).

TEAM: Kyle Booth, Stuart Hadfield, Jeffrey Marshall, Bryan O’Gorman, and Eleanor Rieffel

POINT OF CONTACT: Kyle Booth, kyle.booth@nasa.gov

First Gov logo
NASA Logo - nasa.gov