Quantum Bayesian Networks

December 29, 2009

The World Needs Bayesians, and Bayesians Need Quantum Computers

Filed under: Uncategorized — rrtucci @ 10:44 pm

The computer age has given us the ability to rapidly store and access a deluge of large data sets. These large data sets can be milked for information very effectively using the tools of Bayesian statistics. All major corporations that deal with large data sets are becoming increasingly aware of this. In fact, it is likely that the future survival of those corporations will increasingly depend on how Bayesian they are. The following posts describe current Bayesian activity in some major corporations:

So the world already desperately needs the services of Bayesians. And Bayesians will soon realize that they desperately need quantum computers. That’s because Bayesian inference is an NP-hard problem. A very popular and efficient way of doing Bayesian inference for large problems is to use Gibbs sampling of probability distributions (as done, for example, with Winbugs). Gibbs sampling is still NP-hard on a quantum computer, but quantum computers can do Gibbs sampling quadratically faster than classical computers (see this)

December 24, 2009

My Papa’s Recipe for the Ziti

Filed under: Uncategorized — rrtucci @ 3:42 pm

(Ricetta da mio padre per il Ziti)

It was the great Leonardo who first invented partition functions in physics. He call-ed them Ziti functions, in honor of the delicious plate of ziti that he was eating at the time. That is why we use today the letter Z for denoting \sum_r e^{-\beta E_r}.

Check out il arXivi for my new recipe for cooking il Ziti. Molto delizioso. A recipe inspired by my own father’s recipe. Only thing I change-ed was to add the more modern quantum computer -puttanesca/gigoloesca ingredients. My famiglia compared this recipe with the following ziti recipes from other cooks (they think mine is MUCH, MUCH BETTER. That-sa why I love my famiglia).

(uno) Signiori Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe, Daniel Nagaj, “Quantum Speed-up for Approximating Partition Functions” arxiv:0811.0596

(due) Signiori David Poulin, Pawel Wocjan, “Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer” arxiv:0905.2199

(tre) Signiori K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, F. Verstraete, “Quantum Metropolis Sampling” arxiv:0911.3635

December 22, 2009

Set a Thief to Catch a Thief

Filed under: Uncategorized — rrtucci @ 2:54 pm

The title of this post is an old English proverb. An analogous advice for quantum mechanics could be: Set one quantum contraption to understand another.

In previous blog posts, I’ve extolled the virtues of using a quantum computer to sample probability distributions. QCs can do this quadratically faster than classical computers. A second type of task which QCs can often perform much faster than classical computers is calculating how other quantum systems will behave. Next, I will describe this second type of task. As you will see, it turns out that these two types of tasks are related.

For non-scientific persons, studying how quantum systems behave might sound like an esoteric application of little importance to the average person. Not so. Many of the technological inventions of the last 100 years (for example, many modern electronic gadgets and medicines) were predicted or perfected after careful analysis of the behavior of the quantum systems involved in them.

Let N_S=2^{N_B} be the number of states of N_B bits. Assume N_S is very large. Let H, an N_S \times N_S Hermitian matrix, be the Hamiltonian of a quantum system that we wish to consider. H may depend on time. We know that a quantum computer can do the following calculations faster than a classical computer:

(1)Simulating Quantum State Evolution
Problem: Given the initial state |\psi(0)\rangle of a quantum system, calculate its state |\psi(t)\rangle at time t, where i\frac{\partial}{\partial t}|\psi(t)\rangle = H(t)|\psi(t)\rangle.

One of the first uses for a QC ever proposed was given by Feynman in Fey82. Feynman envisioned a “universal quantum simulator” that could “simulate” the evolution of any quantum system exponentially faster than a classical computer. In the ensuing 3 decades, we have learned several nice techniques for implementing Feynman’s original idea. Llo96 suggested expanding the evolution operator of the quantum system as a Trotter product. Later, Wie96 and Zal96 pointed out that: one could set up the Trotter product so that its factors would include both diagonal and non-diagonal matrices, and then a similarity transformation with super efficient Discrete Fourier Transforms could be used to diagonalize the non-diagonal matrices.

