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)
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 of an “energy” function . 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 points that is distributed according to a probability distribution , where is the stationary distribution of a Markov Chain. But in MH, is fixed: it does not change with each iteration. In SA, on the other hand, is a moving target: it becomes spikier and spikier with each iteration, peaking at those points which are minima of .
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.
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 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).
A qubit lives in a complex vector space spanned by two vectors
Define the following projection operators:
is called the number operator because for . Note .
The Pauli matrices are defined by:
One also defines .
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 (Pinwheel) Single-qubit rotation and Controlled Not (CNOT)
Fig.2 (Farm Windmill) Multiply Controlled Rotation
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 be the number of bits and the number of states. The operators in Fig.1 are a “universal” set: any matrix in 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.