Tabu-driven Quantum Neighborhood Samplers
arXiv:2011.09508 · doi:10.1007/978-3-030-72904-2_7
Abstract
Combinatorial optimization is an important application targeted by quantum computing. However, near-term hardware constraints make quantum algorithms unlikely to be competitive when compared to high-performing classical heuristics on large practical problems. One option to achieve advantages with near-term devices is to use them in combination with classical heuristics. In particular, we propose using quantum methods to sample from classically intractable distributions -- which is the most probable approach to attain a true provable quantum separation in the near-term -- which are used to solve optimization problems faster. We numerically study this enhancement by an adaptation of Tabu Search using the Quantum Approximate Optimization Algorithm (QAOA) as a neighborhood sampler. We show that QAOA provides a flexible tool for exploration-exploitation in such hybrid settings and can provide evidence that it can help in solving problems faster by saving many tabu iterations and achieving better solutions.
arXiv commentCompressed version of the paper with better plots
References in corpus (17)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Parameterized quantum circuits as machine learning models
- Quantum optimization using variational algorithms on near-term quantum devices
- Hybrid quantum-classical algorithms and quantum error mitigation
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum advantage with shallow circuits
- Trading classical and quantum computational resources
- Simulating Large Quantum Circuits on a Small Quantum Computer
- Improving Variational Quantum Optimization using CVaR
- Benchmarking the Quantum Approximate Optimization Algorithm
- Quantum Optimization with a Novel Gibbs Objective Function and Ansatz Architecture Search
- Classical variational simulation of the Quantum Approximate Optimization Algorithm
- Building an iterative heuristic solver for a quantum annealer
- Computational speedups using small quantum devices
- To quantum or not to quantum: towards algorithm selection in near-term quantum optimization