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:1907.02076 · Physical Review Letters

Mitigating the Sign Problem through Basis Rotations

Ryan Levy, Bryan K. Clark

Published May 24, 2021• 35 citations
arXivHTMLPDF

Abstract

Quantum Monte Carlo simulations of quantum many-body systems are plagued by the Fermion sign problem. The computational complexity of simulating Fermions scales exponentially in the projection time β and system size. The sign problem is basis dependent and an improved basis, for fixed errors, leads to exponentially quicker simulations. We show how to use sign-free quantum Monte Carlo simulations to optimize over the choice of basis on large two-dimensional systems. We numerically illustrate these techniques decreasing the "badness" of the sign problem by optimizing over single-particle basis rotations on one- and two-dimensional Hubbard systems. We find a generic rotation which improves the average sign of the Hubbard model for a wide range of U and densities for L×4 systems. In one example improvement, the average sign (and hence simulation cost at fixed accuracy) for the 16×4 Hubbard model at U/t=4 and n=0.75 increases by exp[8.64(6)β]. For typical projection times of β⪆100, this accelerates such simulation by many orders of magnitude.

DOI
10.1103/physrevlett.126.216401

Related papers

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

Alleviating the sign problem in quantum Monte Carlo simulations of spin-orbit-coupled multiorbital Hubbard models

Aaram J. Kim, Philipp Werner, Roser Valentí

We present a strategy to alleviate the sign problem in continuous-time quantum Monte Carlo (CTQMC) simulations of the dynamical-mean-field-theory (DMFT) equations for the spin-orbit-coupled multiorbital Hubbard model. We first identify the combinations of rotationally invariant Hund coupling terms present in the relativistic basis which lead to a severe sign problem. Exploiting the fact that the average sign in CTQMC depends on the choice of single-particle basis, we propose a bonding-antibonding basis ${V}_{j3/2\mathrm{BA}}$ which shows an improved average sign compared to the widely used relativistic basis for most parameter sets investigated. We then generalize this procedure by introducing a stochastic optimization algorithm that exploits the space of single-particle bases and show that ${V}_{j3/2\mathrm{BA}}$ is very close to optimal within the parameter space investigated. Our findings enable more efficient DMFT simulations of materials with strong spin-orbit coupling.

arXiv:1907.11298•Physical review. B./Physical review. B•Jan 9, 2020•27 citations

Local Basis Transformation to Mitigate Negative Sign Problems

Murota, Keisuke, Synge Todo

Quantum Monte Carlo (QMC) methods for the frustrated quantum spin systems occasionally suffer from the negative sign problem, which makes simulations exponentially harder for larger systems at lower temperatures and severely limits QMC's application across a wide range of spin systems. This problem is known to depend on the choice of representation basis. We propose a systematic approach for mitigating the sign problem independent of the given Hamiltonian or lattice structure. We first introduce the concept of negativity to characterize the severity of the negative sign problem. We then demonstrate the existence of a locally defined quantity, the L1 adaptive loss function, which effectively approximates negativity, especially in frustration-free systems. Using the proposed loss function, we demonstrate that optimizing the representation basis can mitigate the negative sign. This is evidenced by several frustration-free models and other important quantum spin systems. Furthermore, we compare the effectiveness of unitary transformations against the standard orthogonal transformation and reveal that unitary transformations can effectively mitigate the sign problem in certain cases.

arXiv:2501.18069•Jan 30, 2025•4 citations

Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations

Matthias Troyer, U.‐J. Wiese

Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.

arXiv:cond-mat/0408370•Physical Review Letters•May 4, 2005•1,396 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

Sign-optimized Quantum Monte Carlo

Julius S. Herz, Robin Schäfer, M. G. Gonzalez +1 more

