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:1703.10141 · Europhysics Letters (EPL)

Polynomial complexity despite the fermionic sign

Riccardo Rossi, Nikolay V. Prokof'ev, Boris V. Svistunov, Kris Van Houcke, Félix Werner

Published Apr 1, 2017• 44 citations
arXivHTMLPDF

Abstract

It is commonly believed that in quantum Monte Carlo approaches to fermionic many- body problems, the infamous sign problem generically implies prohibitively large computational times for obtaining thermodynamic-limit quantities. We point out that for convergent Feynman diagrammatic series evaluated with the Monte Carlo algorithm of [Rossi, arXiv:1612.05184], the computational time increases only polynomially with the inverse error on thermodynamic-limit quantities.

DOI
10.1209/0295-5075/118/10004

Related papers

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,250 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•7 citations

A Generic Solution of Fermion Sign Problem

J. Wang, D. Y. Sun

The fermion sign problem, the biggest obstacle in quantum Monte Carlo calculations, is completely solved in this paper. Here, we find a strategy, in which the contribution from those negative-weighted paths is thoroughly cancelled or replaced by some positive-weighted paths. The crucial point lies on the Feynman path integral formula proposed in our group, which allows us to deeply analyze the Boltzmann weight of each path. Through mathematical proof, we demonstrate that physical quantities can be exactly calculated within a specific kind of paths, which have positive the Boltzmann weight. With this finding, a new Monte Carlo method is proposed, in which the fermion sign problem is absent. As an example, the current method is applied to the two-dimensional Hubbard model, and the results do manifest the correctness.

arXiv:2203.04070•Mar 8, 2022•0 citations

Easing the Monte Carlo sign problem

Dominik Hangleiter, Ingo Roth, Daniel Nagaj +1 more

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.

arXiv:1906.02309•Science Advances•Aug 14, 2020•86 citations

Bold Diagrammatic Monte Carlo Technique: When the Sign Problem Is Welcome

Nikolay V. Prokof'ev, Boris V. Svistunov

We introduce a Monte Carlo scheme for sampling a bold-line diagrammatic series specifying an unknown function in terms of itself. The range of convergence of this bold(-line) diagrammatic Monte Carlo (BMC) technique is significantly broader than that of a simple iterative scheme for solving integral equations. With the BMC technique, a moderate "sign problem" turns out to be an advantage in terms of the convergence of the process. For an illustrative purpose, we solve the one-particle s-scattering problem. As an important application, we obtain the T matrix for a Fermi polaron (one spin-down particle interacting with the spin-up fermionic sea).

arXiv:cond-mat/0702555•Physical Review Letters•Dec 18, 2007•147 citations

Determinant Diagrammatic Monte Carlo Algorithm in the Thermodynamic Limit

Riccardo Rossi

We present a simple trick that allows us to consider the sum of all connected Feynman diagrams at fixed position of interaction vertices for general fermionic models, such that the thermodynamic limit can be taken analytically. With our approach one can achieve superior performance compared to conventional diagrammatic Monte Carlo algorithm, while rendering the algorithmic part dramatically simpler. By considering the sum of all connected diagrams at once, we allow for massive cancellations between different diagrams, greatly reducing the sign problem. In the end, the computational effort increases only exponentially with the order of the expansion, which should be contrasted with the factorial growth of the standard diagrammatic technique. We illustrate the efficiency of the technique for the two-dimensional Fermi-Hubbard model.

arXiv:1612.05184•Physical Review Letters•Jul 25, 2017•110 citations
It is commonly believed that in quantum Monte Carlo approaches to fermionic many- body problems, the infamous sign problem generically implies prohibitively large computational times for obtaining thermodynamic-limit quantities. We point out that for convergent Feynman diagrammatic series evaluated with the Monte Carlo algorithm of [Rossi, arXiv:1612.05184], the computational time increases only polynomially with the inverse error on thermodynamic-limit quantities.
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.
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 fermion sign problem, the biggest obstacle in quantum Monte Carlo calculations, is completely solved in this paper. Here, we find a strategy, in which the contribution from those negative-weighted paths is thoroughly cancelled or replaced by some positive-weighted paths. The crucial point lies on the Feynman path integral formula proposed in our group, which allows us to deeply analyze the Boltzmann weight of each path. Through mathematical proof, we demonstrate that physical quantities can be exactly calculated within a specific kind of paths, which have positive the Boltzmann weight. With this finding, a new Monte Carlo method is proposed, in which the fermion sign problem is absent. As an example, the current method is applied to the two-dimensional Hubbard model, and the results do manifest the correctness.
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.
We introduce a Monte Carlo scheme for sampling a bold-line diagrammatic series specifying an unknown function in terms of itself. The range of convergence of this bold(-line) diagrammatic Monte Carlo (BMC) technique is significantly broader than that of a simple iterative scheme for solving integral equations. With the BMC technique, a moderate "sign problem" turns out to be an advantage in terms of the convergence of the process. For an illustrative purpose, we solve the one-particle s-scattering problem. As an important application, we obtain the T matrix for a Fermi polaron (one spin-down particle interacting with the spin-up fermionic sea).
We present a simple trick that allows us to consider the sum of all connected Feynman diagrams at fixed position of interaction vertices for general fermionic models, such that the thermodynamic limit can be taken analytically. With our approach one can achieve superior performance compared to conventional diagrammatic Monte Carlo algorithm, while rendering the algorithmic part dramatically simpler. By considering the sum of all connected diagrams at once, we allow for massive cancellations between different diagrams, greatly reducing the sign problem. In the end, the computational effort increases only exponentially with the order of the expansion, which should be contrasted with the factorial growth of the standard diagrammatic technique. We illustrate the efficiency of the technique for the two-dimensional Fermi-Hubbard model.