Efficient Quantum Algorithms for Simulating Sparse Hamiltonians |
| |
| Authors: | Dominic W Berry Graeme Ahokas Richard Cleve |
| |
| Institution: | (1) Department of Physics, The University of Queensland, Queensland, 4072, Australia;(2) Institute for Quantum Information Science, University of Calgary, Alberta, T2N 1N4, Canada;(3) Department of Computer Science, University of Calgary, Alberta, T2N 1N4, Canada;(4) School of Computer Science, University of Waterloo, Ontario, N2L 3G1, Canada;(5) Institute for Quantum Computing, University of Waterloo, Ontario, N2L 3G1, Canada;(6) Centre for Quantum Computer Technology, Macquarie University, Sydney, New South Wales, 2109, Australia |
| |
| Abstract: | We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse Hamiltonian H over a given time t in terms of a procedure for computing the matrix entries of H. In particular, when H acts on n qubits, has at most a constant number of nonzero entries in each row/column, and ||H|| is bounded by a constant, we may select any positive integer k such that the simulation requires O((log*
n)t
1+1/2k
) accesses to matrix entries of H. We also show that the temporal scaling cannot be significantly improved beyond this, because sublinear time scaling is not
possible. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
