Although stoquastic Hamiltonians are known to be simulable via sign-problem-free quantum Monte Carlo (QMC) techniques, the nonstoquasticity of a Hamiltonian does not necessarily imply the existence of a QMC sign problem.We give a sufficient and necessary condition for the QMC-simulability of Hamiltonians in a given basis: We prove that a QMC simulation will be sign-problem-free if and only if all the overall total phases along the chordless cycles of the weighted graph whose adjacency matrix is the Hamiltonian are zero (modulo 2π ).We use our findings to provide a construction for nonstoquastic, yet sign-problem-free and hence QMC-simulable, quantum many-body models.We also demonstrate why the simulation of truly sign-problematic models using the QMC weights of the stoquasticized Hamiltonian is generally suboptimal.We offer a superior alternative.
Although stoquastic Hamiltonians are known to be simulable via sign-problem-free quantum Monte Carlo (QMC) techniques, the nonstoquasticity of a Hamiltonian does not necessarily imply the existence of a QMC sign problem.We give a sufficient and necessary condition for the QMC-simulability of Hamiltonians in a given basis: We prove that a QMC simulation will be sign-problem-free if and only if all the overall total phases along the chordless cycles of the weighted graph whose adjacency matrix is the Hamiltonian are zero (modulo 2π ).We use our findings to provide a construction for nonstoquastic, yet sign-problem-free and hence QMC-simulable, quantum many-body models.We also demonstrate why the simulation of truly sign-problematic models using the QMC weights of the stoquasticized Hamiltonian is generally suboptimal.We offer a superior alternative.
Quantum Monte Carlo (QMC) methods are powerful tools for simulating quantum many-body systems, yet their applicability is limited by the infamous sign problem. We approach this challenge through the lens of Vanishing Geometric Phases (VGP) \cite{Hen_2021}, introducing it as a `geometric' criterion for diagnosing QMC simulability. We characterize the class of VGP Hamiltonians, and analyze the complexity of recognizing this class, identifying both hard and efficiently identifiable cases. We further highlight the practical advantage of the VGP criterion by exhibiting specific Hamiltonians that are readily identified as sign-problem-free through VGP, yet whose stoquasticity is difficult to ascertain. These examples underscore the efficiency and sharpness of VGP as a diagnostic tool compared to stoquasticity-based heuristics. Beyond classification, we propose a family of VGP-inspired diagnostics that serve as quantitative indicators of sign problem severity. While exact evaluation of these quantities is generically intractable, we demonstrate their mathematical power in performing scaling analysis for the average sign under unitary transformations. Our results provide both a conceptual foundation and practical tools for understanding and mitigating the sign problem.
Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with 'curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.
Quantum Monte Carlo (QMC) methods are the gold standard for studying equilibrium properties of quantum many-body systems. However, in many interesting situations, QMC methods are faced with a sign problem, causing the severe limitation of an exponential increase in the runtime of the QMC algorithm. In this work, we develop a systematic, generally applicable, and practically feasible methodology for easing the sign problem by efficiently computable basis changes and use it to rigorously assess the sign problem. Our framework introduces measures of non-stoquasticity that-as we demonstrate analytically and numerically-at the same time provide a practically relevant and efficiently computable figure of merit for the severity of the sign problem. Complementing this pragmatic mindset, we prove that easing the sign problem in terms of those measures is generally an NP-complete task for nearest-neighbor Hamiltonians and simple basis choices by a reduction to the MAXCUT-problem.
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.
Quantum Monte Carlo (QMC) simulations involving fermions have a notorious sign problem. Some well-known exceptions to the auxiliary field QMC algorithm rely on the factorizibility of the fermion determinant. Recently, a fermionic QMC algorithm [C. Wu, J. Hu, and S. Zhang, Phys. Rev. Lett. 91, 186402 (2003)] has been found in which the fermion determinant may not necessarily be factorizable, but can instead be expressed as a product of complex conjugate pairs of eigenvalues, thus eliminating the sign problem for a much wider class of models. In this paper, we present the general conditions for the applicability of this algorithm and point out that it is deeply related to the time-reversal symmetry of the fermion matrix. We apply this method to various models of strongly correlated systems at all doping levels and lattice geometries, and show that many phases can be simulated without the sign problem.
The shell model provides a powerful framework for nuclear structure calculations. The nucleons beyond an inert magic core are confined in a valence shell and interact through an effective two-body potential generally determined from the G-matrix method. However, the applicability of the shell model remains limited by the exponential growth of the many-body space with the number of valence nucleons and with the size of the one-body space. The quantum Monte Carlo (QMC) methods may thus be considered as a potentially attractive alternative to the direct diagonalization of the Hamiltonian matrix. The many-body problem is indeed reduced to a set of stochastic one-body problems describing independent particles in a fluctuating external field. Up to date, the QMC approaches of the shell model lead to the ground-state and the thermodynamic properties, but a detailed spectroscopy of nuclei is not reachable. Furthermore, they suffer from a common pathology of fermionic QMC methods, namely the sign/phase problem, which strongly contaminates the convergence of the calculation. In this context, we will present a new QMC method, providing the "yrast spectroscopy" of nuclei, and in which the sign/phase problem is managed through the constrained path approximation that is widely used in the ab initio nuclear calculations and in condensed matter physics.