Academic participants:
Richard Cleve, Raymond Laflamme, Michele Mosca, Ashwin Nayak, Barry Sanders.
Although the simulation of quantum physical systems is a natural and important area of application of quantum algorithms, there are a number of specific problems in this area that have not been well investigated. We consider a specific example from statistical physics, and also address a more general simulation problem.
The Ising model, and its generalization, the Potts model, have been studied widely as models for magnetization in the area of statistical physics. In the Potts model, a solid is assumed to be composed of individual magnetic moments or spins located at the sites of a finite lattice structure. The spins interact only with other spins that are adjacent to them in the lattice.
A central problem in the study of these models is that of estimating the so-called “partition function”, since several properties, such as the mean energy and the mean magnetic moment can be computed from it. Other properties call for sampling spin configurations according to the Gibbs distribution. Polynomial-time quantum and classical algorithms for both computational problems in the Ising model are now known in the special ferromagnetic case. The partition function for an anti-ferromagnet is believed to be computationally intractable (there is no fully polynomial randomized approximation scheme for it unless NP is in BPP).
The Potts model appears to be much harder to analyze. In fact, it is known that computing the ferromagnetic partition function for bipartite planar graphs is #P-hard even for a fixed temperature and interaction energy. In contrast, there is a deterministic polynomial-time algorithm for the Ising partition function for all planar graphs with arbitrary interactions. With the quantum algorithm previously discovered by us as a starting point, we hope to develop algorithms for the Potts ferromagnet as well. These algorithms would be of considerable interest also because of the relationship, via the Tutte polynomial, of the Potts partition function to numerous other combinatorial quantities.
A very general framework for expressing quantum physical simulation problems is that one is given a mechanism for describing the nonzero entries of a d-sparse Hamiltonian acting on n qubits (a 2n °x 2n Hermitian matrix), and a time parameter t, and the goal is to apply e−iHt on a given n-qubit state. A measurement can be associated with the final state to yield a classical output. This can be taken as a very general framework for simulating quantum physical systems by quantum algorithms, which is an algorithmic area of fundamental importance. Also, sparse Hamiltonian simulations can arise in the execution of continuous-time quantum walks. It has been shown that the cost (in terms of gates) of a general sparse Hamiltonian simulation scales polynomially (in several relevant parameters, such as n, d, t). This has been improved —for example, we showed that the dependence on n need not be larger than a factor of log* n. We also have partial progress on several other efficiency improvements.
This project will interact with project QB5 on qubits. D-Wave Systems Inc. will partner with this project to investigate the implications of quantum information for simulation of quantum systems.