Abstract
We consider randomized algorithms for simulating the evolution of a Hamiltonian \(H ={ \sum \nolimits }_{j=1}^{m}{H}_{j}\) for time t. The evolution is simulated by a product of exponentials of H j in a random sequence, and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. First we provide a scheme to bound the error of the final quantum state in a randomized algorithm. Then we obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
R. P. Feynman, Simulating Physics with computers, Int. J. Theoret. Phys. 21, 467–488 (1982)
S. Lloyd, Universal quantum simulators, Science 273, 1073–1078 (1996)
C. Zalka, Simulating Quantum Systems on a Quantum Computer, Proc. R. Soc. Lond. A, 454, 313–323 (1998)
D. W. Berry, G. Ahokas, R. Cleve, B. C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics 270, 359 (2007)
I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, A. Aspuru-Guzik, Polynomial-time quantum algorithm for the simulation of chemical dynamics, Proc. Natl. Acad. Sci. 105, 18681(2008)
D. Aharonov, A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, Proc. 35th Annual ACM Symp. on Theoty of Computing, 20–29 (2003)
E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution, quant-ph/0001106 (2000)
E. Farhi, S. Gutmann, Analog analogue of a digital quantum computation. Phys. Rev. A 57(4), 24032406 (1998)
A. M. Childs, E. Farhi, S. Gutmann, An example of the difference between quantum and classical random walks, J. Quant. Inf. Proc. 1, 35–43 (2002)
E. Farhi, J. Goldstone, S. Gutmann, A Quantum Algorithm for the Hamiltonian NAND Tree, quant-ph/0702144 (2007)
A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett, 102, 180501 (2009)
A. M. Childs, On the relationship between continuous- and discrete-time quantum walk, quant-ph/0810.0312 (2008)
D. W. Berry, A. M. Childs, The quantum query complexity of implementing black-box unitary transformations, quant-ph/0910. 4157 (2009)
M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press (2000)
G. Strang, On the construction and comparison of difference schemes, SIAM J. Num. Analysis, 506–517 (1968)
M. Suzuki, Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations, Phys. Lett. A 146, 319–323 (1990)
M. Suzuki, General theory of fractal path integrals with application to many-body theories and statistical physics, J. Math. Phys, 32, 400–407 (1991)
Acknowledgements
We are grateful to Anargyros Papageorgiou, Joseph F. Traub, Henryk Wozniakowski, Columbia University and Zhengfeng Ji, Perimeter Institute for Theoretical Physics, for their very helpful discussions and comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhang, C. (2012). Randomized Algorithms for Hamiltonian Simulation. In: Plaskota, L., Woźniakowski, H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2010. Springer Proceedings in Mathematics & Statistics, vol 23. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27440-4_42
Download citation
DOI: https://doi.org/10.1007/978-3-642-27440-4_42
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27439-8
Online ISBN: 978-3-642-27440-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)