**Universal quantum simulation for fun & profit**

By making certain classically intractable computational problems easy-to-solve with quantum algorithms, quantum computers offer long-term disruptive capability. In the near term, the original motivation of quantum computers being efficient universal simulators of quantum dynamics is even more exciting. Quantum simulators are especially important to physicists as a potentially efficient means to discover otherwise hard-to-evaluate properties of Hamiltonian systems. Furthermore just dozens of qubits and hundreds of quantum gates on a quantum Turing machine are required to exceed the processing capability of current and foreseeable classical computers, which makes useful quantum simulators feasible in the foreseeable future. “Digital” quantum simulators are a hot topic now, and the first prototype has been realized experimentally. The term “digital” is employed to separate a circuit-based quantum simulation from an experiment specifically designed to behave according to a given Hamiltonian, which is known as “analogue” quantum computation. Scalable “digital” quantum simulation would require strategies such as quantum error correction, but, for now, the experimental challenge is to realize quantum simulation even without scalability hence without the onerous quantum error correction overhead.
Practical universal quantum simulators will be valuable for studying spectral properties or ground states of Hamiltonians and perhaps in relativistic quantum ﬁeld theory to determine particle scattering. The quantum simulator is also applicable to studying open-system dynamics. Moreover, the quantum simulator has applications beyond modelling physical systems, for example simulating quantum-walk dynamics or solving otherwise-intractable problems concerning giant sets of linear coupled equations. Quantum algorithms for Hamiltonian-generated evolution are directly employed in the linear-equations problem to solve certain functions of its solutions exponentially faster than known classical algorithms.
I present an historical account of quantum simulator research since Feynman’s proposal of a universal quantum simulator and Deutsch’s quantum Turing machine for implementing quantum computation. Then we delve into the essence of quantum algorithms for realizing universal quantum simulation based on Lie-Trotter-Suzuki expansions and the assumption of sparse Hamiltonians. Simulations of n-qubit k-local Hamiltonians are amenable to highly efficient quantum-circuit constructions. Time-dependent Hamiltonian evolution poses special challenges but also great benefits such as adiabatic state generation. Finally we will explore experimental developments in realizing quantum simulation in various systems such as the Rydberg atom simulator and ion trap realization.