(2)Approximating Eigenvalues of Hermitian Matrix H
Problem: Given a state |\psi\rangle which crudely approximates an eigenstate of H, estimate with great accuracy the eigenvalue of the predominant eigenstate of H contained in |\psi\rangle.

Suppose |\psi\rangle is an exact eigenvector of H. To obtain the eigenvalue of |\psi\rangle, a classical computer would multiply the N_S components of |\psi\rangle by the first row of H. Doing this would give the eigenvalue of H times the first component of |\psi\rangle, but would require performing N_S multiplications. In Kit 95, Kitaev proposed a PE (phase estimation) algorithm that uses a QC to calculate the eigenvalue in only order N_B steps. Thus, Kitaev’s algorithm calculates the eigenvalue exponentially faster than a classical computer. In Abr98, Abrams and Lloyd extended Kitaev’s algorithm to the case where |\psi\rangle is close to, but not exactly equal to, an eigenvector of H.

(3)Finding Mean Values of Observables and Partition Function of a Quantum System
Problem: If \rho is the density matrix of a quantum system, and \Omega is an observable of the system, calculate tr(\Omega \rho). Also calculate the partition function Z = \sum_{r=1}^{N_S} \exp(-\beta E_r), where \beta is a positive real number and the E_r are the eigenvalues of H. \beta and H are known a priori, but not the eigenvalues E_r.

In Tuc09, I describe one possible solution to this problem. My solution uses, you guessed it, a QC to sample a probability distribution. QCs are by far the best samplers in the business!

December 18, 2009

Why Quantum Computers—Little Dieter Needs to do Quantum Mechanics

Filed under: Uncategorized — rrtucci @ 10:53 am

In a previous blog post, I answered the question of “Why quantum computers?” by making an analogy between QCs and Galileo’s telescope. Let me take a different tack here.

The documentary film “Little Dieter Needs to Fly” by Werner Herzog, tells the story of an American aviator named “Dieter Dengler” whose aircraft was shot down during the Vietnam war. Dengler was captured by the Viet Cong, and detained in a POW camp, where he endured torture and starvation, until he escaped into the surrounding jungle. He then proceeded to make a long, perilous journey through the thick tropical jungle, a journey that nearly killed him. Miraculously, he was finally spotted and rescued by US helicopters, and lived to tell his tale. The title of the documentary refers to the fact that Dengler can recall the exact day he became obsessed with becoming an aviator. He was a child in Germany during WW II. One thrilling day, forever etched in his memory, an allied aircraft flew extremely close to his observation point, so much so that he was able to see the aviator’s goggles. From that day on, Dieter knew he had to fly.

It seems that quantum mechanics provokes a similar fascination in a large fraction of the human population. For many of us, a brief introduction to q.m. sparks a strong, life long interest in it.

I just came across the following example of the enticing power of q.m. From this excellent interview of Sir Anthony Leggett, we learn that even this 71 year old Nobel prize winner still has a childlike curiosity about some aspects of the foundations of q.m.. We also learn that in the last few years he has become keenly interested in topological quantum computers.

Little Dieter needs QCs because he needs desperately to do quantum mechanics. QCs will allow us to do q.m. like no device ever before. The Large Hadron Collider will certainly allow us to do q.m. too, but much more indirectly, and only on a single tremendously expensive machine. Explaining LHC data will require assuming many ideas beyond q.m. (e.g., gauge field theory, spontaneous symmetry breaking, perhaps even more far fetched ones like super-symmetry, string theory, extra dimensions, etc.). By comparison, very few fundamental physics ideas beyond q.m. are needed to explain QCs. And QCs will probably someday be available in large numbers.

QCs will allow the general public to deepen its currently shallow understanding of q.m., a theory which is the foundation of most of 20th century physics. Just like amateur radio electronics popularized electromagnetism, and personal computers did the same for digital electronics and programming algorithms, QCs will finally make q.m. accessible to the masses. QCs will allow us to extend, refine, and maybe even revise, our current thinking about q.m. This, on top of the fact that QCs will shine as a calculational tool.

Blog at WordPress.com.

%d bloggers like this: