Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Quantum Simulations of Classical Annealing Processes

Published

Author(s)

Rolando Somma, S. Boixo, Howard Barnum, Emanuel Knill

Abstract

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(delta) steps to find an optimal solution with bounded error probability, where delta is the minimum spectral gap of the stochastic matrices used in the classical annealing process. This is a quadratic improvement over the order 1/delta steps required by the latter.
Citation
Physical Review Letters
Volume
101

Keywords

quantum computing, quantum algorithms, Monte Carlo Markov chains, simulated annealing

Citation

Somma, R. , Boixo, S. , Barnum, H. and Knill, E. (2008), Quantum Simulations of Classical Annealing Processes, Physical Review Letters (Accessed February 21, 2024)
Created September 25, 2008, Updated October 12, 2021