Quantum Bayesian Networks

February 27, 2010

Quibbs, a Killer-App for Quantum Computers

Filed under: Uncategorized — rrtucci @ 6:00 am

If you are familiar with the famous computer program WinBUGS, imagine running WinBUGS on a quantum computer. A QC can run WinBUGS (or, more precisely, a program with similar inputs and outputs as WinBUGS) quadratically faster than a classical computer. That’s what the computer program that I am currently writing, called “Quibbs”, will allow you to do. The word “Quibbs” is a contraction of the words “Quantum” and “Gibbs”.

My last 3 papers

describe in full detail the algorithm that will be used by Quibbs. The algorithm uses a combination of techniques, including Grover’s algorithm, quantum multiplexors, Szegedy operators, and quantum phase estimation.

Given a probability distribution (i.e., a classical Bayesian network) as input, Quibbs will generate a quantum circuit diagram (i.e., a sequence of one and two-qubit operations) that can be used to sample the probability distribution. Hence, borrowing the terminology of this taxonomy of quantum computing software, Quibbs will be a quantum “code generator”. I’ve previously written a quantum code generator called QuSann. In fact, Quibbs will share a Java class library with QuSann.

Quibbs will be a truly commercially-viable application of QCs, unlike that other less well known algorithm due to Shor. Shor’s algorithm, the greatest QC algorithm that will never be used. I say that because by the time QCs are built, the world will have already switched from RSA to a post-quantum cryptography, a type of classical cryptography that cannot be broken by any QC algorithm, including Shor’s. Okay, maybe saying that Shor’s algorithm will never be used is an ever-so-slight exaggeration. Shor’s algorithm will probably be used for calibration and benchmarking purposes, but certainly not for most commercial, scientific or engineering QC applications.

In the past, I’ve written many blogposts about why an application like Quibbs will be useful:

I’ve also written blogposts about



  1. You’ve probably discussed this already somewhere on your blog, (and seeing as you are much more familiar with it than I am please feel free to point me to any useful posts), but are there any Quantum Bayesian Algorithms which could be run (or would even work better) on an Adiabatic QC rather than a gate model QC? Having moved away from gate model more towards AQC I tend to think more in this hardware model now.

    You’ve got my attention with the Bayesian stuff, I’d like to try to find ways to implement it 😉

    Comment by physicsandcake — February 27, 2010 @ 6:14 pm

  2. Suzanne: What D-Wave/Google have done is sort of Bayesian flavored. I don’t know how to sample an arbitrary probability distribution using an AQC. I hope someone will someday figure out a really good algorithm for translating any gate-circuit algorithm into an AQC algorithm. There have been some exciting developments in that direction already, but I haven’t studied them, so I don’t have any opinions about how good they are.

    Comment by rrtucci — February 27, 2010 @ 7:27 pm

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: