Source-linked AI summary
Quantum Simulations of Classical Annealing Processes
R. D. Somma, S. Boixo, H. Barnum, E. Knill
TL;DR
Combinatorial optimization can be difficult because exponentially large search spaces and small Markov-chain gaps make classical simulated annealing costly. The paper constructs quantum simulated annealing from quantum walks and quantum-Zeno-induced randomization, obtaining a quadratic improvement in dependence on the minimum spectral gap.
Problem
Classical simulated annealing can require costly mixing when the minimum spectral gap δ is exponentially small, motivating methods with better scaling in δ.
Method
The paper transforms MCMC-based simulated annealing into quantum simulated annealing using quantized reversible Markov chains, quantum walks, and phase-estimation or randomized evolution to induce the quantum Zeno effect.
Results
QSA uses O((EM/γ)^2 log^2(d/ε) log(d/(εδ))) transition-rule applications, yielding a quadratic improvement in the dependence on δ^-1 over classical simulated annealing.
Takeaways & Limitations
The quantum procedure can simulate classical annealing with improved spectral-gap scaling, especially for hard instances where δ ≪ 1.
Takeaways & Limitations
The method assumes efficient classical sampling and efficient quantum implementation of the Markov-chain transition transformation.
Abstract
from arXiv · showhide
We describe a quantum algorithm that solves combinatorial optimization problems by quantum simulation of a classical simulated annealing process. Our algorithm exploits quantum walks and the quantum Zeno effect induced by evolution randomization. It requires order $1/\sqrtδ$ steps to find an optimal solution with bounded error probability, where $δ$ is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order $1/δ$ steps required by the latter.