Quantum Bayesian Networks

February 28, 2009

Bayesian Networks at Microsoft

Filed under: Uncategorized — rrtucci @ 10:16 pm

autoreceptionMicrosoft’s Eric Horvitz and his group at Microsoft Research are frequent users and big fans of Bayesian Networks. A famous example of their Bayesian inferencing software is their virtual receptionist:

From “Todd Bishop’s Microsoft Blog”:

Highlights: Microsoft TechFest
By Todd Bishop on February 25, 2009 at 9:41 PST

Once every year, researchers from Microsoft’s labs around the world gather in Redmond to show their latest projects. The event, TechFest, is a glimpse into the minds of the people responsible for pushing the bounds of technology inside the company. In some cases, it can also serve as a preview of future Microsoft products and features.

About 40 projects were on display for the media yesterday, out of more than 100 total this year, so we didn’t get to see everything. There could be some more jaw-dropping stuff for employees behind closed doors. But out of the projects we saw, these were some of the highlights.

Automated Receptionist: Also known as “Situated Interaction” this project from researcher Dan Bohus explores the ways humans and machines can interact. A lifelike on-screen avatar can help complete basic tasks, such as scheduling a shuttle.

The receptionist (pictured above) shifts her gaze when speaking with different people in a group, and tries to determine whether people are Microsoft employees or visitors depending on what they’re wearing (more formal attire usually means a guest, casual means a worker).

The project has been shown publicly in the past, but new capabilities this year include the ability to host a trivia game. If one person keeps getting stumped, the avatar turns and suggests another person help.

Microsoft Research’s Eric Horvitz says one possible future application would be next-generation elevators that could hold the door open when people are approaching, and tell them when they missed their floor.

More here

February 22, 2009

An Elevator Pitch For Quantum Bayesian Networks

Filed under: Uncategorized — rrtucci @ 1:21 pm

salesmanIf you look at the history of computer science (those who ignore history are condemned to repeat its mistakes), you will find that the representation of classical uncertainty in computer programming went through a lot of false starts, but has finally settled into the use of Bayesian networks. Researchers tried to extend rule based systems, functional languages like Lisp, declarative languages like Prolog, etc. to include probabilities, and always ended up with an ugly kludge. Bayesian networks has emerged as the clear winner for representing classical probabilities and uncertainty in computer programs. If you don’t believe me, ask any programmer at Google, or Microsoft (both companies use Bayesian networks extensively), or any person in AI or bio-informatics, or a Bayesian Statistician, etc. Quantum Physics and Probability Theory have much in common. Frequently, they are parallel theories. It would be inexplicably odd if Bayesian networks were not as important to quantum computer programing as they are to classical computer programming. That is why I wrote my Mac application “Quantum Fog” which generalizes Bayesian Networks to quantum mechanics in a minimal way. Bayesian networks have already been successful in illuminating quantum mechanics: for example, they led me to invent squashed entanglement, a new measure of quantum entanglement.

Enlightened Bio-Informatics Curriculum Teaches Bayesian Networks at an Early Stage

Filed under: Uncategorized — rrtucci @ 1:01 pm

Baby’s first Bayesian Network, P(cuteness)=1

February 21, 2009

Classical Reversible Computing and Quantum Computer Programming

Filed under: Uncategorized — rrtucci @ 8:14 am

Historically, discoveries in classical reversible computing (CRC) provided a strong inspiration for later discoveries in quantum computing. But the importance of CRC for quantum computing is much more than historical. Many results and software from CRC can still be used almost out of the box in quantum computer programming. For example, many quantum computing algorithms query an oracle one or more times.  (See my previous blog post for an introduction to quantum oracles.) Finding a quantum circuit for such oracles is essentially a problem in CRC programming. Indeed, these deterministic circuits can be expressed solely in terms of CNOTs and Toffoli gates (i.e., 2 and 3 body deterministic interactions)

For example, consider Monte Carlo integration, an application which is extremely useful in many areas of science and engineering. Quantum computers can do Monte Carlo integration quadratically faster than classical computers. Woo hoo! (This assumes that we know a polynomial complexity algorithm for calculating the function being integrated. For an excellent introduction to quantum Monte Carlo integration, see this paper by Abrams and Williams). Quantum algorithms for Monte Carlo integration use an oracle that loads the function being integrated. Writing a circuit for such an oracle will often require reversible circuits for doing the basic panoply of imperative language operations (arithmetic operations, trigonometric and exponential functions, do-loops and conditionals). CRC software that writes such circuits already exists(?)

CRC Researchers:

(1)Michael P. Frank
has been in the forefront of CRC for more than a decade. He got his Ph.D. from MIT in 1999, in the field of CRC. I especially like the fact that he does both theory and programming. With his student DoRon B. Motter (now at Microsoft?), he wrote a reversible Shroedinger equation simulator in Java (Can’t find a link to it). More recently, he and his collaborators at FSU have written a space-efficient simulator of quantum computers in C++. I found the following talk, an overview of some of his work, very interesting: “Quantum Computer Architectures for Physical Simulations,” invited talk presented by Frank at the Quantum Computation for Physical Modeling workshop sponsored by the Air Force research labs, held at Martha’s Vineyard, Wed., May 8, 2002.  PowerPoint  slides  here

February 9, 2009

Almost All Quantum Oracles Are Impossible to Realize in Practice

Filed under: Uncategorized — rrtucci @ 10:41 pm

In this blog post, I tackle my perplexity at what seems to be a common practice of using quantum oracles without worrying about their time-complexity.

Am I the only quantum computer programmer worried about this? Is there some important point that I’m missing?

This being a blog post, I’ve tried to be as introductory and pedagogical as possible. Since I wanted to use Latex intensively, I’ve put the core of this post in this pdf document. (Feb 14, 2009: Inspired by the excellent blog comments below by Scott Aaronson, I have updated the core pdf to version 2)

Blog at WordPress.com.

%d bloggers like this: