# Quantum Bayesian Networks

## December 7, 2008

### Simulated Annealing B.Q.C.

Filed under: Uncategorized — rrtucci @ 11:10 am

B.Q.C. = Before Quantum Computers.

This post is about simulated annealing (SA), before the age of quantum computers. Its purpose is merely to quote a cute formula that gives an upper bound to the number $t_f$ of iterations that classical SA needs, in order to find an absolute minimum of an energy function $E(x)$, allowing a certain probability $\epsilon$ of failure. Here is the formula:

 $Eq.(1)\qquad t_f \leq {\cal O}\left( \frac{E_{max} \ln(N_{\underline{x}}/\epsilon^2)}{\gamma\;\delta}\right)$

Eq.(1) is THE BOUNDER TO BEAT  by quantum computers, if they are to do SA faster than classical computers. (a bounder is something that bounds; it’s also a cad or ruffian in British slang).

References Som07, Som08, and Woc08 have already given us several quantum computer algorithms that beat this bounder. Their algorithms give $t_f \leq {\cal O}(1/\sqrt{\delta})$ rather than $t_f \leq {\cal O}(1/\delta)$. This will be significant for tough NP-complete problems where $\delta$ is very small. One of my New Year’s resolutions is to come up with my own version of a quantum algorithm that beats Eq.(1).

In the remainder of this post, I will define the variables used in Eq.(1). A proof of Eq.(1) may be found in Appendix A of Ref. Som07.

Consider the Markov chain that underlies SA.

I will underline symbols that represent random variables. A Markov chain is a Bayesian network $\underline{x_0}\rightarrow\underline{x_1}\rightarrow\underline{x_2} \cdots \rightarrow\underline{x_{t_f}}$, where all the random variables $\underline{x_t}$, where $t=0,1,2,\ldots, t_f$, have the same set $S_{\underline{x}}$ of possible values (a.k.a. states).

Let $N_{\underline{x}}$ be the number of elements in $S_{\underline{x}}$. Let ${\cal M}_t(y|x) = P(\underline{x}_{t}=y|\underline{x}_{t-1}=x)$ be the transition matrix of the Markov chain at time $t$. Let ${\cal M}_t$ have eigenvalues $\lambda^{(1)}_t=1 > \lambda^{(2)}_t\geq \lambda^{(3)}_t\ldots \geq \lambda^{(N_{\underline{x}})}_t\geq 0$. Let $\delta = \min_t (1-\lambda^{(2)}_t)$ be the “Markov chain spectral gap”.

Suppose we have an energy function $E:S_{\underline{x}}\rightarrow [0,\infty)$. Let $E_{max} = max_x E(x)$, $(S_{\underline{x}})_{min E} = \{x: E(x) {\rm\;is\;absolute\;min\;of\;}E\}$. Let
$\gamma = min \{E(x)-E(x_0): x\in S_{\underline{x}}-(S_{\underline{x}})_{min E},x_0\in (S_{\underline{x}})_{min E}\}$ be the “energy gap”.

Let $\epsilon = P(\underline{x_{t_f}}\not \in (S_{\underline{x}})_{min E})$ be the failure probability.

One can show that the “final time” (i.e. total number of links in the chain, total number of SA iterations) is upper bounded by Eq.(1).
References:

Blog at WordPress.com.