Quantum Bayesian Networks

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!

Leave a Comment »

No comments yet.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: