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.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: