Name
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1017/S0269888916000278 | KNOWLEDGE ENGINEERING REVIEW |
Field | DocType | Volume |
Quantum,Embedding,Quadratic unconstrained binary optimization,Parametrization,Computer science,Theoretical computer science,Compiler,Quantum annealing,restrict,Management science | Journal | 31 |
Issue | ISSN | Citations |
5.0 | 0269-8889 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bryan O'Gorman | 1 | 1 | 0.79 |
| Eleanor Rieffel | 2 | 488 | 48.71 |
| Minh Binh Do | 3 | 289 | 22.14 |
| Davide Venturelli | 4 | 90 | 9.06 |
| Jeremy Frank | 5 | 216 | 23.82 |