Abstract

There are three main applications of quantum computer algorithms: the hidden subgroup problem, search problems, and our interest here: universal quantum simulation. We develop an efficient algorithm for simulating quantum evolution for an arbitrary and a priori unknown Hamiltonian over any time t: for n qubits and at most a constant number of nonzero entries (sparse) in each column of the Hamiltonian matrix, with norm bounded by a constant, the cost of the simulation is nearly linear in t and nearly constant in n, and we prove that there cannot be an algorithm that is sub linear in t. Our work provides a firm algorithmic foundation for studying a quantum computer as a simulator, especially with respect to assessing and optimizing the resources required for the simulation.



Information: