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 be the number of states of bits. Assume is very large. Let , an Hermitian matrix, be the Hamiltonian of a quantum system that we wish to consider. 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 of a quantum system, calculate its state at time , where .
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.
- Fey82 R.P. Feynman, Int. J. Th. Ph. 21, 467 (1982)
- Llo96 S. Lloyd, Science 273, 1073-8 (1996).
- Wie96 S. Wiesner, arXiv:quant-ph/9603028
- Zal96 C. Zalka, arXiv:quant-ph/9603026
(2)Approximating Eigenvalues of Hermitian Matrix
Problem: Given a state which crudely approximates an eigenstate of , estimate with great accuracy the eigenvalue of the predominant eigenstate of contained in .
Suppose is an exact eigenvector of . To obtain the eigenvalue of , a classical computer would multiply the components of by the first row of . Doing this would give the eigenvalue of times the first component of , but would require performing multiplications. In Kit 95, Kitaev proposed a PE (phase estimation) algorithm that uses a QC to calculate the eigenvalue in only order 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 is close to, but not exactly equal to, an eigenvector of .
(3)Finding Mean Values of Observables and Partition Function of a Quantum System
Problem: If is the density matrix of a quantum system, and is an observable of the system, calculate . Also calculate the partition function , where is a positive real number and the are the eigenvalues of . and are known a priori, but not the eigenvalues .
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!
- Tuc09 R.R. Tucci, arXiv:0912.4402