Simulating the Hamiltonian dynamics of a quantum system is one of the most natural applications of a quantum computer. The idea of quantum simulation was initially suggested by Feynman and others in the 1980s, and the first explicit algorithm was designed by Lloyd. Since then, significant attention has been dedicated to developing simulation algorithms that are asymptotically fast with respect to various parameters, as well as identifying new applications of quantum simulation in areas such as mathematics, physics and computer science.

The goal of my thesis is to develop an understanding of quantum simulation algorithms concerning their design, resource estimation and applications. We aim to produce concrete resource estimates for solving practical simulation problems, as well as to design algorithms that perform well in practice. In addition, we apply ideas from quantum simulation to other quantum computing areas, improving existing algorithms and discovering new ones.

A near-term quantum computer is likely to have restrictions on the number of available qubits or the total number of gates that can be reliably applied. To use such a device for quantum simulation, it is important to estimate and optimize the resource requirements. We implement three leading algorithms, employing diverse techniques to tighten error bounds and optimize circuit implementations. We estimate the resource needed for simulating spin systems, a problem that arises in condensed matter physics that is difficult to solve on a classical computer. As for future work, we plan to investigate quantum chemistry simulation, another natural target for near-term quantum simulation that has significant industrial value.

Product formula algorithm is an approach to quantum simulation that is straightforward but not asymptotically optimal. However, our preliminary result on resource estimation shows that this approach has the best empirical performance among all the algorithms we implement. This motives us to close the dramatic gap between the provable and the actual behavior of product formulas. We show that by simply randomizing how the terms in the Hamiltonian are ordered, one can prove stronger bounds on the quality of approximation for product formulas, and thereby give more efficient simulations. As for future work, it would be interesting to design improved product-formula algorithms for specific physical systems, such as lattice systems or systems with long-range interactions.

More broadly speaking, the problem of quantum simulation is one of the many examples where quantum computers could offer speedup. There has been considerable interest in recent years in designing new quantum algorithms, such as algorithms for solving linear equations, quantum walks and quantum machine learning. These algorithms work in different ways, which makes mastering all of them a challenge. We develop an algorithmic paradigm that unifies algorithms from all these disparate fields. Our approach is inspired by a technique from quantum simulation, and is both natural and conceptually simple. We also aim to apply our paradigm, discovering new algorithms that were hitherto unknown.

Dept. rep: Dr. Howard Elman

Members: Dr. Xiaodi Wu