Quantum Bayesian Networks

May 24, 2009

Software For Bayesian Networks

Filed under: Uncategorized — rrtucci @ 3:05 am

If you are interested in software for Bayesian nets, I enthusiastically recommend that you read K. Murphy’s excellent 3 page review article entitled “Software for Graphical Models – A Review” (ISBA Bulletin, Dec 2007).

By the way, the website of Prof. K. Murphy (Uni. of British Columbia) is also well worth a visit. I found the class notes for his courses on B nets and related topics very clear and helpful. Prof. Murphy is the author of a popular B net software package (in MatLab/C) called Bayes Net Toolbox (BNT). For many years, he has kept an authoritative table comparing various B net computer programs.

May 17, 2009

WolframAlpha + Bayesian Networks = ?

Filed under: Uncategorized — rrtucci @ 6:11 am

WolframAlpha is a beautiful, amazing computer program. As with any truly novel idea, on first encountering it, one struggles to put it into context. Here is how I view it, from a Bayesian Networks perspective.

Quote from the WolframAlpha website:
What is the core technology of WolframAlpha?

There are many parts to it, each with significant innovations. Four key general areas are the data curation pipeline, the algorithmic computation system, the linguistic processing system, and the automated presentation system.

I view the current WoframAlpha as an intermediate step towards full AI. To answer my own question in the title, I would say

WolframAlpha + Bayesian Networks = Hal 100 (not yet 9000) possible in five years

AI task WolframAlpha equivalent task limitations of current WolframAlpha
remember facts data curation pipeline Can’t add, alone, by itself, data (for instance, data acquired from internet) to curated data. In this sense, it’s ability to remember what it hears is very limited.
analyze algorithmic computation system Uses a deterministic, rule-based analyzer. If it also used bayesian networks and statistics, it could analyze cases, common in real life, in which some of the input data is missing or contradictory.
hear linguistic processing system Can’t hear except from command line.
speak automated presentation system Limited ability to say things in meaningful prose.
learn models not yet Can’t learn new models of nature from its own analyses. Bayesian network learning could help here.

May 12, 2009

QC Paulinesia

Filed under: Uncategorized — rrtucci @ 5:37 am
Picture yourself strolling down this beach

Picture yourself strolling down this Polynesian beach

Tensors are like multi-legged creatures. A leg (index) of one creature (tensor) can be connected (contracted, summed over) with the leg of another creature. Tensor networks consisting of many interconnected creatures are very common in Physics. For example:

‘t Hooft and Veltman used tensor networks to explain some aspects of quantum field theory (Ward-Takahashi identities, renormalization, etc) in their famous 1973 paper entitled “Diagrammar”.

Predrag Cvitanovic used tensor networks (he calls them birdtracks) to explain both, quantum field theory in this “webBook”, and group representation theory in this webBook.

Sir Roger Penrose used tensor networks to do general relativity calculations. See here

Quantum circuit diagrams are tensor networks too. In my 2004 paper, “QC Paulinesia”, I tried to compile all the tensor network (circuit diagram) identities I had encountered while learning about quantum computing. Sort of like a table of integrals for quantum computerists. These identities almost always entail Pauli matrices, and I was reading a travel book about the Polynesian islands at the time, hence the title. (My original plan was to publish periodic updates of QC Paulinesia, with corrections and additions. I haven’t done a single update yet though, because, because…okay, because I’m damn lazy.)

May 8, 2009

The QIS Workshop

Filed under: Uncategorized — rrtucci @ 2:40 am

Prof. Scott Aaronson (MIT) has just written a blog post about his experiences at the Quantum Information Science (QIS) Workshop (April 23-26 Vienna VA, 2009). (QIS research includes quantum computer research.) This is my comment about his blog post. (I also wrote an earlier blog post about the politics behind the QIS workshop.)

In 2002, a team of researchers published this paper:

Chi02: Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman, “Exponential algorithmic speedup by quantum walk”. Abstract here

Chi02 uses a vector space V spanned by a set of orthogonal states, one state for each node of the following graph.

Fig.1- Chi02 graph

