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

Abstract

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.

69 pages, 29 figures; corrected affiliations and acknowledgements, added some details, fixed typos

References in corpus (11)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Theory of Quantum Annealing of an Ising Spin Glass
• Experimental Demonstration of a Robust and Scalable Flux Qubit
• Experimental implementation of an adiabatic quantum optimization algorithm
• A scalable readout system for a superconducting adiabatic quantum optimization system
• Thermally assisted adiabatic quantum computation
• A Compound Josephson Junction Coupler for Flux Qubits With Minimal Crosstalk
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
• Quantum Annealing in a Kinetically Constrained System
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

Cited by in corpus (13)

• A case study in programming a quantum annealer for hard operational planning problems
• Adiabatic Quantum Simulation of Quantum Chemistry
• Quantum phase transitions in transverse field spin models: from statistical physics to quantum information
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Multivariable Optimization: Quantum Annealing & Computation
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Adiabatic Quantum Optimization for Associative Memory Recall
• Graph Coloring with Quantum Annealing
• Totally Corrective Boosting with Cardinality Penalization
• Quantum Annealing and Computation: A Brief Documentary Note
• A QUBO Model for Gaussian Process Variance Reduction
• Quantum distance-based classifier with constant size memory, distributed knowledge and state recycling