Quantum Bayesian Networks

April 30, 2009

MRI for Quantum Computerists

Filed under: Uncategorized — rrtucci @ 4:41 am

Recently, the press has been reporting on how NIST researchers used the NMR (a.k.a. MRI) technique of Spin Echo to decrease the decoherence rate of an array of hundreds of ultracold beryllium ions.

If you are interested in the physics of quantum computer hardware, and are a beginner in this area, I recommend that you familiarize yourself with the rudiments of NMR – stuff like T_1, T_2, T_2^* and T_{echo} time constants. These are nicely explained, for example, in Wikipedia, the fountain of all Knowledge, under Relaxation_(NMR). Check out also this link, which leads to Chapter 2 of a book entitled “All you really need to know About MRI Physics”. The full book is sold at the delightful website of “Simply Physics – the home of MRI Physics put simply”.

April 25, 2009

I, Grammaticus, speak about simulation

Filed under: Uncategorized — rrtucci @ 6:29 am


(Grammaticus=the Grammarian)

From time to time, I, Grammaticus, Caesar of the vast Roman Empire, will compare the way base humans say something to the way divine Caesar does. In a previous blog post, Grammaticus compared the Quayle (HUMAN) convention to the Dirac (DIVINE) convention for quantum circuit diagrams. In this blog post, Grammaticus addresses the use of the word simulation.

Definitions from The American Heritage Dictionary. Use of boldface is by Grammaticus.

tr.v. sim·u·lat·ed, sim·u·lat·ing, sim·u·lates
a. To have or take on the appearance, form, or sound of; imitate.
b. To make in imitation of or as a substitute for. See Synonyms at imitate.
2. To make a pretense of; feign: simulate interest.
3. To create a representation or model of (a physical system or particular situation, for example).

tr.v. com·piled, com·pil·ing, com·piles
1. To gather into a single book.
2. To put together or compose from materials gathered from several sources: compile an encyclopedia.
3. (Computer Science) To translate (a program) into machine language.

How a base human speaks How Divine Grammaticus speaks
This is a simulation of the weather or of zero gravity. Same, if what is meant is that an imitation (like a computer model) of the physical process is given.
We simulated the Hamiltonian H.
We simulated a unitary matrix U=e^{-itH}.

(Examples of this base usage here and here.)

Use this

We compiled the Hamiltonian H or the unitary matrix U=e^{-itH}, either exactly or approximately.

if what is meant is that the matrix H (or the matrix U) was expressed or decomposed, either approximately or exactly, into a sequence of elementary operators (SEO) which equals H (or U). Elementary operators are usually one or two qubit operators. A SEO is the machine language of quantum computers, so Grammaticus is here following standard usage by American Heritage and other muses, whereas base humans are redefining and defiling the language.

Note that in the vile human usage, the word “simulation” corresponds most closely to “approximate compilation”. Thus, there is no word for “exact compilation” in the vile, limited language of mortals, unless you want to say “exact simulation”, which sounds like an ugly oxymoron to all nine muses.

Thalia, the muse of comedy, points out that “The quantum GNU simulator” sounds like a nefarious “The Matrix” program, whereas “The quantum GNU compiler” sounds more familiar and thus less scary.

April 23, 2009

Oracle and Sun Corporations – Archaic Technology

Filed under: Uncategorized — rrtucci @ 5:43 pm

On April, 2009, the press announced that Oracle will acquire Sun for a gazillion dollars.

For the purposes of this blog, these two giant corporations are like distant, isolated lands untouched by modern civilization. They partake not in the modern necessities of life like indoor plumbing, electrification, vaccination, and Bayesian Network software. Querying their official websites for “bayesian”, I did not find any hint of ongoing projects or software offerings remotely related to Bayesian Networks. Let us hope that the new merger will join the civilized nations. Oracle could follow the example of Autonomy, Microsoft, or Google (see previous posts). Since Oracle is very keen on Java, how about a Java framework analogous to Infer.NET ? Hiring people from Winbugs would greatly accelerate such a project.

Bayesian Networks at Microsoft, Part 2

Filed under: Uncategorized — rrtucci @ 12:20 am

Microsoft Research has recently (on Dec 2008) released the first public version of Infer.NET, a .NET framework for doing inference using Bayesian Networks. A nice FAQ here. Very promising!

