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).

  1. Som07
  2. Som08
  3. Woc08

Blog at WordPress.com.

%d bloggers like this: