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:

  1. Som07
  2. Som08
  3. Woc08

Blog at WordPress.com.