April 17, 2009

Brief Introduction to Quantum Compilers

Filed under: Uncategorized — rrtucci @ 8:46 am

Qubiter Logo

Qubiter Logo

A general purpose quantum compiler is a computer program (for a conventional classical computer) that takes an arbitrary unitary matrix U as input and returns a decomposition of U; more specifically, it expresses U as a SEO (Sequence of Elementary Operations). The basic set of elementary operations is arbitrary, but it usually consists of single-qubit rotations and CNOTs. A SEO is the machine language of quantum computers. It’s what they understand. By an arbitrary unitary matrix we mean a unitary matrix that doesn’t have any structure which is known a priori to the compiler’s user. A special purpose quantum compiler is a computer program that decomposes an input unitary matrix U with known a priori structure into a SEO. For example, it might decompose a matrix U known a priori to be a Discrete Fourier Transform matrix into its Coppersmith SEO.

Back in 1998, when I was 10 years younger (how time flies), I published at ArXiv a paper that describes a method for doing exact, general quantum compiling using, in a recursive manner, something called in Linear Algebra the CS decomposition (CSD). See Appendix A. It appears nobody had thought of using recursive CSD to do quantum compiling before. At the same time, I also posted publicly at my website the C++ source code for a program called Qubiter that implements this recursive CSD method. So far, Qubiter is the only general purpose quantum compiler listed at quantiki.

More recently, I’ve also posted the Java source code for a special purpose quantum compiler called QuanSuite.

Why are quantum compilers useful?

  • One good reason to build quantum compilers is simply to obtain a numerical SEO for a pesky unitary. Note that to express exactly an arbitrary unitary matrix of size 2^{N_B}\times 2^{N_B}, we need a sequence of at least {\cal O}(2^{N_B}\times 2^{N_B}) elementary operation. Hence, for N_B larger than about 5, it becomes impractical to compile arbitrary matrices exactly. However, if we can enhance a quantum compiler so that it can do approximate compilations, then the range of doable matrix sizes might be extended considerably. What kind of approximations are useful in quantum compiling? For example, one can use Trotter Rescaling and the Suzuki approximant. See Appendix B. Software implementations of the Trotter and Suzuki methods can be found in the Java class library for QuanSuite. This excellent recent paper by Jordan and Wocjan reviews much of the existing literature about the complexity, as a function of error and number of qubits, of approximate compilations of sparse unitary matrices. Note that some approximations assume that the unitary matrix being compiled is not totally arbitrary, that it has some structure, such as that it is sparse or it is generated by exponentiating a Hamiltonian that connects no more than a fixed number of qubits.
  • Another good reason to study quantum compilers is that they help us understand the nature of those special input unitaries U which lead to efficient SEOs (i.e., SEOs whose length or number of elementary operations is polynomial(N_B)). For example, this and this paper show that the Coppersmith SEO for a Discrete Fourier Transform matrix can be viewed as a special case of the recursive CSD method used by Qubiter. Thus, a Qubiter user unaware of the Coppersmith SEO can independently re-discover it using Qubiter.

Technical Appendices (in pdf):

  • Appendix A. What is the CS decomposition and how does one use it to do quantum compiling?
  • Appendix B. Brief Introduction to Trotter Rescaling, and to the Lie and Suzuki Approximants

April 12, 2009

Work at Google

Filed under: Uncategorized — rrtucci @ 12:36 pm

Google Research has its official website here. Upon querying the website’s search engine with the keyword “bayesian”, I was pleasantly surprised to find among the hits, one page entitled “Work at Google”. This come-work-for-us page contains the following paragraph:

We’re exploring large-scale machine learning as a means of improving search quality. Our spelling correction system is one excellent example (spehl korector? phonitick spewling? who needs a dictniary?). People searching for Britney Spears have clearly found it useful on many occasions. In more recent work, we have been working on algorithms and techniques to construct very large scale Bayesian network models to help understand the relationships between words.

Cool! Of all the hundreds of projects that Google works on, someone at Google thinks that this particular project (among a few others) is cool enough to mention in their come-work-for-us page. I thoroughly agree! Now what would it take to convince Google to start a small research group that did research on quantum computation, from a quantum bayesian network perspective? We can only dream.


April 8, 2009

How NOT to build an American Quantum Computer Industry

Filed under: Uncategorized — rrtucci @ 7:05 am

John Marburger John Holdren, director of the Office of Science and Technology Policy, has called for a “workshop” that may well determine the direction of quantum computing R&D in the US for the next decade. His agency has published a very slick sales brochure, signed by Holdren’s predecessor, John Marburger, that describes various unanswered issues in Quantum Information Science, and promises a bold new American initiative to answer them.

At first glance, this might seem like promising news. However, there are some disheartening red flags. The buck must stop at Holdren, since his agency is financing this workshop.


The general public has been notified about the conference on April 7, only 16 days before the April 23-25 event. With so many confirmed speakers (about 2 dozen), it’s clear that the planners of this conference have known about it long before April 7. It appears that Holdren is no great believer in the democratic process, and that he is using this technique of late announcement to dissuade the general public from attending, except for a token few of the great unwashed.


From (1), it appears that the workshop is mainly for insiders, for the old boys network of tenured “experts”, to advise on government policy. If so, then why so many technical talks? Are experts coming together in this workshop to advise on government policy,  or to learn additional esoteric details about quantum information theory? I mean, should the experts in this workshop be focusing on the microscopic details of the trees, when their main goal is to see through the forest? Personally, I think the only expert that should be speaking at this workshop is Mr. Open Discussion. An adjunct, secondary poster session would have been okay too, but why the hilariously long, dog and pony show?


The list of speakers includes no business interests. No entrepreneurs, no investors, no CEOs , no real business people, no software developers (of either closed or open software). How does Holdren expect to foster a new industry if he excludes business interests from day one? Is he planning to invent a new kind of computer that doesn’t use software? Sure, there are a few invited speakers from IBM and Microsoft, but they are all quasi-academics, many are partially funded by the government, none is trying to sell a product or court investment. One or two of the speakers have even written a small amount of quantum computer software, but none of their software is public that I know of.

The outcome of Holdren’s workshop appears to be a foregone conclusion, so why have a workshop at all? Holdren will continue to fund the same old tenured academics and their silly institutes. These old fashioned institutes will continue to produce an endless stream of post-docs. Most of these post-docs will have to leave the field because Holdren’s “initiative” has failed to foster the industry that could employ them.

To learn more about how to build a computer that uses no software, see this.

This workshop has been announced also at

Quantum Moxie,

Shtetl Optimized,

Quantum Pontiff

April 3, 2009

I hack, therefore I am

Filed under: Uncategorized — rrtucci @ 5:00 pm

Suzanne Gildert — a female MacGyver, the next Q in James Bond movies, Walter Mitty in the operating room — alerts us to the existence of hackerspaces, via her very inspiring blog, Physics and Cake. Being a P.G. Wodehouse fan, a hackerspace sounds to me like a Drones Club or a Junior Ganymede Club for nerds like me. Awesome.

Your local ham radio club is another cool, non-academic club for socializing and collaborating with others that share your passion for technology.

Lastly, I would be remiss if I didn’t mention my all time favorite science (non-fiction) TV series, “The Secret Life of Machines”…pure hacker bliss.

Alas, in quantum computation, hardware hacking is too expensive (it requires facilities and equipment that costs millions of dollars). Software hacking is quite feasible, but, for some sociological reason that eludes me, it has failed to catch on in earnest.

April 1, 2009

WALL-E and quantum computer programming

Filed under: Uncategorized — rrtucci @ 10:19 am

wall-eI recently saw the movie WALL-E and fell in love with it. The animation was brilliant; the plot and dialogue were excellent too. That is not a misprint: I found the dialogue (and accompanying pantomime) excellent too. My favorite lines are when WALL-E introduces himself to MO:

(WALL-E, while shaking hands with MO) WALL-E.
(MO) MO.
(MO) MO!

Okay, not exactly dazzling Shakespearean wordplay, but it fully and very humorously fills a whole scene using only 5 syllables.

No, I won’t claim that Wall-E, (nor EVE nor Auto) are quantum computers. But I would like to re-iterate my previous point about the lessons that Pixar offers for quantum computer programming.

Blog at WordPress.com.

%d bloggers like this: