4715Accesses
643Citations
39 Altmetric
2Mentions
Abstract
We present an efficient quantum algorithm for simulating the evolution of a quantum state for a sparse HamiltonianH over a given timet in terms of a procedure for computing the matrix entries ofH. In particular, whenH acts onn 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 integerk such that the simulation requiresO((log*n)t1+1/2k) accesses to matrix entries ofH. We also show that the temporal scaling cannot be significantly improved beyond this, because sublinear time scaling is not possible.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Starting from 10 chapters or articles per month
- Access and download chapters and articles from more than 300k books and 2,500 journals
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, books and news in related subjects, suggested using machine learning.References
Shor, P. W.: Algorithms for quantum computation: Discrete logarithms and factoring. In:Proc. 35th Symp. on Foundations of Computer Science, Los Alamitos, CA:IEEE, 1994, pp. 124–134
Grover L. (1997) Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325–328
Kempe J., Kitaev A., Regev O. (2006) The complexity of the local Hamiltonian problem. SIAM J. Computing 35: 1070–1097
Feynman R.P. (1982) Simulating physics with computers. Int. J. Theoret. Phys. 21, 467–488
Lloyd S. (1996) Universal quantum simulators. Science 273: 1073–1078
Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In:Proc. 35th Annual ACM Symp. on Theory of Computing, New York:ACM, 2003, pp. 20–29
Childs A., Farhi E., Gutmann S. (2002) An example of the difference between quantum and classical random walks. J. Quant. Inf. Proc. 1, 35–43
Shenvi N., Kempe J., Whaley K.B. (2003) Quantum random-walk search algorithm. Phys. Rev. A 67: 052307
Childs A., Goldstone J. (2004) Spatial search by quantum walk. Phys. Rev. A 70: 022314
Ambainis, A.: Quantum walk algorithm for element distinctness. In:Proc. 45th Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE, 2004, pp. 22–31
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In:Proc. 16th ACM-SIAM SODA, Philadelphia, PA:SIAM, 2005, pp. 1099–1108
Suzuki M. (1990) Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations. Phys. Lett. A 146, 319–323
Suzuki M. (1991) General theory of fractal path integrals with applications to many-body theories and statistical physics. J. Math. Phys. 32, 400–407
Childs A.M. Quantum information processing in continuous time.Ph.D. Thesis, Massachusetts Institute of Technology, 2004
Cole R., Vishkin U. (1986) Deterministic coin tossing with applications to optimal parallel list ranking. Inform. and Control 70, 32–53
Linial N. (1992) Locality in distributed graph algorithms. SIAM J. Comput. 21, 193–201
Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Guttman, S., Spielman, D.A.: Exponential algorithmic speedup by quantum walk. In:Proc. 35th Annual ACM Symp. on Theory of Computing, New York: ACM, 2003, pp. 59–68
Ahokas, G.: Improved algorithms for approximate quantum Fourier transforms and sparse Hamiltonian simulations.M.Sc. Thesis, University of Calgary, 2004
Beals R., Buhrman H., Cleve R., Mosca M., de Wolf R. (2001) Quantum lower bounds by polynomials. J. ACM 48, 778–797
Farhi E., Goldstone J., Gutmann S., Sipser M. (1998) Limit on the speed of quantum computation in determining parity. Phys. Rev. Lett. 81: 5442–5444
Nielsen M.A., Chuang I.L., (2000) Quantum Computation and Quantum Information. Cambridge, Cambridge University Press
Author information
Authors and Affiliations
Department of Physics, The University of Queensland, Queensland, 4072, Australia
Dominic W. Berry
Institute for Quantum Information Science, University of Calgary, Alberta, T2N 1N4, Canada
Dominic W. Berry, Graeme Ahokas, Richard Cleve & Barry C. Sanders
Department of Computer Science, University of Calgary, Alberta, T2N 1N4, Canada
Graeme Ahokas & Richard Cleve
School of Computer Science, University of Waterloo, Ontario, N2L 3G1, Canada
Richard Cleve
Institute for Quantum Computing, University of Waterloo, Ontario, N2L 3G1, Canada
Richard Cleve
Centre for Quantum Computer Technology, Macquarie University, Sydney, New South Wales, 2109, Australia
Barry C. Sanders
- Dominic W. Berry
Search author on:PubMed Google Scholar
- Graeme Ahokas
Search author on:PubMed Google Scholar
- Richard Cleve
Search author on:PubMed Google Scholar
- Barry C. Sanders
Search author on:PubMed Google Scholar
Additional information
Communicated by M.B. Ruskai
Rights and permissions
About this article
Cite this article
Berry, D.W., Ahokas, G., Cleve, R.et al. Efficient Quantum Algorithms for Simulating Sparse Hamiltonians.Commun. Math. Phys.270, 359–371 (2007). https://doi.org/10.1007/s00220-006-0150-x
Received:
Accepted:
Published:
Issue date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
Keywords
Profiles
- Barry C. SandersView author profile