We report on a case study in programming an early quantum annealer to attack optimization problems related to operational planning. While a number of studies have looked at the performanceof quantum annealers on problems native to their architecture, and others have examined performance of select problems stemming from an application area, ours is one of the first studies of a quantum annealer’s performance on parametrized families of hard problems from a practical domain. We explore two different general mappings of planning problems to quadratic unconstrained binary optimization (QUBO) problems, and apply them to two parametrized families of planning problems, navigation-type and scheduling-type. We also examine two more compact, but problem-type specific, mappings to QUBO, one for the navigation-type planning problems and one for the scheduling-type planning problems. We study embedding properties and parameter setting, and examine their effect on the efficiency with which the quantum annealer solves these problems. From these results we derive insights useful for the programming and design of future quantum annealers: problem choice, the mapping used, the properties of the embedding, and the annealing profile all matter, each significantly affecting the performance.
In this article, we show how to map a sampling of the hardest artificial
intelligence problems in space exploration onto equivalent Ising models that
then can be attacked using quantumannealing implemented in D-Wave machine. We
overview the existing results as well as propose new Ising model
implementations for quantum annealing. We review supervised and unsupervised
learning algorithms for classification and clustering with applications to
feature identification and anomaly detection. We introduce algorithms for data
fusion and image matching for remote sensing applications. We overview planning
problems for space exploration mission applications and algorithms for
diagnostics and recovery with applications to deep space missions. We describe
combinatorial optimization algorithms for task assignment in the context of
autonomous unmanned exploration. Finally, we discuss the ways to circumvent the
limitation of the Ising mapping using a „blackbox“ approach based on ideas from
probabilistic computing. In this article we describe the architecture of the
D-Wave One machine and report its benchmarks. Results on random ensemble of
problems in the range of up to 96 qubits show improved scaling for median core
quantum annealing time compared with classical algorithms; whether this scaling
persists for larger problem sizes is an open question. We also review previous
results of D-Wave One benchmarking studies for solving binary classification
problems with a quantum boosting algorithm which is shown to outperform
AdaBoost. We review quantum algorithms for structured learning for multi-label
classification and introduce a hybrid classical/quantum approach for learning
the weights. Results of D-Wave One benchmarking studies for learning structured
labels on four different data sets show a better performance compared with an
independent Support Vector Machine approach with linear kernel.