Quantum Bayesian Networks

November 20, 2008

Books on Bayesian Networks

Filed under: Uncategorized — rrtucci @ 6:36 pm

hammock

Two of the best books for teaching Bayesian networks are

  • Michael Jordan, “Introduction to Graphical Models”, in preparation
  • Daphne Koller and Nir Friedman, “Bayesian Networks and Beyond”, in preparation.

In preparation !@#. For eons now, these books have been “in preparation”. Civilizations have come and gone. Many courses in many universities have used these books in preliminary form as their primary text. Why are these authors so laid back! Do they live in Frank Capra’s Shangrila, where people live thousands of years, and don’t need to hurry much. Hmm, Jordan at Berkeley, Koller at Stanford. California…Shangrila. It seems that, for the time being, these gem books will be available only to surfer dudes, not to us hard working Yankees on the other coast.

Update (Sept 9, 2009)
Wow, 1200 pages! I take back all I said about Californian’s being laid back. Check out

Probabilistic Graphical Models
Principles and Techniques

Daphne Koller and Nir Friedman
(Aug 2009, MIT Press)

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.

November 13, 2008

Books on Quantum Bayesian Networks

Filed under: Uncategorized — rrtucci @ 4:23 pm

secret-garden Nope. None. Not yet. The field is a secret garden at present. A secret garden, having one is great solace from those aspects of life that make us inconsolably sad. For many years now, quantum bayesian networks has been one of my secret gardens. Which reminds me of the novel, “The Secret Garden”, by Frances Hodgson Burnett. Great book, very memorable plot. Usually considered children’s literature, like Treasure Island and the like, but still a fun read for an adult, even better if the adult is reading it to his/her children. The 1993 movie is very good too.

My new paper: sampling + quantum computers

Filed under: Uncategorized — rrtucci @ 12:30 am

My youngest paper, just published today at ArXiv, is entitled:

“Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network”

The paper (41 pages) is just as wordy as its title. I could have written a much leaner paper (claims he), but I opted to include lots of introductory material, to make life easier for newcomers to my secret garden.

My target audience are two clans of people, quantum computerists and Bayesian network users. These two clans have never talked to each other until now, no doubt because they have never been properly introduced. My hope is that I, like Mr. Robinson, can get them to talk to each other, for a while at least (at least until they find out about my unsavory character.) I am referring here to the Mr. Robinson in the humorous poem “Etiquette” by W.S. Gilbert (yes, the Gilbert of the Gilbert & Sullivan operettas).

November 2, 2008

Qubit Mixers

Filed under: Uncategorized — rrtucci @ 3:04 pm
Tags:

A qubit lives in a complex vector space spanned by two vectors

|0\rangle= \left[\begin{array}{c}1\\ 0 \end{array}\right]\;\;,\;\;|1\rangle = \left[\begin{array}{c}0\\ 1\end{array}\right]\;.

Define the following projection operators:

\overline{n} = P_0 = |0\rangle\langle 0|=\left[\begin{array}{c}1\;\;0\\ 0\;\;0\end{array}\right]\;\;,\;\;  n = P_1 = |1\rangle\langle 1| =\left[\begin{array}{c}0\;\;0\\ 0\;\;1\end{array}\right]\;.

n is called the number operator because n|b\rangle = b|b\rangle for b \in \{0,1\}. Note \overline{n} =  1 -n.

The Pauli matrices are defined by:
\sigma_X = \left[\begin{array}{c}0\;\;1\\1\;\;0\end{array}\right]\;\;,\;\;\sigma_Y =\left[\begin{array}{c}0\;-i\\i\;\;0\end{array}\right]\;\;,\;\;\sigma_Z = \left[\begin{array}{c}1\;\;0\\ 0\;-1\end{array}\right]\;.
One also defines \vec{\sigma} = (\sigma_X,\sigma_Y,\sigma_Z).

The lingua franca for expressing a sequence of quantum computer commands are quantum circuits with circuit elements of some basic types. Here are some circuit elements in order of increasing complexity: (in these figures, 0,1,2 are qubit labels)

Fig.1 Single-qubit rotation and CNOT

Fig.1 (Pinwheel) Single-qubit rotation and Controlled Not (CNOT)

Fig.2 (Farm Windmill) Multiply Controlled Rotation

Fig.2 (Farm Windmill) Multiply Controlled Rotation

Fig.3 (Windfarm) Multiplexor

Fig.3 (Windfarm) Multiplexor

The pinwheel, farm windmill and wind farm are my poetic analogues.
One can generalize the operators of Figs.2 and 3 to have more controls (the dark dots in Fig.2 and the half-moon nodes of Fig.3) and more complicated targets (the square nodes in Figs.2 and 3).

Let N_B be the number of bits and N_S= 2^{N_B} the number of states. The operators in Fig.1 are a “universal” set: any matrix in SU(N_S) can be constructed in terms of them. The operators in Figs. 2 and 3 can be expressed in terms of those in Fig.1.

The operators in Figs. 1 and 2 appear frequently in the quantum computing literature. The multiplexor operator of Fig.3 is much less common. Only I and a few other workers have used it in their papers. Multiplexors have some very useful properties. I’ve used them in the theory behind my quantum compiler, Qubiter ( a quantum compiler decomposes an input unitary matrix into a sequence of elementary operations (SEO), elementary operations such as single qubit rotations and CNOTs.) My next paper uses multiplexors heavily. As soon as the paper is in ArXiv, I will update this post with a link to it.

Update: The paper is now available here. It contains a whole section introducing multiplexors.

Create a free website or blog at WordPress.com.

%d bloggers like this: