A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations

doi:10.1007/s42967-023-00336-z

Abstract

Abstract: Given the Hamiltonian, the evaluation of unitary operators has been at the heart of many quantum algorithms. Motivated by existing deterministic and random methods, we present a hybrid approach, where Hamiltonians with large amplitude are evaluated at each time step, while the remaining terms are evaluated at random. The bound for the mean square error is obtained, together with a concentration bound. The mean square error consists of a variance term and a bias term, arising, respectively, from the random sampling of the Hamiltonian terms and the operator-splitting error. Leveraging on the bias/variance tradeoff, the error can be minimized by balancing the two. The concentration bound provides an estimate of the number of gates. The estimates are verified using numerical experiments on classical computers.

Key words: Trotter splitting, Quantum simulation, Unitary dynamics

CLC Number:

Shi Jin, Xiantao Li. A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 442-469.

TrendMD

References

1. An, D., Fang, D., Lin, L.: Time-dependent unbounded Hamiltonian simulation with vector norm scaling. Quantum 5, 459 (2021)
2. Aspuru-Guzik, A.: Simulated quantum computation of molecular energies. Science 309, 1704–1707 (2005). https:// doi. org/ 10. 1126/ scien ce. 11134 79
3. Babbush, R., McClean, J., Wecker, D., Aspuru-Guzik, A., Wiebe, N.: Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation. Phys. Rev. A 91(2), 022311 (2015)
4. Babbush, R., Wiebe, N., McClean, J., McClain, J., Neven, H., Chan, K.L.: Low-depth quantum simulation of materials. Phys. Rev. X 8(1), 011044 (2018)
5. Baker, H.F.: Alternants and continuous groups. Proc. London Math. Soc. 2(1), 24–47 (1905)
6. Bravyi, S.B., Kitaev, A.Y.: Fermionic quantum computation. Ann. Phys. 298(1), 210–226 (2002)
7. Campbell, E.: Random compiler for fast Hamiltonian simulation. Phys. Rev. Lett. 123(7), 070503 (2019)
8. Campbell, J.E.: On a law of combination of operators (second paper). Proc. London Math. Soc. 1(1), 14–32 (1897)
9. Chen, C.F., Huang, H.Y., Kueng, R., Tropp, J.A.: Quantum simulation via randomized product formulas: low gate complexity with accuracy guarantees. arXiv: 2008. 11751 (2020)
10. Childs, A.M., Li, T.Y.: Efficient simulation of sparse Markovian quantum dynamics. arXiv: 1611. 05543 (2016)
11. Childs, A.M., Ostrander, A., Su, Y.: Faster quantum simulation by randomization. Quantum 3, 182 (2019)
12. Childs, A.M., Su, Y.: Nearly optimal lattice simulation by product formulas. Phys. Rev. Lett. 123(5), 050503 (2019)
13. Childs, A.M., Su, Y, Tran, M.C., Wiebe, N., Zhu, S.C.: Theory of Trotter error with commutator scaling. Phys. Rev. X 11(1), 011020 (2021)
14. Childs, A.M, Wiebe, N.: Hamiltonian simulation using linear combinations of unitary operations. arXiv: 1202. 5822 (2012)
15. Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. London A 454, 339–354 (1998)
16. Cleve, R., Wang, C.H.: Efficient quantum algorithms for simulating lindblad evolution. arXiv: 1612. 09512 (2016)
17. Deuflhard, P., Bornemann, F.: Scientific Computing with Ordinary Differential Equations. Springer New York, NY (2012)
18. Faehrmann, P.K., Steudtner, M., Kueng, R., Kieferova, M., Eisert, J.: Randomizing multi-product formulas for improved Hamiltonian simulation. arXiv: 2101. 07808 (2021)
19. Feynman, R.P.: Quantum mechanical computers. Opt. News 11(2), 11–20 (1985)
20. Gilyén, A., Su, Y., Low, G.H., Wiebe, N.: Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In: Proceedings of the 51st Annual ACM Sigact Symposium on Theory of Computing, pp. 193–204 (2019)
21. Gokhale, P., Angiuli, O., Ding, Y.S., Gui, K.W., Tomesh, T., Suchara, M., Martonosi, M., Chong, F.T.: Minimizing state preparations in variational quantum eigensolver by partitioning into commuting families. arXiv: 1907. 13623 (2019)
22. Golse, F., Jin, S., Paul, T.: The random batch method for n-body quantum dynamics. arXiv: 1912. 07424 (2020)
23. Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for solving linear systems of equations. arXiv: 0811.3171 (2009)
24. Hastings, M.B., Wecker, D., Bauer, B., Troyer, M.: Improving quantum algorithms for quantum chemistry. arXiv: 1403. 1539 (2014)
25. Hausdorff, F.: Die symbolische exponentialformel in der gruppentheorie. Ber. Verh. Kgl. SÃ chs. Ges. Wiss. Leipzig. Math.-phys. Kl. 58, 19–48 (1906)
26. Havlíček, V., Troyer, M., Whitfield, J.D.: Operator locality in the quantum simulation of Fermionic models. Phys. Rev. A 95(3), 032332 (2017)
27. Jin, S., Li, L: Random batch methods for classical and quantum interacting particle systems and statistical samplings. arXiv: 2104. 04337 (2021)
28. Jin, S., Li, L., Liu, J.G..: Random batch methods (RBM) for interacting particle systems. J. Comput. Phys. 400, 108877 (2020)
29. Jin, S., Li, L., Liu, J.G.: Convergence of the random batch method for interacting particles with disparate species and weights. SIAM J. Num. Analys. 59(2), 746–768 (2021)
30. Jin, S., Li, L., Xu, Z.L., Zhao, Y.: A random batch Ewald method for particle systems with Coulomb interactions. SIAM. J. Sci. Comp. 43, B937–B960 (2021)
31. Jin, S., Li, X.T.: Random batch algorithms for quantum Monte Carlo simulations. Commun. Comput. Phys. 28(5), 1907–1936 (2020)
32. Jordan, P., Wigner, E.P.: About the Pauli exclusion principle. Z. Phys. 47(631), 14–75 (1928)
33. Kutin, S.: Extensions to McDiarmid’s inequality when differences are bounded with high probability. Dept. Comput. Sci., Univ. Chicago, Chicago, IL, USA, Tech. Rep. TR-2002-04 (2002)
34. Li, L., Xu, Z.L., Zhao, Y.: A random-batch Monte Carlo method for many-body systems with singular kernels. SIAM J. Sci. Comput. 42(3), A1486–A1509 (2020)
35. McClean, J.: OpenFermion: the electronic structure package for quantum computers. Quant. Sci. Technol. 5, 034041 (2020)
36. McDiarmid, C.: On the method of bounded differences. Surv. Combin. 141(1), 148–188 (1989)
37. McDiarmid, C., Concentration. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds) Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195–248. Springer-Verlag, Berlin (1998)
38. Montanaro, A.: Quantum speedup of Monte Carlo methods. Proc. R. Soc. A 471(2181), 20150301 (2015)
39. Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
40. Ouyang, Y.K., White, D.R., Campbell, E.T.: Compilation by stochastic Hamiltonian sparsification. Quantum 4, 235 (2020)
41. Poulin, D., Hastings, M.B, Wecker, D., Wiebe, N., Doherty, A.C, Troyer, M.: The Trotter step size required for accurate quantum simulation of quantum chemistry. arXiv: 1406. 4920 (2014)
42. Qin, Y.M.: Integral and Discrete Inequalities and Their Applications. Springer International Publishing, Switzerland (2016)
43. Ramsay, J.O., Silverman, B.W.: Applied Functional Data Analysis: Methods and Case Studies. Springer International Publishing, New York (2002)
44. Rio, E.: On McDiarmid’s concentration inequality. Electr. Commun. Prob. 18, 1–11 (2013)
45. Seeley, J.T., Richard, M.J., Love, P.J.: The Bravyi-Kitaev transformation for quantum computation of electronic structure. J. Chem. Phys. 137(22), 224109 (2012)
46. Sweke, R., Wilde, F., Meyer, J., Schuld, M., Fährmann, P.K., Meynard-Piganeau, B., Eisert, J.: Stochastic gradient descent for hybrid quantum-classical optimization. Quantum 4, 314 (2020)
47. Tran, M.C., Guo, A.Y., Su, Y., Garrison, J.R., Eldredge, Z., Foss-Feig, M., Childs, A.M., Gorshkov, A.V.: Locality and digital quantum simulation of power-law interactions. Phys. Rev. X 9(3), 031006 (2019)
48. Tranter, A., Love, P.J., Mintert, F., Coveney, P.V.: A comparison of the Bravyi-Kitaev and JordanWigner transformations for the quantum simulation of quantum chemistry. J. Chem. Theory Comput. 14(11), 5617–5630 (2018)
49. Tranter, A., Love, P.J., Mintert, F., Wiebe, N., Coveney, P.V.: Ordering of Trotterization: impact on errors in quantum simulation of electronic structure. Entropy 21(12), 1218 (2019)
50. Tropp, J.A: An introduction to matrix concentration inequalities. arXiv: 1501. 01571 (2015)
51. Wecker, D., Bauer, B., Clark, B.K., Hastings, M.B., Troyer, M.: Gate count estimates for performing quantum chemistry on small quantum computers. arXiv: 1312. 1695 (2014)
52. Whitfield, J.D., Biamonte, J., Aspuru-Guzik, A.: Simulation of electronic structure Hamiltonians using quantum computers. Mol. Phys. 109(5), 735–750 (2011)