Quantum-assisted Monte Carlo algorithms for fermions

Xiaosi Xu and Ying Li

Graduate School of China Academy of Engineering Physics, Beijing 100193, China

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Quantum computing is a promising way to systematically solve the longstanding computational problem, the ground state of a many-body fermion system. Many efforts have been made to realise certain forms of quantum advantage in this problem, for instance, the development of variational quantum algorithms. A recent work by Huggins et al. [1] reports a novel candidate, i.e. a quantum-classical hybrid Monte Carlo algorithm with a reduced bias in comparison to its fully-classical counterpart. In this paper, we propose a family of scalable quantum-assisted Monte Carlo algorithms where the quantum computer is used at its minimal cost and still can reduce the bias. By incorporating a Bayesian inference approach, we can achieve this quantum-facilitated bias reduction with a much smaller quantum-computing cost than taking empirical mean in amplitude estimation. Besides, we show that the hybrid Monte Carlo framework is a general way to suppress errors in the ground state obtained from classical algorithms. Our work provides a Monte Carlo toolkit for achieving quantum-enhanced calculation of fermion systems on near-term quantum devices.

Solving the Schrodinger equation of many-body fermion systems is essential in many scientific fields. Quantum Monte Carlo (QMC) is a group of well-developed classical algorithms that have been widely used. However, a sign problem prohibits its use for large systems as the variance of the results increases exponentially with the system size. Common methods to constrain the sign problem usually introduces some bias. We consider incorporating quantum computers into QMC to reduce the bias. Prior works have some issues with scalability in general and quantum computation cost. In this work, we try to address the issues and introduce a framework of quantum-assisted QMC algorithms where the quantum computer is involved at flexible levels. We describe two strategies based on the extent of quantum resources used and show notably improved numerical results compared with the classical counterpart. To further reduce the quantum computing measurements, we introduce a Bayesian inference method and show that a stable quantum advantage can be maintained. With inherent symmetry in the target physical system, our quantum-assisted QMC is resilient to errors. By making our quantum-assisted QMC a subroutine of the subspace diagonalization algorithm, we show that quantum-assisted QMC is a general method of reducing errors in other classical or quantum algorithms. The quantum-assisted QMC is a potentially new method to demonstrate some level of quantum advantage on NIST machines.

► BibTeX data

► References

[1] William J Huggins, Bryan A O’Gorman, Nicholas C Rubin, David R Reichman, Ryan Babbush, and Joonho Lee. Unbiasing fermionic quantum monte carlo with a quantum computer. Nature, 603 (7901): 416–420, 2022. https:/​/​doi.org/​10.1038/​s41586-021-04351-z.

[2] Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in second quantization. New Journal of Physics, 18 (3): 033032, 2016. https:/​/​doi.org/​10.1088/​1367-2630/​18/​3/​033032.

[3] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1): 015003, 2020. https:/​/​doi.org/​10.1103/​RevModPhys.92.015003.

[4] Raffaele Resta. Manifestations of berry's phase in molecules and condensed matter. Journal of Physics: Condensed Matter, 12 (9): R107, 2000. https:/​/​doi.org/​10.1088/​0953-8984/​12/​9/​201.

[5] Lingzhen Guo and Pengfei Liang. Condensed matter physics in time crystals. New Journal of Physics, 22 (7): 075003, 2020. https:/​/​doi.org/​10.1088/​1367-2630/​ab9d54.

[6] Jean Pierre Jeukenne, A Lejeune, and Claude Mahaux. Many-body theory of nuclear matter. Physics Reports, 25 (2): 83–174, 1976. https:/​/​doi.org/​10.1016/​0370-1573(76)90017-X.

[7] J Carlson, Stefano Gandolfi, Francesco Pederiva, Steven C Pieper, Rocco Schiavilla, KE Schmidt, and Robert B Wiringa. Quantum monte carlo methods for nuclear physics. Reviews of Modern Physics, 87 (3): 1067, 2015. https:/​/​doi.org/​10.1103/​RevModPhys.87.1067.

