A case study in programming a quantum annealer for hard operational planning problems
From MaRDI portal
Publication:2018131
DOI10.1007/S11128-014-0892-XzbMATH Open1311.81084arXiv1407.2887OpenAlexW1979392010MaRDI QIDQ2018131FDOQ2018131
Authors: Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman, Minh B. Do, Elicia M. Prystay, V. N. Smelyanskiy 
Publication date: 13 April 2015
Published in: Quantum Information Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1407.2887
Recommendations
- Quantum annealing of hard problems
- Building an iterative heuristic solver for a quantum annealer
- Practical integer-to-binary mapping for quantum annealers
- Quantum Annealing with Anneal Path Control: Application to 2-SAT Problems with Known Energy Landscapes
- Benchmarking advantage and D-wave 2000Q quantum annealers with exact cover problems
Cites Work
- Title not available (Why is that?)
- Fast planning through planning graph analysis
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Adiabatic quantum programming: minor embedding with hard faults
- STRIPS: A new approach to the application of theorem proving to problem solving
- Colloquium: Quantum annealing and analog quantum computation
- Pseudo-Boolean optimization
- Title not available (Why is that?)
- Resource efficient gadgets for compiling adiabatic quantum optimization problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quantum computing. A gentle introduction
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Almost all graphs with average degree 4 are 3-colorable
- The 3-XORSAT threshold.
- Upper-bounding the \(k\)-colorability threshold by counting covers
- Title not available (Why is that?)
- Complexity results for standard benchmark domains in planning
- Title not available (Why is that?)
Cited In (36)
- Deep learning optimal quantum annealing schedules for random Ising models
- Mapping a logical representation of TSP to quantum annealing
- Hard combinatorial problems and minor embeddings on lattice graphs
- Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
- Models in quantum computing: a systematic review
- Statistical Analysis of Quantum Annealing
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- A subgradient approach for constrained binary optimization via quantum adiabatic evolution
- Embedding equality constraints of optimization problems into a quantum annealer
- Biclustering with a quantum annealer
- Privacy-enhanced multi-user quantum private data query using partial quantum homomorphic encryption
- A comparison of approaches for finding minimum identifying codes on graphs
- Inter-generational comparison of quantum annealers in solving hard scheduling problems
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
- Garden optimization problems for benchmarking quantum annealers
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Modeling the Costas array problem in QUBO for quantum annealing
- Quantum Computing Meets the Real World
- Large-scale vehicle routing problems: quantum annealing, tunings and results
- Differential geometric treewidth estimation in adiabatic quantum computation
- Evaluating the practicality of quantum optimization algorithms for prototypical industrial applications
- Minor embedding in broken chimera and derived graphs is NP-complete
- Quantum computing and tensor networks for laminate design: a novel approach to stacking sequence retrieval
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Quantum annealing versus digital computing. An experimental comparison
- Efficiently embedding QUBO problems on adiabatic quantum computers
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Minimizing minor embedding energy: an application in quantum annealing
- Enhancing quantum annealing performance for the molecular similarity problem
- Quantum annealing with Markov chain Monte Carlo simulations and D-wave quantum computers
- Building an iterative heuristic solver for a quantum annealer
- Embedding of complete graphs in broken Chimera graphs
- The potential of quantum annealing for rapid solution structure identification
- Practical integer-to-binary mapping for quantum annealers
- Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling
Uses Software
This page was built for publication: A case study in programming a quantum annealer for hard operational planning problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018131)
