A Partially Random Trotter Algorithm for Quantum Hamiltonian Simulations

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 trade-off, 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.

Keywords

Trotter splitting / Quantum simulation / Unitary dynamics / 68Q12 / 62L20 / 34A45

References

[1] An D, Fang D, Lin L. Time-dependent unbounded Hamiltonian simulation with vector norm scaling. Quantum. 2021, 5: 459

[2] Aspuru-Guzik A. Simulated quantum computation of molecular energies. Science. 2005, 309: 1704-1707

[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. 2015, 91(2): 022311

[4] Babbush R, Wiebe N, McClean J, McClain J, Neven H, Chan KL. Low-depth quantum simulation of materials. Phys. Rev. X. 2018, 8(1): 011044

[5] Baker HF. Alternants and continuous groups. Proc. London Math. Soc.. 1905, 2(1): 24-47

[6] Bravyi SB, Kitaev AY. Fermionic quantum computation. Ann. Phys.. 2002, 298(1): 210-226

[7] Campbell E. Random compiler for fast Hamiltonian simulation. Phys. Rev. Lett.. 2019, 123(7) 070503

[8] Campbell JE. On a law of combination of operators (second paper). Proc. London Math. Soc.. 1897, 1(1): 14-32

[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 AM, Ostrander A, Su Y. Faster quantum simulation by randomization. Quantum. 2019, 3: 182

[12] Childs AM, Su Y. Nearly optimal lattice simulation by product formulas. Phys. Rev. Lett.. 2019, 123(5) 050503

[13] Childs AM, Su Yuan, Tran MC, Wiebe N, Zhu SC. Theory of Trotter error with commutator scaling. Phys. Rev. X. 2021, 11(1): 011020

[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. 1998, 454: 339-354

[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 RP. Quantum mechanical computers. Opt. News. 1985, 11(2): 11-20

[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 JD. Operator locality in the quantum simulation of Fermionic models. Phys. Rev. A. 2017, 95(3): 032332

[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 JG. Random batch methods (RBM) for interacting particle systems. J. Comput. Phys.. 2020, 400 108877

[29] Jin S, Li L, Liu JG. Convergence of the random batch method for interacting particles with disparate species and weights. SIAM J. Num. Analys.. 2021, 59(2): 746-768

[30] Jin S, Li L, Xu ZL, Zhao Y. A random batch Ewald method for particle systems with Coulomb interactions. SIAM. J. Sci. Comp.. 2021, 43: B937-B960

[31] Jin S, Li XT. Random batch algorithms for quantum Monte Carlo simulations. Commun. Comput. Phys.. 2020, 28(5): 1907-1936

[32] Jordan P, Wigner EP. About the Pauli exclusion principle. Z. Phys.. 1928, 47(631): 14-75

[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 ZL, Zhao Y. A random-batch Monte Carlo method for many-body systems with singular kernels. SIAM J. Sci. Comput.. 2020, 42(3): A1486-A1509

[35] McClean J. OpenFermion: the electronic structure package for quantum computers. Quant. Sci. Technol.. 2020, 5: 034041

[36] McDiarmid C. On the method of bounded differences. Surv. Combin.. 1989, 141(1): 148-188

[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. 2015, 471(2181): 20150301

[39] Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

[40] Ouyang YK, White DR, Campbell ET. Compilation by stochastic Hamiltonian sparsification. Quantum. 2020, 4: 235

[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.. 2013, 18: 1-11

[45] Seeley JT, Richard MJ, Love PJ. The Bravyi-Kitaev transformation for quantum computation of electronic structure. J. Chem. Phys.. 2012, 137(22) 224109

[46] Sweke R, Wilde F, Meyer J, Schuld M, Fährmann PK, Meynard-Piganeau B, Eisert J. Stochastic gradient descent for hybrid quantum-classical optimization. Quantum. 2020, 4: 314

[47] Tran MC, Guo AY, Su Y, Garrison JR, Eldredge Z, Foss-Feig M, Childs AM, Gorshkov AV. Locality and digital quantum simulation of power-law interactions. Phys. Rev. X. 2019, 9(3)): 031006

[48] Tranter A, Love PJ, Mintert F, Coveney PV. A comparison of the Bravyi-Kitaev and Jordan-Wigner transformations for the quantum simulation of quantum chemistry. J. Chem. Theory Comput.. 2018, 14(11): 5617-5630

[49] Tranter Andrew, Love Peter J, Mintert Florian, Wiebe Nathan, Coveney Peter V. Ordering of Trotterization: impact on errors in quantum simulation of electronic structure. Entropy. 2019, 21(12): 1218

[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 JD, Biamonte J, Aspuru-Guzik A. Simulation of electronic structure Hamiltonians using quantum computers. Mol. Phys.. 2011, 109(5): 735-750

Funding

Directorate for Mathematical and Physical Sciences(1953120)

Division of Mathematical Sciences(2111221)

National Natural Science Foundation of China(12031013)

RIGHTS & PERMISSIONS

Shanghai University