Fig.1- Chi02 graph

Chi02 considers a pure state from V. The state is a traveling wave moving from left to right of the above graph, evolving according to Schrodinger’s equation with a “quantum walk” Hamiltonian (proportional to the adjacency matrix of the graph). Chi02 finds that the quantum walk travels from entrance to exit exponentially faster than the classical random walk. (A sort of quantum tunneling effect)

More recently, Prof. Alán Aspuru-Guzik (Harvard) and Prof. Seth Loyd(MIT) have published this paper with their students:

Moh08:  Masoud Mohseni, Patrick Rebentrost, Seth Lloyd, and Alan Aspuru-Guzik “Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer”. Abstract here

where they claim that a quantum walk (albeit a heavily damped one) can be used to describe photosynthesis. They also claim, without proof, that their model and photosynthesis exhibit the Chi02 effect. Of course, the Moh08 paper doesn’t use its model to predict any observed experimental data.

Aspuru gave a talk about his work at the QIS Workshop. In the words of Scott Aaronson

Fig. 2- Light Harvesting Molecule

Fig. 2- Light Harvesting Molecule

In a talk that was so good, you almost forgot it involved chemistry, Alán Aspuru-Guzik discussed applications of quantum complexity theory to understanding photosynthesis and the design of efficient solar cells (!). …Shown above is a light-harvesting molecule (image snagged from Alán’s slides), which apparently is efficient at concentrating light at its center for essentially the same reason the Childs et al. quantum walk reaches the target vertex exponentially faster than a classical walk:..

And according to Prof. Andrew Landhal (U. of New Mexico)

Just a quick comment on Alán Aspuru-Guzik’s talk, which was indeed fantastic and inspirational…

Well, let’s see. The Chi02 result is for a pure state with quantum coherence over all the nodes of Fig.1. There is no way that you are going to get quantum coherence over the thousands of atoms in Fig.2, for any significant amount of time, when these atoms are sitting inside a stew at room temperature or hotter. The quantum walk MohO8 is considering will degrade in this thermal environment to a classical random walk, so it can’t possibly exhibit Chi02’s purely quantum effect.

I don’t see how a paper that proposes a very speculative model of photosynthesis, makes dubious, amazing and unproven assertions about its connection to complexity theory, and predicts no observed data, can be so inspirational. But maybe I’m totally wrong. (would not be the first time 🙂 ) You be the judge. See Aspuru’s comment (#20) here. Extraordinary claims require extraordinary proof.

May 4, 2009

PageRank – How Google used Statistics to Change the World

Filed under: Uncategorized — rrtucci @ 1:04 am

How I think history books circa 2100 will read:

When widespread adoption of classical computers and the Internet arrived in the late 20th century, human society suddenly became capable of quickly storing, accessing, and analyzing huge data sets. The stage was set for a band of young technologists called Google to harness Probability and Statistics to analyze these huge data sets. PageRank was their algorithm. Simple math, just finding the stationary state of a Markov chain, was key to how Google changed the world.

A second wave of technology followed soon after, and this one towered over the first in importance. Quantum Computer mainframes became available from 2020 onwards. These were harnessed by the visionary  <insert your name here>  to analyze, again huge data sets, again using the tools of Probability and Statistics (such as Bayesian Networks, of which Markov Chains are an example). But this time the data sets came fast and furious, not just from what people wrote and posted on the Internet, but also from AI and biotech and nanotech. Quantum computers could do such analyses much faster than classical computers. Subtle AI finally became possible. Quantum thinkers that could ponder about petabytes of data, and make sense of it in a heartbeat; machines, called johnnies, with IQ’s thousands of times higher than that of Johnny von Neumann, had finally arrived.

Okay, enough geek day dreaming for today. Here are some excellent links explaining Google’s PageRank. It’s clever but simple math (understandable by most undergraduate students in engineering or science).

BigTable and MapReduce are also very interesting Google technologies that go hand in hand with PageRank. Mike Nielsen (co-author of a popular textbook on Quantum Computing) explains those nicely in his  Google Technology Stack

Blog at WordPress.com.

%d bloggers like this: