Comparing planning problem compilation approaches for quantum annealing. (22nd February 2017)

• Record Type: Journal Article
• Authors: O'Gorman, Bryan; Rieffel, Eleanor Gilbert; Do, Minh; Venturelli, Davide; Frank, Jeremy
• Is Part Of: Knowledge engineering review. Volume 31:Number 5(2016)
• Page Start: 465
• Page End: 474
• Publication Date: 2017-02-22
• Subjects: Expert systems (Computer science) -- Periodicals; 006.33
• DOI: 10.1017/S0269888916000278
• Languages: English
• ISSNs: 0269-8889

Abstract

Abstract: One approach to solving planning problems is to compile them to other problems for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances of quadratic unconstrained binary optimization (QUBO) problem. Early quantum annealers are now available, though their constraints restrict the types of QUBOs they can take as input. Here, we introduce the planning community to the key steps in compiling planning problems to QA hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we describe preliminary results from running an early quantum annealer on a parametrized family of hard planning problems. The results show that different mappings can substantially affect performance, even when many features of the resulting instances are similar. We conclude with insights gained from this early study that suggest directions for future work.