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.
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.
Building on a recent investigation of the Shastry-Sutherland model [S. Wessel et al., Phys. Rev. B 98, 174432 (2018)], we develop a general strategy to eliminate the Monte Carlo sign problem near the zero-temperature limit in frustrated quantum spin models. If the Hamiltonian of interest and the sign-problem-free Hamiltonian, obtained by making all off-diagonal elements negative in a given basis, have the same ground state and this state is a member of the computational basis, then the average sign returns to one as the temperature goes to zero. We illustrate this technique by studying the triangular and kagome lattice Heisenberg antiferrromagnet in a magnetic field above saturation, as well as the Heisenberg antiferromagnet on a modified Husimi cactus in the dimer basis. We also provide detailed Appendices on using linear programming techniques to automatically generate efficient directed loop updates in quantum Monte Carlo simulations.
The sign problem remains a major obstacle to extending the success of Monte Carlo methods to generic quantum many-body systems. A powerful alternative relies on cluster expansions, which provide convergent representations of free energies and related quantities, with applications ranging from tensor network contractions to quantum dynamics and circuits. Within their convergence regime, these expansions often yield deterministic polynomial-time algorithms. However, such methods require exhaustive enumeration of connected clusters, leading to a computational overhead of (Nε−1)O(logΔ), where N is the system size, ε the desired precision, and Δ the interaction-graph degree. This becomes particularly severe in long-range systems, where Δ≡N, resulting in quasi-polynomial runtimes. Here, we introduce a Markov chain algorithm that samples cluster expansions directly in the space of connected clusters, replacing deterministic enumeration by Monte Carlo sampling. Because sampling occurs in an abstract cluster space rather than a physical configuration space, the conventional exponential sign problem is absent within the convergence regime. For general polymer models, we establish an FPRAS with runtime O~(N4ε−3). For quantum partition functions at temperatures β≤βsampling≡O(1), this improves to O~(N3+1/Dε−3), where D is the lattice dimension. The framework directly applies to long-range quantum systems with interactions ∝1/rα, including 2-local models with α>2D.
When one tries to simulate quantum spin systems by the Monte Carlo method, often the ``minus-sign problem'' is encountered. In such a case, an application of probabilistic methods is not possible. In this paper, the method has been proposed which allows to avoid the minus-sign problem for certain class of frustrated Heisenberg models. The systems where this method is applicable are, for instance, the pyrochlore lattice and the ${J}_{1}\ensuremath{-}{J}_{2}$ Heisenberg model. The method works in singlet sector. It relies on the expression of wave functions in dimer (pseudo)basis and writing down the Hamiltonian as a sum over plaquettes. In such a formulation, matrix elements of the exponent of Hamiltonian are positive.
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.
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.