NIST Authors in **Bold**

Author(s): | Rolando Somma; S. Boixo; Howard Barnum; Emanuel H. Knill; |
---|---|

Title: | Quantum Simulations of Classical Annealing Processes |

Published: | September 26, 2008 |

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 |

Pages: | pp. 130504-1 - 130504-4 |

Keywords: | quantum computing,quantum algorithms, Monte Carlo Markov chains,simulated annealing |

Research Areas: | Math |