A case study in programming a quantum annealer for hard operational planning problems
From MaRDI portal
Publication:2018131
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.
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
- scientific article; zbMATH DE number 67483 (Why is no real title available?)
- scientific article; zbMATH DE number 2038892 (Why is no real title available?)
- scientific article; zbMATH DE number 2038893 (Why is no real title available?)
- scientific article; zbMATH DE number 1380613 (Why is no real title available?)
- scientific article; zbMATH DE number 2201583 (Why is no real title available?)
- scientific article; zbMATH DE number 2243410 (Why is no real title available?)
- Adiabatic quantum programming: minor embedding with hard faults
- Almost all graphs with average degree 4 are 3-colorable
- Colloquium: Quantum annealing and analog quantum computation
- Complexity results for standard benchmark domains in planning
- Fast planning through planning graph analysis
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
- Pseudo-Boolean optimization
- Quantum computing. A gentle introduction
- Resource efficient gadgets for compiling adiabatic quantum optimization problems
- STRIPS: A new approach to the application of theorem proving to problem solving
- The 3-XORSAT threshold.
- Upper-bounding the \(k\)-colorability threshold by counting covers
Cited in
(36)- Quantum annealing with Markov chain Monte Carlo simulations and D-wave quantum computers
- Quantum annealing versus digital computing. An experimental comparison
- Embedding equality constraints of optimization problems into a quantum annealer
- A subgradient approach for constrained binary optimization via quantum adiabatic evolution
- Enhancing quantum annealing performance for the molecular similarity problem
- The potential of quantum annealing for rapid solution structure identification
- Deep learning optimal quantum annealing schedules for random Ising models
- Efficiently embedding QUBO problems on adiabatic quantum computers
- Modeling the Costas array problem in QUBO for quantum annealing
- A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
- Minor embedding in broken chimera and derived graphs is NP-complete
- Building an iterative heuristic solver for a quantum annealer
- Large-scale vehicle routing problems: quantum annealing, tunings and results
- Quantum Computing Meets the Real World
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Practical integer-to-binary mapping for quantum annealers
- Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling
- Garden optimization problems for benchmarking quantum annealers
- Minimizing minor embedding energy: an application in quantum annealing
- Models in quantum computing: a systematic review
- Quantum computing and tensor networks for laminate design: a novel approach to stacking sequence retrieval
- Privacy-enhanced multi-user quantum private data query using partial quantum homomorphic encryption
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Hard combinatorial problems and minor embeddings on lattice graphs
- Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
- Statistical Analysis of Quantum Annealing
- Differential geometric treewidth estimation in adiabatic quantum computation
- Mapping a logical representation of TSP to quantum annealing
- Evaluating the practicality of quantum optimization algorithms for prototypical industrial applications
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Biclustering with a quantum annealer
- A comparison of approaches for finding minimum identifying codes on graphs
- Embedding of complete graphs in broken Chimera 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
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)
