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:
Date:  Saturday, Sep. 15, 2007 , 15:0017:00  Place:  Niavaran Bldg., Niavaran Square, Tehran, Iran 
