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)- Mapping a logical representation of TSP to quantum annealing
- Deep learning optimal quantum annealing schedules for random Ising models
- Hard combinatorial problems and minor embeddings on lattice graphs
- Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
- Optimizing adiabatic quantum program compilation using a graph-theoretic framework
- Models in quantum computing: a systematic review
- A subgradient approach for constrained binary optimization via quantum adiabatic evolution
- Statistical Analysis of Quantum Annealing
- 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
- Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
- Inter-generational comparison of quantum annealers in solving hard scheduling problems
- Garden optimization problems for benchmarking quantum annealers
- A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
- 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
- Systematic and deterministic graph minor embedding for Cartesian products of graphs
- Efficiently embedding QUBO problems on adiabatic quantum computers
- 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
- Quantum annealing versus digital computing. An experimental comparison
- 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
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)
