# 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!