Faster quantum simulation by randomization

Andrew M. Childs1,2,3, Aaron Ostrander2,3,4, and Yuan Su1,2,3

1Department of Computer Science, University of Maryland
2Institute for Advanced Computer Studies, University of Maryland
3Joint Center for Quantum Information and Computer Science, University of Maryland
4Department of Physics, University of Maryland

Product formulas can be used to simulate Hamiltonian dynamics on a quantum computer by approximating the exponential of a sum of operators by a product of exponentials of the individual summands. This approach is both straightforward and surprisingly efficient. We show that by simply randomizing how the summands are ordered, one can prove stronger bounds on the quality of approximation for product formulas of any given order, and thereby give more efficient simulations. Indeed, we show that these bounds can be asymptotically better than previous bounds that exploit commutation between the summands, despite using much less information about the structure of the Hamiltonian. Numerical evidence suggests that the randomized approach has better empirical performance as well.

► BibTeX data

► References

[1] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 20-29, 2003. 10.1145/​780542.780546. arXiv:quant-ph/​0301023.
https:/​/​doi.org/​10.1145/​780542.780546
arXiv:quant-ph/0301023

[2] Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe. Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation. Physical Review A, 91: 022311, 2015. 10.1103/​PhysRevA.91.022311. arXiv:1410.8159.
https:/​/​doi.org/​10.1103/​PhysRevA.91.022311
arXiv:1410.8159

[3] R. Barends, L. Lamata, J. Kelly, L. García-Álvarez, A. G. Fowler, A Megrant, E Jeffrey, T. C. White, D. Sank, J. Y. Mutus, B. Campbell, Yu Chen, Z. Chen, B. Chiaro, A. Dunsworth, I.-C. Hoi, C. Neill, P. J. J. O'Malley, C. Quintana, P. Roushan, A. Vainsencher, J. Wenner, E. Solano, and John M. Martinis. Digital quantum simulation of fermionic models with a superconducting circuit. Nature Communications, 6: 7654, 2015. 10.1038/​ncomms8654. arXiv:1501.07703.
https:/​/​doi.org/​10.1038/​ncomms8654
arXiv:1501.07703

[4] Dominic W. Berry and Andrew M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12 (1-2): 29-62, 2012. arXiv:0910.4157. 10.26421/​QIC12.1-2.
https:/​/​doi.org/​10.26421/​QIC12.1-2
arXiv:0910.4157

[5] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270 (2): 359-371, 2007. 10.1007/​s00220-006-0150-x. arXiv:quant-ph/​0508139.
https:/​/​doi.org/​10.1007/​s00220-006-0150-x
arXiv:quant-ph/0508139

[6] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proceedings of the 46th ACM Symposium on Theory of Computing, pages 283-292, 2014. 10.1145/​2591796.2591854. arXiv:1312.1414.
https:/​/​doi.org/​10.1145/​2591796.2591854
arXiv:1312.1414

[7] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114 (9): 090502, 2015a. 10.1103/​PhysRevLett.114.090502. arXiv:1412.4687.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502
arXiv:1412.4687

[8] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science, pages 792-809, 2015b. 10.1109/​FOCS.2015.54. arXiv:1501.01715.
https:/​/​doi.org/​10.1109/​FOCS.2015.54
arXiv:1501.01715

[9] Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356: 1057-1081, 2017. 10.1007/​s00220-017-3002-y. arXiv:1701.03684.
https:/​/​doi.org/​10.1007/​s00220-017-3002-y
arXiv:1701.03684

[10] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe. Time-dependent Hamiltonian simulation with $L^1$-norm scaling, 2019. arXiv:1906.07115.
arXiv:1906.07115

[11] Fernando G. S. L. Brandao and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science, pages 415-426, 2017. 10.1109/​FOCS.2017.45. arXiv:1609.05537.
https:/​/​doi.org/​10.1109/​FOCS.2017.45
arXiv:1609.05537

[12] Kenneth R. Brown, Robert J. Clark, and Isaac L. Chuang. Limitations of quantum simulation examined by simulating a pairing Hamiltonian using nuclear magnetic resonance. Physical Review Letters, 97: 050504, 2006. 10.1103/​PhysRevLett.97.050504. arXiv:quant-ph/​0601021.
https:/​/​doi.org/​10.1103/​PhysRevLett.97.050504
arXiv:quant-ph/0601021