[8] Vladimir A Miransky and Igor A Shovkovy. Quantum field theory in a magnetic field: From quantum chromodynamics to graphene and dirac semimetals. Physics Reports, 576: 1–209, 2015. https:/​/​doi.org/​10.1016/​j.physrep.2015.02.003.

[9] Stanley J Brodsky, Hans-Christian Pauli, and Stephen S Pinsky. Quantum chromodynamics and other field theories on the light cone. Physics Reports, 301 (4-6): 299–486, 1998. https:/​/​doi.org/​10.1016/​S0370-1573(97)00089-6.

[10] Gabriel Kotliar, Sergej Y Savrasov, Kristjan Haule, Viktor S Oudovenko, O Parcollet, and CA Marianetti. Electronic structure calculations with dynamical mean-field theory. Reviews of Modern Physics, 78 (3): 865, 2006. https:/​/​doi.org/​10.1103/​RevModPhys.78.865.

[11] John W Negele. The mean-field theory of nuclear structure and dynamics. Reviews of Modern Physics, 54 (4): 913, 1982. https:/​/​doi.org/​10.1103/​RevModPhys.54.913.

[12] Rafael Guardiola. Monte carlo methods in quantum many-body theories. In Microscopic quantum many-body theories and their applications, pages 269–336. Springer, 1998. https:/​/​doi.org/​10.1016/​0375-9474(79)90217-3.

[13] Y-Y Shi, L-M Duan, and Guifre Vidal. Classical simulation of quantum many-body systems with a tree tensor network. Physical review a, 74 (2): 022320, 2006. https:/​/​doi.org/​10.1103/​PhysRevA.74.022320.

[14] Shi-Ju Ran, Angelo Piga, Cheng Peng, Gang Su, and Maciej Lewenstein. Few-body systems capture many-body physics: Tensor network approach. Physical Review B, 96 (15): 155120, 2017. https:/​/​doi.org/​10.1103/​PhysRevB.96.155120.

[15] Drew Creal. A survey of sequential monte carlo methods for economics and finance. Econometric reviews, 31 (3): 245–296, 2012. https:/​/​doi.org/​10.1080/​07474938.2011.607333.

[16] Liaw Y Batan, Gregory D Graff, and Thomas H Bradley. Techno-economic and monte carlo probabilistic analysis of microalgae biofuel production system. Bioresource technology, 219: 45–52, 2016. https:/​/​doi.org/​10.1016/​j.biortech.2016.07.085.

[17] Zheng-Zhi Sun, Cheng Peng, Ding Liu, Shi-Ju Ran, and Gang Su. Generative tensor network classification model for supervised machine learning. Physical Review B, 101 (7): 075135, 2020. https:/​/​doi.org/​10.1103/​PhysRevB.101.075135.

[18] Toshiyuki Tanaka. Mean-field theory of boltzmann machine learning. Physical Review E, 58 (2): 2302, 1998. https:/​/​doi.org/​10.1103/​PhysRevE.58.2302.

[19] Brian M Austin, Dmitry Yu Zubarev, and William A Lester Jr. Quantum monte carlo and related approaches. Chemical reviews, 112 (1): 263–288, 2012. https:/​/​doi.org/​10.1021/​cr2001564.

[20] Gerardo Ortiz, James E Gubernatis, Emanuel Knill, and Raymond Laflamme. Quantum algorithms for fermionic simulations. Physical Review A, 64 (2): 022319, 2001. https:/​/​doi.org/​10.1103/​PhysRevA.64.022319.

[21] Mario Motta and Shiwei Zhang. Ab initio computations of molecular systems by the auxiliary-field quantum monte carlo method. Wiley Interdisciplinary Reviews: Computational Molecular Science, 8 (5): e1364, 2018. https:/​/​doi.org/​10.1002/​wcms.1364.

[22] Nick S Blunt. Fixed-and partial-node approximations in slater determinant space for molecules. Journal of Chemical Theory and Computation, 17 (10): 6092–6104, 2021. https:/​/​doi.org/​10.1021/​acs.jctc.1c00500.

[23] Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum pcp conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 19–32, 2022. https:/​/​doi.org/​10.1145/​3519935.3519991.

[24] Chris Cade, Marten Folkertsma, and Jordi Weggemans. Complexity of the guided local hamiltonian problem: improved parameters and extension to excited states. arXiv preprint arXiv:2207.10097, 2022. https:/​/​doi.org/​10.48550/​arXiv.2207.10097.

[25] Sevag Gharibian, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae. Improved hardness results for the guided local hamiltonian problem. arXiv preprint arXiv:2207.10250, 2022. https:/​/​doi.org/​10.48550/​arXiv.2207.10250.

[26] James D Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. Simulation of electronic structure hamiltonians using quantum computers. Molecular Physics, 109 (5): 735–750, 2011. https:/​/​doi.org/​10.1080/​00268976.2011.552441.

[27] Pedro MQ Cruz, Gonçalo Catarina, Ronan Gautier, and Joaquín Fernández-Rossier. Optimizing quantum phase estimation for the simulation of hamiltonian eigenstates. Quantum Science and Technology, 5 (4): 044005, 2020. https:/​/​doi.org/​10.1088/​2058-9565/​abaa2c.

[28] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2: 79, 2018. https:/​/​doi.org/​10.22331/​q-2018-08-06-79.

[29] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S Kottmann, Tim Menke, et al. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics, 94 (1): 015004, 2022. https:/​/​doi.org/​10.1103/​RevModPhys.94.015004.

[30] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles. Noise-induced barren plateaus in variational quantum algorithms. Nature communications, 12 (1): 1–11, 2021. https:/​/​doi.org/​10.1038/​s41467-021-27045-6.

[31] Marco Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature communications, 12 (1): 1–12, 2021a. https:/​/​doi.org/​10.1038/​s41467-021-21728-w.

[32] Edward Grant, Leonard Wossnig, Mateusz Ostaszewski, and Marcello Benedetti. An initialization strategy for addressing barren plateaus in parametrized quantum circuits. Quantum, 3: 214, 2019. https:/​/​doi.org/​10.22331/​q-2019-12-09-214.

[33] Stefan H Sack, Raimel A Medina, Alexios A Michailidis, Richard Kueng, and Maksym Serbyn. Avoiding barren plateaus using classical shadows. PRX Quantum, 3: 020365, Jun 2022. https:/​/​doi.org/​10.1103/​PRXQuantum.3.020365.

[34] Yongdan Yang, Bing-Nan Lu, and Ying Li. Accelerated quantum monte carlo with mitigated error on noisy quantum computer. PRX Quantum, 2 (4): 040361, 2021. https:/​/​doi.org/​10.1103/​PRXQuantum.2.040361.

[35] Guglielmo Mazzola and Giuseppe Carleo. Exponential challenges in unbiasing quantum monte carlo algorithms with quantum computers. arXiv preprint arXiv:2205.09203, 2022. https:/​/​doi.org/​10.48550/​arXiv.2205.09203.

[36] Joonho Lee, David R Reichman, Ryan Babbush, Nicholas C Rubin, Fionn D. Malone, Bryan O'Gorman, and Huggins. William J. Response to "exponential challenges in unbiasing quantum monte carlo algorithms with quantum computers". arXiv preprint arXiv:2207.13776, 2022. https:/​/​doi.org/​10.48550/​arXiv.2207.13776.

[37] Ankit Mahajan and Sandeep Sharma. Symmetry-projected jastrow mean-field wave function in variational monte carlo. The Journal of Physical Chemistry A, 123 (17): 3911–3921, 2019. https:/​/​doi.org/​10.1021/​acs.jpca.9b01583.

[38] Alessandro Roggero, Abhishek Mukherjee, and Francesco Pederiva. Quantum monte carlo with coupled-cluster wave functions. Physical Review B, 88 (11): 115138, 2013. https:/​/​doi.org/​10.1103/​PhysRevB.88.115138.

