Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2010.00949 · npj Quantum Information

Sign-problem free quantum stochastic series expansion algorithm on a quantum computer

Kok Chuan Tan, Dhiman Bhowmick, Pinaki Sengupta

Published Apr 26, 2022• 16 citations
arXivHTMLPDF

Abstract

Abstract A quantum implementation of the Stochastic Series Expansion (SSE) Monte Carlo method is proposed, and is shown to offer significant advantages over classical implementations of SSE. In particular, for problems where classical SSE encounters the sign problem, the cost of implementing a Monte Carlo iteration scales only linearly with system size in quantum SSE, while it may scale exponentially with system size in classical SSE. In cases where classical SSE can be efficiently implemented, quantum SSE still offers an advantage by allowing for more general observables to be measured.

DOI
10.1038/s41534-022-00555-x

Related papers

Accessing the dynamics of large many-particle systems using the stochastic series expansion

Ansgar Dorneich, Matthias Troyer

The stochastic series expansion (SSE) method is a quantum Monte Carlo (QMC) technique working directly in the imaginary time continuum and thus avoiding "Trotter discretization" errors. Using a nonlocal "operator-loop update," it allows one to treat large quantum mechanical systems of many thousand sites. In this paper we first give a comprehensive review on SSE and present benchmark calculations of SSE scaling behavior with system size and inverse temperature, and compare it to the loop algorithm, whose scaling is known to be one of the best of all QMC methods. Finally we introduce an efficient algorithm to measure Green's functions and thus dynamical properties within SSE.

arXiv:cond-mat/0106471•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 20, 2001•111 citations

Mitigating the sign problem by quantum computing

Kwai-Kong Ng, Min-Fong Yang

The notorious sign problem severely limits the applicability of quantum Monte Carlo (QMC) simulations, as statistical errors grow exponentially with system size and inverse temperature. A recent proposal of a quantum-computing stochastic series expansion (qc-SSE) method suggested that the problem could be avoided by introducing constant energy shifts into the Hamiltonian. Here we critically examine this framework and show that it does not strictly resolve the sign problem for Hamiltonians with non-commuting terms. Instead, it provides a practical mitigation strategy that suppresses the occurrence of negative weights. Using the antiferromagnetic anisotropic XY chain as a test case, we analyze the dependence of the average sign on system size, temperature, anisotropy, and shift parameters. An operator contraction method is introduced to improve efficiency. Our results demonstrate that moderate shifts optimally balance sign mitigation and statistical accuracy, while large shifts amplify errors, leaving the sign problem unresolved but alleviated.

arXiv:2509.13017•Physical Review A•Feb 25, 2026•0 citations

Stochastic Series Expansion Methods

Anders W. Sandvik

The Stochastic Series Expansion (SSE) technique is a quantum Monte Carlo method that is especially efficient for many quantum spin systems and boson models. It was the first generic method free from the discretization errors affecting previous path integral based approaches. These lecture notes give a brief overview of the SSE method and its applications. In the introductory section, the representation of quantum statistical mechanics by the power series expansion of ${\rm e}^{-βH}$ will be compared with path integrals in discrete and continuous imaginary time. Extensions of the SSE approach to ground state projection and quantum annealing in imaginary time will also be briefly discussed. The later sections introduce efficient sampling schemes (loop and cluster updates) that have been developed for many classes of models. A summary of generic forms of estimators for important observables are also given. Applications are discussed in the last section.

arXiv:1909.10591•Sep 23, 2019•61 citations

Monte Carlo simulation methods for quantum mechanical systems

Robert Achleitner

This thesis work deals with Monte Carlo (MC) simulations with the focus on quantum mechanical systems. I start with an introduction about Monte-Carlo methods in general and their application to the classical Ising model. The second, most important part deals with the problem in quantum mechanics, and presents a possible simulation method, the Stochastic Series Expansion (SSE). I give an introduction about the idea behind that method and give some results obtained for simulations for finite spin chains. All programming was performed in FORTRAN.

•May 1, 2008•0 citations

Signal-to-noise problems in fault-tolerant quantum computation

Hyunwoo Oh

Quantum computation offers a promising alternative to classical Monte Carlo methods by naturally avoiding sign problems through unitary evolution. A common misconception follows from this: because quantum simulation sidesteps the sign problem, it is often assumed to be an essentially perfect substitute for classical sampling. This is false---quantum measurements are intrinsically stochastic, and estimating observables often requires a number of samples that grows exponentially with system size, time separation, or inverse temperature, exactly as in the classical signal-to-noise problem. In this work, we analyze the origin and structure of signal-to-noise problems in quantum computation, drawing parallels with classical Monte Carlo, and demonstrate that such noise persists even in sign-problem-free regimes. We discuss strategies to mitigate it, in particular a quantum generalization of Stein control variates construction, in which unbiased estimators are built from operator commutators $[X,A]$ and their discrete diagonal counterparts, and validate the approach with exactly solvable numerical examples that quantify the achievable variance reduction. Our results underscore that variance reduction, not merely sign-problem avoidance, is required to make quantum algorithms practically viable for many-body physics.

quant-pharXiv:2610.15210•Oct 13, 2026•0 citations

Sign Problem in Quantum Monte Carlo Simulation

Gaopei Pan, Zi Yang Meng

Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.

arXiv:2204.08777•Apr 19, 2022•42 citations
Abstract A quantum implementation of the Stochastic Series Expansion (SSE) Monte Carlo method is proposed, and is shown to offer significant advantages over classical implementations of SSE. In particular, for problems where classical SSE encounters the sign problem, the cost of implementing a Monte Carlo iteration scales only linearly with system size in quantum SSE, while it may scale exponentially with system size in classical SSE. In cases where classical SSE can be efficiently implemented, quantum SSE still offers an advantage by allowing for more general observables to be measured.
The stochastic series expansion (SSE) method is a quantum Monte Carlo (QMC) technique working directly in the imaginary time continuum and thus avoiding "Trotter discretization" errors. Using a nonlocal "operator-loop update," it allows one to treat large quantum mechanical systems of many thousand sites. In this paper we first give a comprehensive review on SSE and present benchmark calculations of SSE scaling behavior with system size and inverse temperature, and compare it to the loop algorithm, whose scaling is known to be one of the best of all QMC methods. Finally we introduce an efficient algorithm to measure Green's functions and thus dynamical properties within SSE.
The notorious sign problem severely limits the applicability of quantum Monte Carlo (QMC) simulations, as statistical errors grow exponentially with system size and inverse temperature. A recent proposal of a quantum-computing stochastic series expansion (qc-SSE) method suggested that the problem could be avoided by introducing constant energy shifts into the Hamiltonian. Here we critically examine this framework and show that it does not strictly resolve the sign problem for Hamiltonians with non-commuting terms. Instead, it provides a practical mitigation strategy that suppresses the occurrence of negative weights. Using the antiferromagnetic anisotropic XY chain as a test case, we analyze the dependence of the average sign on system size, temperature, anisotropy, and shift parameters. An operator contraction method is introduced to improve efficiency. Our results demonstrate that moderate shifts optimally balance sign mitigation and statistical accuracy, while large shifts amplify errors, leaving the sign problem unresolved but alleviated.
The Stochastic Series Expansion (SSE) technique is a quantum Monte Carlo method that is especially efficient for many quantum spin systems and boson models. It was the first generic method free from the discretization errors affecting previous path integral based approaches. These lecture notes give a brief overview of the SSE method and its applications. In the introductory section, the representation of quantum statistical mechanics by the power series expansion of e−βH{\rm e}^{-βH}e−βH will be compared with path integrals in discrete and continuous imaginary time. Extensions of the SSE approach to ground state projection and quantum annealing in imaginary time will also be briefly discussed. The later sections introduce efficient sampling schemes (loop and cluster updates) that have been developed for many classes of models. A summary of generic forms of estimators for important observables are also given. Applications are discussed in the last section.
This thesis work deals with Monte Carlo (MC) simulations with the focus on quantum mechanical systems. I start with an introduction about Monte-Carlo methods in general and their application to the classical Ising model. The second, most important part deals with the problem in quantum mechanics, and presents a possible simulation method, the Stochastic Series Expansion (SSE). I give an introduction about the idea behind that method and give some results obtained for simulations for finite spin chains. All programming was performed in FORTRAN.
Quantum computation offers a promising alternative to classical Monte Carlo methods by naturally avoiding sign problems through unitary evolution. A common misconception follows from this: because quantum simulation sidesteps the sign problem, it is often assumed to be an essentially perfect substitute for classical sampling. This is false---quantum measurements are intrinsically stochastic, and estimating observables often requires a number of samples that grows exponentially with system size, time separation, or inverse temperature, exactly as in the classical signal-to-noise problem. In this work, we analyze the origin and structure of signal-to-noise problems in quantum computation, drawing parallels with classical Monte Carlo, and demonstrate that such noise persists even in sign-problem-free regimes. We discuss strategies to mitigate it, in particular a quantum generalization of Stein control variates construction, in which unbiased estimators are built from operator commutators [X,A][X,A][X,A] and their discrete diagonal counterparts, and validate the approach with exactly solvable numerical examples that quantify the achievable variance reduction. Our results underscore that variance reduction, not merely sign-problem avoidance, is required to make quantum algorithms practically viable for many-body physics.
Sign problem in quantum Monte Carlo (QMC) simulation appears to be an extremely hard yet interesting problem. In this article, we present a pedagogical overview on the origin of the sign problem in various quantum Monte Carlo simulation techniques, ranging from the world-line and stochastic series expansion Monte Carlo for boson and spin systems to the determinant and momentum-space quantum Monte Carlo for interacting fermions. We point out the basis dependency of the sign problem and summarize the progresses to cure, ease and even make use of the sign problem over the years, such as symmetry analysis of the underlying Hamiltonian, basis optimization in writting down the partition functions and many others. Moreover, we state that although traditional lore saying that in case of sign problem, the average sign in QMC simulation approaches zero exponentially fast with the space-time volume of the configurational space, there are recent breakthroughs showing this is not always the case and based on the properties of the partition function for finite size systems, one could distinguish when the average sign has the usual exponential scaling and when it is bestowed with an algebraic scaling at the low temperature limit. Fermionic QMC simulations with such algebraic sign problems have been successfully carried out for extended Hubbard-type and quantum Moiré lattice models.