Eleanor G. Rieffel

A case study in programming a quantum annealer for hard operational planning problems

  1. Eleanor G. Rieffel,
  2. Davide Venturelli,
  3. Bryan O'Gorman,
  4. Minh B. Do,
  5. Elicia Prystay,
  6. and Vadim N. Smelyanskiy
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 performance
of 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.
arxiv pdf

A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration

  1. Vadim N. Smelyanskiy,
  2. Eleanor G. Rieffel,
  3. Sergey I. Knysh,
  4. Colin P. Williams,
  5. Mark W. Johnson,
  6. Murray C. Thom,
  7. William G. Macready,
  8. and Kristen L. Pudenz
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 quantum
annealing 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.
arxiv pdf