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

- “An Adaptive, Fixed-Point Version of Grover’s Algorithm”

by Robert R. Tucci, arXiv:1001.5200 (See also My Secret Life as a Captain of the Grover’s Algorithm) - “Use of Quantum Sampling to Calculate Mean Values of Observables and Partition Function of a Quantum System”

by Robert R. Tucci, arXiv:0912.4402 (See also My Papa’s Recipe for the Ziti) - “Quantum Gibbs Sampling Using Szegedy Operators”,

by Robert R. Tucci, arXiv:0910.1647

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:

- The World Needs Bayesians, and Bayesians Need Quantum Computers
- The MCMC Revolution
- Quantum Computerization of MCMC
- Military Uses of Quantum Computers
- Quantum Computing Primer for Spies
- Proposing to Spies
- Likely: Wall Street Firms Will be Early Adopters of Quantum Computers
- Experimental Physics Informatics and Quantum Computing
- Bioinformatics and Quantum Computing

I’ve also written blogposts about

- Grover’s algorithm:

Grover’s Algorithm for Dummies - Quantum multiplexors:

Qubit Mixers - Szegedy operators:

Szegedy Ops - Quantum phase estimation:

Set a Thief to Catch a Thief

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

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