Quantum Simulated Annealing
arXiv:0712.1008
Abstract
We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines techniques from quantum walks, quantum phase estimation, and quantum Zeno effect. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. Our implementation scales with the inverse of the square root of the minimum spectral gap of the stochastic matrix used in the classical simulation. The quantum algorithm outperforms the classical one, which scales with the inverse of the gap.
8 pages, 2 figure
Cited by in corpus (10)
- On the impact of quantum computing technology on future developments in high-performance scientific computing
- Speed-up via Quantum Sampling
- Quantum Speed-up for Approximating Partition Functions
- QFold: Quantum Walks and Deep Learning to Solve Protein Folding
- Quantum Computation Beyond the Circuit Model
- Quantum Enhanced Inference in Markov Logic Networks
- Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
- Code Generator for Quantum Simulated Annealing
- Quantum Gibbs Sampling Using Szegedy Operators
- Sensitivity of Quantum Walks with Perturbation