Heterogeneous Quantum Computing for Satellite Constellation Optimization: Solving the Weighted K-Clique Problem
arXiv:1709.05381 · doi:10.1088/2058-9565/aaadc2
Abstract
NP-hard optimization problems scale very rapidly with problem size, becoming unsolvable with brute force methods, even with supercomputing resources. Typically, such problems have been approximated with heuristics. However, these methods still take a long time and are not guaranteed to find an optimal solution. Quantum computing offers the possibility of producing significant speed-up and improved solution quality. Current quantum annealing (QA) devices are designed to solve difficult optimization problems, but they are limited by hardware size and qubit connectivity restrictions. We present a novel heterogeneous computing stack that combines QA and classical machine learning, allowing the use of QA on problems larger than the hardware limits of the quantum device. These results represent experiments on a real-world problem represented by the weighted k-clique problem. Through this experiment, we provide insight into the state of quantum machine learning.
arXiv comment16 pages, 6 figures
References in corpus (10)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Architectural considerations in the design of a superconducting quantum annealing processor
- What is the Computational Value of Finite Range Tunneling?
- A practical heuristic for finding graph minors
- Optimized simulated annealing for Ising spin glasses
- Prime factorization using quantum annealing and computational algebraic geometry
- Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing