Universal Quantum Simulation for Fun & Profit

Since 1982, when Feynman first proposed simulating Hamiltonian dynamics on a quantum computer as a way around intractability on classical computers, the subject has rapidly advanced both theoretically and experimentally. Compared to other quantum algorithms, quantum simulations could deliver interesting results (i.e. answers to computational problems that aren't solvable with currently available computers) with far less overhead. In this lecture I relate the history of quantum simulation research and highlight key results. Specifically we begin with Feynman's concept of quantum simulation and Lloyd's formalization of quantum simulation into a procedure that could be run efficiently on a quantum computer. We then investigate the conditions for a Hamiltonian to be simulatable and pay particular attention to Aharanov and Ta-Shma's sparse Hamiltonian lemma. Strategies for reducing both time and space complexity are then reviewed. Two types of quantum simulation are explored experimentally: "analogue" and "digital". We discuss the nature of these experiments and the different approaches and goals in teach type of simulation.