[13] Earl Campbell. Shorter gate sequences for quantum computing by mixing unitaries. Physical Review A, 95: 042306, Apr 2017. 10.1103/​PhysRevA.95.042306. arXiv:1612.02689.
https:/​/​doi.org/​10.1103/​PhysRevA.95.042306
arXiv:1612.02689

[14] Earl Campbell. Random compiler for fast Hamiltonian simulation. Physical Review Letters, 123: 070503, Aug 2019. 10.1103/​PhysRevLett.123.070503. arXiv:1811.08017.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.070503
arXiv:1811.08017

[15] Andrew M. Childs and Yuan Su. Nearly optimal lattice simulation by product formulas. Physical Review Letters, 123: 050503, Aug 2019. 10.1103/​PhysRevLett.123.050503. arXiv:1901.00564.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.050503
arXiv:1901.00564

[16] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. Exponential algorithmic speedup by quantum walk. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 59-68, 2003. 10.1145/​780542.780552. arXiv:quant-ph/​0209131.
https:/​/​doi.org/​10.1145/​780542.780552
arXiv:quant-ph/0209131

[17] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115 (38): 9456-9461, 2018. 10.1073/​pnas.1801723115. arXiv:1711.10980.
https:/​/​doi.org/​10.1073/​pnas.1801723115
arXiv:1711.10980

[18] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum algorithm for the Hamiltonian NAND tree. Theory of Computing, 4 (1): 169-190, 2008. 10.4086/​toc.2008.v004a008.
https:/​/​doi.org/​10.4086/​toc.2008.v004a008

[19] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6-7): 467-488, 1982. 10.1007/​BF02650179.
https:/​/​doi.org/​10.1007/​BF02650179

[20] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice Hamiltonians. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 350-360, Oct 2018. 10.1109/​FOCS.2018.00041. arXiv:1801.03922.
https:/​/​doi.org/​10.1109/​FOCS.2018.00041
arXiv:1801.03922

[21] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103 (15): 150502, 2009. 10.1103/​PhysRevLett.103.150502. arXiv:0811.3171.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502
arXiv:0811.3171

[22] Matthew B. Hastings. Turning gate synthesis errors into incoherent errors. Quantum Information and Computation, 17 (5-6): 488-494, 2017. arXiv:1612.01011.
arXiv:1612.01011

[23] Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum algorithms for quantum field theories. Science, 336 (6085): 1130-1133, 2012. 10.1126/​science.1217069. arXiv:1111.3633.
https:/​/​doi.org/​10.1126/​science.1217069
arXiv:1111.3633

[24] B. P. Lanyon, C. Hempel, D. Nigg, M. Müller, R. Gerritsma, F. Zähringer, P. Schindler, J. T. Barreiro, M. Rambach, G. Kirchmair, M. Hennrich, P. Zoller, R. Blatt, and C. F. Roos. Universal digital quantum simulation with trapped ions. Science, 334 (6052): 57-61, 2011. 10.1126/​science.1208001. arXiv:1109.1512.
https:/​/​doi.org/​10.1126/​science.1208001
arXiv:1109.1512

[25] Seth Lloyd. Universal quantum simulators. Science, 273 (5278): 1073-1078, 1996. 10.1126/​science.273.5278.1073.
https:/​/​doi.org/​10.1126/​science.273.5278.1073

[26] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters, 118: 010501, 2017. 10.1103/​PhysRevLett.118.010501. arXiv:1606.02685.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501
arXiv:1606.02685

[27] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3: 163, July 2019. 10.22331/​q-2019-07-12-163. arXiv:1610.06546.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv:1610.06546

[28] Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe. Well-conditioned multiproduct Hamiltonian simulation, 2019. arXiv:1907.11679.
arXiv:1907.11679

[29] David Poulin, Angie Qarry, Rolando D. Somma, and Frank Verstraete. Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space. Physical Review Letters, 106 (17): 170501, 2011. 10.1103/​PhysRevLett.106.170501. arXiv:1102.1360.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.170501
arXiv:1102.1360

[30] David Poulin, Matthew B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doherty, and Matthias Troyer. The Trotter step size required for accurate quantum simulation of quantum chemistry. Quantum Information and Computation, 15 (5-6): 361-384, 2015. arXiv:1406.4920.
arXiv:1406.4920