The sign problem breaks the polynomial scaling of Quantum Monte Carlo methods. We alleviate it by rotation of the local basis of the Hilbert space, such that the phase of off-diagonal matrix elements of the rotated Hamiltonian is minimized. These minima coincide with optima of the average sign. We benchmark our method for frustrated Heisenberg antiferromagnets in one dimension and on the two-dimensional maple-leaf lattice. Our approach reveals more efficient bases with improved sign in a large part of the parameter space for all models considered, enabling us to reach lower temperatures, on par with state-of-the-art numerical linked cluster expansions which we directly compare to.

arXiv:2607.24679•Jul 27, 2026•1 citation
Quantum Monte Carlo simulations of quantum many-body systems are plagued by the Fermion sign problem. The computational complexity of simulating Fermions scales exponentially in the projection time β and system size. The sign problem is basis dependent and an improved basis, for fixed errors, leads to exponentially quicker simulations. We show how to use sign-free quantum Monte Carlo simulations to optimize over the choice of basis on large two-dimensional systems. We numerically illustrate these techniques decreasing the "badness" of the sign problem by optimizing over single-particle basis rotations on one- and two-dimensional Hubbard systems. We find a generic rotation which improves the average sign of the Hubbard model for a wide range of U and densities for L×4 systems. In one example improvement, the average sign (and hence simulation cost at fixed accuracy) for the 16×4 Hubbard model at U/t=4 and n=0.75 increases by exp[8.64(6)β]. For typical projection times of β⪆100, this accelerates such simulation by many orders of magnitude.
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.
We present a strategy to alleviate the sign problem in continuous-time quantum Monte Carlo (CTQMC) simulations of the dynamical-mean-field-theory (DMFT) equations for the spin-orbit-coupled multiorbital Hubbard model. We first identify the combinations of rotationally invariant Hund coupling terms present in the relativistic basis which lead to a severe sign problem. Exploiting the fact that the average sign in CTQMC depends on the choice of single-particle basis, we propose a bonding-antibonding basis Vj3/2BA{V}_{j3/2\mathrm{BA}}Vj3/2BA​ which shows an improved average sign compared to the widely used relativistic basis for most parameter sets investigated. We then generalize this procedure by introducing a stochastic optimization algorithm that exploits the space of single-particle bases and show that Vj3/2BA{V}_{j3/2\mathrm{BA}}Vj3/2BA​ is very close to optimal within the parameter space investigated. Our findings enable more efficient DMFT simulations of materials with strong spin-orbit coupling.
Quantum Monte Carlo (QMC) methods for the frustrated quantum spin systems occasionally suffer from the negative sign problem, which makes simulations exponentially harder for larger systems at lower temperatures and severely limits QMC's application across a wide range of spin systems. This problem is known to depend on the choice of representation basis. We propose a systematic approach for mitigating the sign problem independent of the given Hamiltonian or lattice structure. We first introduce the concept of negativity to characterize the severity of the negative sign problem. We then demonstrate the existence of a locally defined quantity, the L1 adaptive loss function, which effectively approximates negativity, especially in frustration-free systems. Using the proposed loss function, we demonstrate that optimizing the representation basis can mitigate the negative sign. This is evidenced by several frustration-free models and other important quantum spin systems. Furthermore, we compare the effectiveness of unitary transformations against the standard orthogonal transformation and reveal that unitary transformations can effectively mitigate the sign problem in certain cases.
Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem" when applied to fermions--causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time.
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 sign problem breaks the polynomial scaling of Quantum Monte Carlo methods. We alleviate it by rotation of the local basis of the Hilbert space, such that the phase of off-diagonal matrix elements of the rotated Hamiltonian is minimized. These minima coincide with optima of the average sign. We benchmark our method for frustrated Heisenberg antiferromagnets in one dimension and on the two-dimensional maple-leaf lattice. Our approach reveals more efficient bases with improved sign in a large part of the parameter space for all models considered, enabling us to reach lower temperatures, on par with state-of-the-art numerical linked cluster expansions which we directly compare to.