**Universal quantum simulators for fun & profit**

By making certain classically intractable compu- tational problems easy to solve with quantum algo- rithms, quantum computers offer the possibility of long-term disruptive capability in problem-solving. However, in the shorter term, the original motivation of quantum computers being efficient universal simula- tors of quantum dynamics is even more exciting [1, 2]. Quantum simulators are especially important to physi- cists as a potentially efficient means to discover oth- erwise hard-to-evaluate properties of Hamiltonian sys- tems. Furthermore just dozens of qubits and dozens of quantum gates on a quantum Turing machine [3] are required to exceed the processing capability of current and foreseeable classical computers, which makes use- ful quantum simulators feasible in the near future [4].
“Digital” quantum simulators [5–7] are a hot topic now, and the first prototype has been realized ex- perimentally [8]. The term “digital” is employed to separate a circuit-based quantum simulation from an experiment specifically designed to emulate a given Hamiltonian, which is known as “analogue” quantum computation [9]. Scalable “digital” quantum simula- tion 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 valu- able for studying spectral properties or ground states of Hamiltonians [10–12] and perhaps in relativistic
[1] R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982). [2] S. Lloyd, Science 273, 1073 (1996). [3] D. Deutsch, Proc. Roy. Soc. Lond. A 400, 97 (1985). [4] I. Buluta and F. Nori, Science 326, 108 (2009).
[5] A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Science 309, 1704 (2005).
[6] H. Weimer, M. Mu ̈ller, I. Lesanovsky, P. Zoller, and H. P. Bu ̈chler, Nat. Phys. 6, 382 (2010).
[7] J. D. Whitfield, J. Biamonte, and A. Aspuru-Guzik, Mol. Phys. 109, 735 (2011).
[8] B. P. Lanyon, C. Hempel, D. Nigg, M. Mu ̈ller, R. Ger- ritsma, F. Z ̈ahringer, P. Schindler, J. T. Barriero, M. Rambach, G. Kirchmair, et al., Science 334, 57 (2011).
[9] L.-M. Duan, E. Demler, and M. Lukin, Phys. Rev. Lett. 91, 090402 (2003).
[10] D. S. Abrams and S. Lloyd, Phys. Rev. Lett. 79, 2586 (1997).
[11] L. Wu, M. S. Byrd, and D. A. Lidar, Phys. Rev. Lett.
quantum field theory to determine particle scatter- ing [13]. The quantum simulator is also applicable to studying open-system dynamics [6]. Moreover, the quantum simulator has applications beyond modeling physical systems, for example simulating quantum- walk dynamics [12, 14] or solving otherwise-intractable problems concerning giant sets of linear coupled equa- tions [15]. Quantum algorithms for Hamiltonian- generated evolution [2, 12, 14, 16] are directly em- ployed in the linear-equations problem to solve cer- tain functions of its solutions exponentially faster than known classical algorithms [15].
I present an historical account of quantum simula- tor research since Feynman’s proposal of a universal quantum simulator [1] and Deutsch’s quantum Turing machine for implementing quantum computation [3]. 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 [12, 14]. Simulations of n-qubit k-local Hamiltonians [17] are amenable to highly ef- ficient quantum-circuit constructions [6, 18]. Time- dependent Hamiltonian evolution poses special chal- lenges but also great benefits such as adiabatic state generation [12, 16, 19]. Finally we will explore experi- mental developments in realizing quantum simulation in various systems such as the Rydberg atom simula- tor [6] and ion trap realization [8].
Financial support:– NSERC, AITF, CIFAR, MI- TACS, PIMS and USARO.