Hybrid annealing using a quantum simulator coupled to a classical computer
arXiv:1611.09729 · doi:10.1103/PhysRevA.95.052309
Abstract
Finding the global minimum in a rugged potential landscape is a computationally hard task, often equivalent to relevant optimization problems. Simulated annealing is a computational technique which explores the configuration space by mimicking thermal noise. By slow cooling, it freezes the system in a low-energy configuration, but the algorithm often gets stuck in local minima. In quantum annealing, the thermal noise is replaced by controllable quantum fluctuations, and the technique can be implemented in modern quantum simulators. However, quantum-adiabatic schemes become prohibitively slow in the presence of quasidegeneracies. Here we propose a strategy which combines ideas from simulated annealing and quantum annealing. In such hybrid algorithm, the outcome of a quantum simulator is processed on a classical device. While the quantum simulator explores the configuration space by repeatedly applying quantum fluctuations and performing projective measurements, the classical computer evaluates each configuration and enforces a lowering of the energy. We have simulated this algorithm for small instances of the random energy model, showing that it potentially outperforms both simulated thermal annealing and adiabatic quantum annealing. It becomes most efficient for problems involving many quasi-degenerate ground states.
arXiv comment6 pages, 3 figures
References in corpus (18)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- An Elementary Quantum Network of Single Atoms in Optical Cavities
- Observation of entanglement propagation in a quantum many-body system
- Demonstration of a neutral atom controlled-NOT quantum gate
- Non-local propagation of correlations in long-range interacting quantum systems
- Demonstration of a small programmable quantum computer with atomic qubits
- Quantum Error Correction for Beginners
- Universal digital quantum simulation with trapped ions
- Quantum many-body models with cold atoms coupled to photonic crystals
- Digitized adiabatic quantum computing with a superconducting circuit
- Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
- Scalable Architecture for a Room Temperature Solid-State Quantum Information Processor
- Anderson localization casts clouds over adiabatic quantum optimization
- Simple Glass Models and their Quantum Annealing
- Quantum annealing for the number partitioning problem using a tunable spin glass of ions
- Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
Cited by in corpus (6)
- A Coherent Quantum Annealer with Rydberg Atoms
- Quantum annealing with longitudinal bias fields
- Finding spin-glass ground states using quantum walks
- Predicting quantum advantage by quantum walk with convolutional neural networks
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
- The quantum annealing gap and quench dynamics in the exact cover problem