# Quantum Bayesian Networks

## November 20, 2008

### Quantum Simulated Annealing

Filed under: Uncategorized — rrtucci @ 5:40 am

In my youngest paper, I proposed a “quantum Metropolis-Hastings algorithm” (MH) that uses a quantum computer to sample probability distributions. (This is useful in AI applications of Bayesian networks, for example). Now I am expanding my horizons by studying simulated annealing. In particular, I am studying the work of Somma, et al, and Wocjan et al. These two researchers and their collaborators have proposed a “quantum simulated annealing algorithm” (SA) that uses a quantum computer to find a local minimum $x_0$ of an “energy” function $E(x)$. They have found that quantum computers can do this quadratically faster than classical computers.

MH and SA are closely related. In both MH and SA, we seek a sample of $x$ points that is distributed according to a probability distribution $\pi(x)$, where $\pi$ is the stationary distribution of a Markov Chain. But in MH, $\pi$ is fixed: it does not change with each iteration. In SA, on the other hand, $\pi$ is a moving target: it becomes spikier and spikier with each iteration, peaking at those points which are minima of $E(x)$.

This excellent website describes various optimization algorithms. In particular, it has a page with an applet that uses SA to solve an instance of the traveling salesman problem with 15 cities.

SA must have been invented by a group of Shakers 🙂 . So simple and beautiful, and yet so useful.