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

Abstract

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.

19 pages, 16 figures. Comments welcome

References in corpus (12)

• PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains
• Defining and detecting quantum speedup
• Simulating chemistry using quantum computers
• The 3rd International Planning Competition: Results and Analysis
• A practical heuristic for finding graph minors
• Quantum Optimization of Fully-Connected Spin Glasses
• Adiabatic Quantum Simulation of Quantum Chemistry
• Bayesian Network Structure Learning Using Quantum Annealing
• How "Quantum" is the D-Wave Machine?
• A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration
• Comment on "Distinguishing Classical and Quantum Models for the D-Wave Device"
• On the non-3-colourability of random graphs

Cited by in corpus (77)

• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Perspectives of quantum annealing: Methods and implementations
• Quantum Annealing for Industry Applications: Introduction and Review
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
• Continuous-variable quantum key distribution with non-Gaussian quantum catalysis
• Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Quantum Annealing for Constrained Optimization
• Bayesian Network Structure Learning Using Quantum Annealing
• Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• Multivariable Optimization: Quantum Annealing & Computation
• Quantum Computing Assisted Deep Learning for Fault Detection and Diagnosis in Industrial Process Systems
• Driver Hamiltonians for constrained optimization in quantum annealing
• Flight Gate Assignment with a Quantum Annealer
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Quantum machine learning and quantum biomimetics: A perspective
• Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
• Maximum-Entropy Inference with a Programmable Annealer
• Prospects and challenges of quantum finance
• A Quantum Model for Coherent Ising Machines: Discrete-time Measurement Feedback Formulation
• Readiness of Quantum Optimization Machines for Industrial Applications
• Quantum processor-inspired machine learning in the biomedical sciences
• Enhancing Quantum Annealing Performance for the Molecular Similarity Problem
• Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Practical Integer-to-Binary Mapping for Quantum Annealers
• Constrained quantum annealing of graph coloring
• Combinatorial Optimization on Gate Model Quantum Computers: A Survey
• Degeneracy, degree, and heavy tails in quantum annealing
• Evaluating Ising Processing Units with Integer Programming
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Ferromagnetically shifting the power of pausing
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Embedding of Complete Graphs in Broken Chimera Graphs
• Minor Embedding in Broken Chimera and Pegasus Graphs is NP-complete
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Counterdiabatic Reverse Annealing
• Parity Quantum Optimization: Encoding Constraints
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• Deep learning optimal quantum annealing schedules for random Ising models
• Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Mean-field Coherent Ising Machines with artificial Zeeman terms
• Advantage of pausing: parameter setting for quantum annealers
• A small-world search for quantum speedup: How small-world interactions can lead to improved quantum annealer designs
• Lossy compression of statistical data using quantum annealer
• Using continuation methods to analyse the difficulty of problems solved by Ising machines
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Localization in the constrained quantum annealing of graph coloring
• Quantum-assisted finite-element design optimization
• Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
• Quantum annealing with pairs of ${}^2\Sigma$ molecules as qubits
• Performance Models for Split-execution Computing Systems
• Applications of Quantum Annealing in Statistics
• Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
• Quantum annealing of Cayley-tree Ising spins at small scales
• Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
• Analysis of the Hopfield Model with Discrete Coupling
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Decoding quantum error correction with Ising model hardware
• Minor Embedding for Quantum Annealing with Reinforcement Learning
• Hard combinatorial problems and minor embeddings on lattice graphs
• A QUBO Model for Gaussian Process Variance Reduction
• Minimizing minor embedding energy: an application in quantum annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• Statistical Analysis of Quantum Annealing