[39] Anders W Sandvik and Guifre Vidal. Variational quantum monte carlo simulations with tensor-network states. Physical review letters, 99 (22): 220602, 2007. https:/​/​doi.org/​10.1103/​PhysRevLett.99.220602.

[40] DFB Ten Haaf, HJM Van Bemmel, JMJ Van Leeuwen, W Van Saarloos, and DM Ceperley. Proof for an upper bound in fixed-node monte carlo for lattice fermions. Physical Review B, 51 (19): 13039, 1995. https:/​/​doi.org/​10.1103/​physrevb.51.13039.

[41] Shiwei Zhang and Henry Krakauer. Quantum monte carlo method using phase-free random walks with slater determinants. Physical review letters, 90 (13): 136401, 2003. https:/​/​doi.org/​10.1103/​PhysRevLett.90.136401.

[42] Iliya Sabzevari and Sandeep Sharma. Improved speed and scaling in orbital space variational monte carlo. Journal of chemical theory and computation, 14 (12): 6276–6286, 2018. https:/​/​doi.org/​10.1021/​acs.jctc.8b00780.

[43] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physics, 3 (9): 625–644, 2021b. https:/​/​doi.org/​10.1038/​s42254-021-00348-9.

[44] Panagiotis Kl Barkoutsos, Jerome F Gonthier, Igor Sokolov, Nikolaj Moll, Gian Salis, Andreas Fuhrer, Marc Ganzhorn, Daniel J Egger, Matthias Troyer, Antonio Mezzacapo, et al. Quantum algorithms for electronic structure calculations: Particle-hole hamiltonian and optimized wave-function expansions. Physical Review A, 98 (2): 022322, 2018. https:/​/​doi.org/​10.1103/​PhysRevA.98.022322.

[45] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16 (10): 1050–1057, 2020. https:/​/​doi.org/​10.1038/​s41567-020-0932-7.

[46] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002. https:/​/​doi.org/​10.1090/​conm/​305/​05215.

[47] Artur K Ekert, Carolina Moura Alves, Daniel KL Oi, Michał Horodecki, Paweł Horodecki, and Leong Chuan Kwek. Direct estimations of linear and nonlinear functionals of a quantum state. Physical review letters, 88 (21): 217901, 2002. https:/​/​doi.org/​10.1103/​PhysRevLett.88.217901.

[48] Sirui Lu, Mari Carmen Bañuls, and J Ignacio Cirac. Algorithms for quantum simulation at finite energies. PRX Quantum, 2 (2): 020321, 2021. https:/​/​doi.org/​10.1103/​PRXQuantum.2.020321.

[49] Thomas E O’Brien, Stefano Polla, Nicholas C Rubin, William J Huggins, Sam McArdle, Sergio Boixo, Jarrod R McClean, and Ryan Babbush. Error mitigation via verified phase estimation. PRX Quantum, 2 (2): 020317, 2021. https:/​/​doi.org/​10.1103/​PRXQuantum.2.020317.

[50] Ian D Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush. Quantum simulation of electronic structure with linear depth and connectivity. Physical review letters, 120 (11): 110501, 2018. https:/​/​doi.org/​10.1103/​PhysRevLett.120.110501.

[51] Arne L. Grimsmo, Joshua Combes, and Ben Q. Baragiola. Quantum computing with rotation-symmetric bosonic codes. Phys. Rev. X, 10: 011058, Mar 2020. https:/​/​doi.org/​10.1103/​PhysRevX.10.011058.

[52] Zhenyu Cai. Quantum error mitigation using symmetry expansion. Quantum, 5: 548, 2021. https:/​/​doi.org/​10.22331/​q-2021-09-21-548.

[53] Taisuke Ozaki. O (n) krylov-subspace method for large-scale ab initio electronic structure calculations. Physical Review B, 74 (24): 245101, 2006. https:/​/​doi.org/​10.1103/​PhysRevB.74.245101.

[54] Ken M Nakanishi, Kosuke Mitarai, and Keisuke Fujii. Subspace-search variational quantum eigensolver for excited states. Physical Review Research, 1 (3): 033062, 2019. https:/​/​doi.org/​10.1103/​PhysRevResearch.1.033062.

[55] Kazuhiro Seki and Seiji Yunoki. Quantum power method by a superposition of time-evolved states. PRX Quantum, 2 (1): 010333, 2021. https:/​/​doi.org/​10.1103/​PRXQuantum.2.010333.

[56] Cristian L Cortes and Stephen K Gray. Quantum krylov subspace algorithms for ground-and excited-state energy estimation. Physical Review A, 105 (2): 022417, 2022. https:/​/​doi.org/​10.1103/​PhysRevA.105.022417.

[57] Rongxin Xia and Sabre Kais. Qubit coupled cluster singles and doubles variational quantum eigensolver ansatz for electronic structure calculations. Quantum Science and Technology, 6 (1): 015001, 2020. https:/​/​doi.org/​10.1088/​2058-9565/​abbc74.

[58] Timo Felser, Simone Notarnicola, and Simone Montangero. Efficient tensor network ansatz for high-dimensional quantum many-body problems. Physical Review Letters, 126 (17): 170603, 2021. https:/​/​doi.org/​10.1103/​PhysRevLett.126.170603.

[59] Michael R Wall and Daniel Neuhauser. Extraction, through filter-diagonalization, of general quantum eigenvalues or classical normal mode frequencies from a small number of residues or a short-time segment of a signal. i. theory and application to a quantum-dynamics model. The Journal of chemical physics, 102 (20): 8011–8022, 1995. https:/​/​doi.org/​10.1063/​1.468999.

[60] Ethan N. Epperly, Lin Lin, and Yuji Nakatsukasa. A theory of quantum subspace diagonalization. SIAM Journal on Matrix Analysis and Applications, 43 (3): 1263–1290, 2022. https:/​/​doi.org/​10.1137/​21M145954X.

Cited by

[1] Jinzhao Sun, Suguru Endo, Huiping Lin, Patrick Hayden, Vlatko Vedral, and Xiao Yuan, "Perturbative Quantum Simulation", Physical Review Letters 129 12, 120505 (2022).

[2] Guglielmo Mazzola, "Quantum computing for chemistry and physics applications from a Monte Carlo perspective", arXiv:2308.07964, (2023).

[3] Yukun Zhang, Yifei Huang, Jinzhao Sun, Dingshun Lv, and Xiao Yuan, "Quantum Computing Quantum Monte Carlo", arXiv:2206.10431, (2022).

[4] Shu Kanno, Hajime Nakamura, Takao Kobayashi, Shigeki Gocho, Miho Hatanaka, Naoki Yamamoto, and Qi Gao, "Quantum computing quantum Monte Carlo with hybrid tensor network toward electronic structure calculations of large-scale molecular and solid systems", arXiv:2303.18095, (2023).

[5] Maximilian Amsler, Peter Deglmann, Matthias Degroote, Michael P. Kaicher, Matthew Kiser, Michael Kühn, Chandan Kumar, Andreas Maier, Georgy Samsonidze, Anna Schroeder, Michael Streif, Davide Vodola, and Christopher Wever, "Quantum-enhanced quantum Monte Carlo: an industrial view", arXiv:2301.11838, (2023).

[6] Benchen Huang, Nan Sheng, Marco Govoni, and Giulia Galli, "Quantum simulations of Fermionic Hamiltonians with efficient encoding and ansatz schemes", arXiv:2212.01912, (2022).

[7] Yongdan Yang, Ying Li, Xiaosi Xu, and Xiao Yuan, "A resource-efficient quantum-classical hybrid algorithm for energy gap evaluation", arXiv:2305.07382, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-09-22 20:12:56). 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 2023-09-22 20:12:54).