Black-box Hamiltonian simulation and unitary implementation

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as ⁴ and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified unitary operation use O (²) elementary gates, we show that a black-box unitary can be performed with bounded error using O (^2/3 () ^4/3) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O () queries, which is optimal.