  We investigate the sample complexity of Hamiltonian simulation: how many
copies of an unknown quantum state are required to simulate a Hamiltonian
encoded by the density matrix of that state? We show that the procedure
proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631--633, 2014]
is optimal for this task. We further extend their method to the case of
multiple input states, showing how to simulate any Hermitian polynomial of the
states provided. As applications, we derive optimal algorithms for commutator
simulation and orthogonality testing, and we give a protocol for creating a
coherent superposition of pure states, when given sample access to those
states. We also show that this sample-based Hamiltonian simulation can be used
as the basis of a universal model of quantum computation that requires only
partial swap operations and simple single-qubit states.