[31] Sadegh Raeisi, Nathan Wiebe, and Barry C. Sanders. Quantum-circuit design for efficient simulations of many-body quantum dynamics. New Journal of Physics, 14: 103017, 2012. 10.1088/​1367-2630/​14/​10/​103017. arXiv:1108.4318.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​10/​103017
arXiv:1108.4318

[32] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114 (29): 7555-7560, 2017. 10.1073/​pnas.1619152114. arXiv:1605.03590.
https:/​/​doi.org/​10.1073/​pnas.1619152114
arXiv:1605.03590

[33] Masuo Suzuki. General theory of fractal path integrals with applications to many-body theories and statistical physics. Journal of Mathematical Physics, 32 (2): 400-407, 1991. 10.1063/​1.529425.
https:/​/​doi.org/​10.1063/​1.529425

[34] John Watrous. Simpler semidefinite programs for completely bounded norms. Chicago Journal of Theoretical Computer Science, 2013 (8), 2013. 10.4086/​cjtcs.2013.008.
https:/​/​doi.org/​10.4086/​cjtcs.2013.008

[35] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/​9781316848142.
https:/​/​doi.org/​10.1017/​9781316848142

[36] Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, and Matthias Troyer. Gate count estimates for performing quantum chemistry on small quantum computers. Physical Review A, 90: 022305, 2014. 10.1103/​PhysRevA.90.022305. arXiv:1312.1695.
https:/​/​doi.org/​10.1103/​PhysRevA.90.022305
arXiv:1312.1695

[37] Chi Zhang. Randomized algorithms for Hamiltonian simulation. In Leszek Plaskota and Henryk Woźniakowski, editors, Monte Carlo and Quasi-Monte Carlo Methods 2010, pages 709-719, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-27440-4. 10.1007/​978-3-642-27440-4_42.
https:/​/​doi.org/​10.1007/​978-3-642-27440-4_42

Cited by

[1] Sam McArdle, Suguru Endo, Alan Aspuru-Guzik, Simon Benjamin, and Xiao Yuan, "Quantum computational chemistry", arXiv:1808.10402.

[2] Andrew M. Childs and Yuan Su, "Nearly Optimal Lattice Simulation by Product Formulas", Physical Review Letters 123 5, 050503 (2019).

[3] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush, "Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization", arXiv:1902.10673.

[4] Bryan O'Gorman, William J. Huggins, Eleanor G. Rieffel, and K. Birgitta Whaley, "Generalized swap networks for near-term quantum computing", arXiv:1905.05118.

[5] Tyson Jones and Simon C Benjamin, "Quantum compilation and circuit optimisation via energy dissipation", arXiv:1811.03147.

[6] Earl Campbell, "Random Compiler for Fast Hamiltonian Simulation", Physical Review Letters 123 7, 070503 (2019).

[7] Seth Lloyd and Reevu Maity, "Efficient implementation of unitary transformations", arXiv:1901.03431.

[8] Benjamin D. M. Jones, George O. O'Brien, David R. White, Earl T. Campbell, and John A. Clark, "Optimising Trotter-Suzuki Decompositions for Quantum Simulation Using Evolutionary Strategies", arXiv:1904.01336.

[9] Oleksandr Kyriienko, "Quantum inverse iteration algorithm for near-term quantum devices", arXiv:1901.09988.

[10] Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov, "Lower bounds on the non-Clifford resources for quantum computations", arXiv:1904.01124.

[11] Mark Steudtner and Stephanie Wehner, "Quantum codes for quantum simulation of fermions on a square lattice of qubits", Physical Review A 99 2, 022308 (2019).

[12] Suguru Endo, Ying Li, Simon Benjamin, and Xiao Yuan, "Variational quantum simulation of general processes", arXiv:1812.08778.

[13] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe, "Time-dependent Hamiltonian simulation with $L^1$-norm scaling", arXiv:1906.07115.

[14] Suguru Endo, Qi Zhao, Ying Li, Simon Benjamin, and Xiao Yuan, "Mitigating algorithmic errors in Hamiltonian simulation", arXiv:1808.03623.

[15] Ian D. Kivlichan, Christopher E. Granade, and Nathan Wiebe, "Phase estimation with randomized Hamiltonians", arXiv:1907.10070.

The above citations are from SAO/NASA ADS (last updated 2019-09-22 03:00:09). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-09-22 03:00:07).