2012

Hamiltonian Simulation Using Linear Combinations of Unitary Operations

Childs, Andrew M., Wiebe, Nathan

Understand

We present a new approach to simulating Hamiltonian dynamics based on implementing linear combinations of unitary operations rather than products of unitary operations.

The resulting algorithm has superior performance to existing simulation algorithms based on product formulas and, most notably, scales better with the simulation error than any known Hamiltonian simulation technique.
Our main tool is a general method to nearly deterministically implement linear combinations of nearby unitary operations, which we show is optimal among a large class of methods.

Built on

L. F. Richardson, The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam , Philosophical Transactions of the Royal Society of London Series A 210
1911
Earlier work this paper cites.
M. Abramowitz and I. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables , vol. 55 of Applied Mathematics Series (U.S. Government Printing Office, 1964)
1964
Earlier work this paper cites.
A. M. Childs, Universal computation by quantum walk , Physical Review Letters 102
Original
1972
Earlier work this paper cites.
Q. Sheng, Solving linear partial differential equations by exponential splitting , IMA Journal of Numerical Analysis 9
1989
Earlier work this paper cites.
M. Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics , Journal of Mathematical Physics 32
1991
Earlier work this paper cites.
S. Lloyd, Universal quantum simulators , Science 273
1996
Earlier work this paper cites.
S. Blanes, F. Casas, and J. Ros, Extrapolation of symplectic integrators , Celestial Mechanics and Dynamical Astronomy 75
1999
Earlier work this paper cites.
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by quantum walk , in Proceedings of the 35th ACM Symposium on Theory of Computing (2003), pp. 59–68, eprint arXiv:quant-ph/0209131
2003
Earlier work this paper cites.
D. Aharonov and A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge , in Proceedings of the 35th ACM Symposium on Theory of Computing (2003), pp. 20–29, eprint arXiv:quant-ph/0301023
2003
Earlier work this paper cites.

Similar

M. E. A. El-Mikkawy, Explicit inverse of a generalized Vandermonde matrix , Applied Mathematics and Computation 146
2003
Cited alongside, same era.
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, Adiabatic quantum computation is equivalent to standard quantum computation , SIAM Journal on Computing 37
2004
Cited alongside, same era.
A. M. Childs, Quantum information processing in continuous time , Ph.D. thesis, Massachusetts Institute of Technology (2004)
2004
Cited alongside, same era.
D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians , Communications in Mathematical Physics 270
2007
Cited alongside, same era.
E. Farhi, J. Goldstone, and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree , Theory of Computing 4
2008
Cited alongside, same era.
A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations , Physical Review Letters 103
Original
2009
Cited alongside, same era.
R. Cleve, D. Gottesman, M. Mosca, R. D. Somma, and D. Yonge-Mallo, Efficient discrete-time simulations of continuous-time quantum query algorithms , in Proceedings of the 41st ACM Symposium on Theory of Computing (2009), pp. 409–416, eprint arXiv:0811.4428
Original
2009
Cited alongside, same era.
D. W. Berry, Quantum algorithms for solving linear differential equations (2010), eprint arXiv:1010.2745
Original
2010
Cited alongside, same era.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution , eprint arXiv:quant-ph/0001106
Cited in the paper.
A. M. Childs, On the relationship between continuous- and discrete-time quantum walk , Communications in Mathematical Physics 294
Original
Cited in the paper.

Then

N. Wiebe, D. W. Berry, P. Høyer, and B. C. Sanders, Higher order decompositions of ordered operator exponentials , Journal of Physics A 43
Original
2010
Later among the works it cites.
S. Chin, Multi-product splitting and Runge-Kutta-Nyström integrators , Celestial Mechanics and Dynamical Astronomy 106
2010
Later among the works it cites.
A. M. Childs and R. Kothari, Simulating sparse Hamiltonians with star decompositions , in Theory of Quantum Computation, Communication, and Cryptography (Springer, 2011), vol. 6519 of Lecture Notes in Computer Science , pp. 94–103, eprint arXiv:1003.3683
Original
2011
Later among the works it cites.
N. Wiebe, D. W. Berry, P. Høyer, and B. C. Sanders, Simulating quantum dynamics on a quantum computer , Journal of Physics A 44
Original
2011
Later among the works it cites.
D. Poulin, A. Qarry, R. Somma, and F. Verstraete, Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space , Physical Review Letters 106
Original
2011
Later among the works it cites.
S. A. Chin and J. Geiser, Multi-product operator splitting as a general method of solving autonomous and nonautonomous equations , IMA Journal of Numerical Analysis 31
2011
Later among the works it cites.
A. Papageorgiou and C. Zhang, On the efficiency of quantum algorithms for Hamiltonian simulation , to appear in Quantum Information Processing (2012), eprint arXiv:1005.1318
Original
2012
Closest in time.
D. W. Berry and A. M. Childs, Black-box Hamiltonian simulation and unitary implementation , Quantum Information and Computation 12
Original
2012
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…