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:2208.13744

A Solution to the Sign Problem Using a Sum of Controlled Few-Fermions

Wei, David H.

Published Jun 8, 2022• 0 citations
arXivHTMLPDF

Abstract

A restricted path integral method is proposed to simulate a type of quantum system or Hamiltonian called a sum of controlled few-fermions on a classical computer using Monte Carlo without a numerical sign problem. Then a universality is proven to assert that any bounded-error quantum polynomial time (BQP) algorithm can be encoded into a sum of controlled few-fermions and simulated efficiently using classical Monte Carlo. Therefore, BQP is precisely the same as the class of bounded-error probabilistic polynomial time (BPP), namely, BPP = BQP.

DOI
10.48550/arxiv.2208.13744

Related papers

Monte Carlo Quantum Computing

Wei, David H.

It is shown that a class of separately frustration-free (SFF) Hamiltonians can be Monte Carlo simulated efficiently on a classical computing machine, because such an SFF Hamiltonian corresponds to a Gibbs wavefunction whose nodal structure is efficiently computable by solving a small subsystem associated with a low-dimensional configuration subspace. It is further demonstrated that SFF Hamiltonians can be designed to implement universal ground state quantum computation. The two results combined have effectively solved the notorious sign problem in Monte Carlo simulations, and proved that all bounded-error quantum polynomial time algorithms admit bounded-error probabilistic polynomial time simulations.

arXiv:2012.14523•Dec 28, 2020•1 citation

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

On Conditional Wiener Integrals and a Novel Approach to the Fermion Sign Problem

Warwick Michael Dumas

The path-integral formulation of nonrelativistic quantum mechanics was introduced by Feynman in 1948. The use of Path Integral Monte Carlo can be put on a rigorous footing using conditional Wiener integrals. This thesis addresses the topics both of numerical error and of Monte Carlo error.\nA piecewise constant numerical method which is of second order of accuracy for computing conditional Wiener integrals for a rather general class of sufficiently smooth functional is proposed. The method is based on simulation of Brownian bridges via the corresponding stochastic differential equations (SDEs) and on ideas of the weak-sense numerical integration of SDEs. A convergence theorem is proved. Special attention is paid to integral-type functionals. Results of some numerical experiments are presented.\nIn a further part of the research, the goal is to develop Monte Carlo methods for fermion simulations that are resistant to the explosion of variance which happens due to the fermion sign problem. A novel approach is developed which represents a radical departure from the current approaches. This is based on the principle of using a geometrical interpretation of the problem in order to find ways to maximize the negative covariance between the countersigned functional contributions. The fundamental connection between quantum exchange and the fermion sign problem is exploited. It is shown that this leads to a mathematical proof of the well-known exact solution to the sign problem for 1-dimensional fermion systems, and also to a novel exact solution in the case of a pair of 2-dimensional fermions.

•Jul 7, 2010•0 citations

Path Integral Monte Carlo Methods for Fermions

Ethan Brown

In general, Quantum Monte Carlo methods suffer from a sign problem when simulating fermionic systems. This causes the efficiency of a simulation to decrease exponentially with the number of particles and inverse temperature. To circumvent this issue, a nodal constraint is often implemented, restricting the Monte Carlo procedure from sampling paths that cause the many-body density matrix to change sign. Unfortunately, this high-dimensional nodal surface is not a priori known unless the system is exactly solvable, resulting in uncontrolled errors. We will discuss two possible routes to extend the applicability of finite-temperatue path integral Monte Carlo. First we extend the regime where signful simulations are possible through a novel permutation sampling scheme. Afterwards, we discuss a method to variationally improve the nodal surface by minimizing a free energy during simulation. Applications of these methods will include both free and interacting electron gases, concluding with discussion concerning extension to inhomogeneous systems.

•Jan 1, 2014•0 citations

Fermion ground state methods

James E. Gubernatis, Naoki Kawashima, Philipp Werner

In this chapter, we discuss the fixed-node and constrained-path Monte Carlo methods for computing the ground state properties of systems of interacting electrons. These methods are arguably the two most powerful ones presently available for doing such calculations, but they are approximate. By sacrificing exactness, they avoid the exponential scaling of the Monte Carlo errors with system size that typically accompanies the simulation of systems of interacting electrons. This exponential scaling is called the Fermion sign problem . After a few general comments about the sign problem, we outline both methods, noting points of similarity and difference, plus points of strength and weakness. We also discuss the constrained-phase method, an extension of the constrained-path method, which controls the phase problem that develops when the ground state wave function cannot be real. Sign problem The “sign problem” refers to the exponential increase of the Monte Carlo errors with increasing system size or decreasing temperature (e.g., Loh et al., 1990, 2005; Gubernatis and Zhang, 1994) that often accompanies a Markov chain simulation whose limiting distribution is not everywhere positive. Such a case generally arises in simulations of Fermion and frustrated quantum-spin systems. It seems so inherent to Monte Carlo simulations of Fermion systems that the phrase “the sign problem” to many seems almost synonymous with the phrase “the Fermion sign problem.” Explanations for the cause of the sign problem vary and are still debated. In this chapter, we choose to summarize two explanations that seem to connect the causes in ground state Fermion simulations in the continuum and on the lattice. The sign problem, of course, is not limited to ground state calculations or even to Fermion simulations. While the cause we discuss in Sections 11.2 and 11.3 focuses on the low-lying states of diffusion-like operators, several topological pictures have been proposed (Muramatsu et al., 1992; Samson, 1993; Gubernatis and Zhang, 1994; Samson, 1995). Some of these discussions are done in the context of the zero- and finite-temperature determinant methods (Muramatsu et al., 1992; Gubernatis and Zhang, 1994). Others are done more analytically from a Feynman path-integral point of view (Samson, 1993, 1995). Some are for particles with statistics other than Fermions. The presentation of the sign problem in this chapter is appropriate for the Monte Carlo methods discussed in this chapter.

Cambridge University Press eBooks•Jan 31, 2016•0 citations

Multilevel algorithm for quantum-impurity models

Jaebeom Yoo, Shailesh Chandrasekharan A, Harold U. Baranger

A continuous-time path integral quantum Monte Carlo method using the directed-loop algorithm is developed to simulate the Anderson single-impurity model in the occupation number basis. Although the method suffers from a sign problem at low temperatures, the new algorithm has many advantages over conventional algorithms. For example, the model can be easily simulated in the Kondo limit without time discretization errors. Furthermore, many observables including the impurity susceptibility and a variety of fermionic observables can be calculated efficiently. Finally the new approach allows us to explore a general technique, called the multilevel algorithm, to solve the sign problem. We find that the multilevel algorithm is able to generate an exponentially large number of configurations with an effort that grows as a polynomial in inverse temperature such that configurations with a positive sign dominate over those with negative signs. Our algorithm can be easily generalized to other multi-impurity problems.

arXiv:cond-mat/0408123•Physical Review E•Mar 31, 2005•3 citations
A restricted path integral method is proposed to simulate a type of quantum system or Hamiltonian called a sum of controlled few-fermions on a classical computer using Monte Carlo without a numerical sign problem. Then a universality is proven to assert that any bounded-error quantum polynomial time (BQP) algorithm can be encoded into a sum of controlled few-fermions and simulated efficiently using classical Monte Carlo. Therefore, BQP is precisely the same as the class of bounded-error probabilistic polynomial time (BPP), namely, BPP = BQP.
It is shown that a class of separately frustration-free (SFF) Hamiltonians can be Monte Carlo simulated efficiently on a classical computing machine, because such an SFF Hamiltonian corresponds to a Gibbs wavefunction whose nodal structure is efficiently computable by solving a small subsystem associated with a low-dimensional configuration subspace. It is further demonstrated that SFF Hamiltonians can be designed to implement universal ground state quantum computation. The two results combined have effectively solved the notorious sign problem in Monte Carlo simulations, and proved that all bounded-error quantum polynomial time algorithms admit bounded-error probabilistic polynomial time simulations.
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 path-integral formulation of nonrelativistic quantum mechanics was introduced by Feynman in 1948. The use of Path Integral Monte Carlo can be put on a rigorous footing using conditional Wiener integrals. This thesis addresses the topics both of numerical error and of Monte Carlo error.\nA piecewise constant numerical method which is of second order of accuracy for computing conditional Wiener integrals for a rather general class of sufficiently smooth functional is proposed. The method is based on simulation of Brownian bridges via the corresponding stochastic differential equations (SDEs) and on ideas of the weak-sense numerical integration of SDEs. A convergence theorem is proved. Special attention is paid to integral-type functionals. Results of some numerical experiments are presented.\nIn a further part of the research, the goal is to develop Monte Carlo methods for fermion simulations that are resistant to the explosion of variance which happens due to the fermion sign problem. A novel approach is developed which represents a radical departure from the current approaches. This is based on the principle of using a geometrical interpretation of the problem in order to find ways to maximize the negative covariance between the countersigned functional contributions. The fundamental connection between quantum exchange and the fermion sign problem is exploited. It is shown that this leads to a mathematical proof of the well-known exact solution to the sign problem for 1-dimensional fermion systems, and also to a novel exact solution in the case of a pair of 2-dimensional fermions.
In general, Quantum Monte Carlo methods suffer from a sign problem when simulating fermionic systems. This causes the efficiency of a simulation to decrease exponentially with the number of particles and inverse temperature. To circumvent this issue, a nodal constraint is often implemented, restricting the Monte Carlo procedure from sampling paths that cause the many-body density matrix to change sign. Unfortunately, this high-dimensional nodal surface is not a priori known unless the system is exactly solvable, resulting in uncontrolled errors. We will discuss two possible routes to extend the applicability of finite-temperatue path integral Monte Carlo. First we extend the regime where signful simulations are possible through a novel permutation sampling scheme. Afterwards, we discuss a method to variationally improve the nodal surface by minimizing a free energy during simulation. Applications of these methods will include both free and interacting electron gases, concluding with discussion concerning extension to inhomogeneous systems.
In this chapter, we discuss the fixed-node and constrained-path Monte Carlo methods for computing the ground state properties of systems of interacting electrons. These methods are arguably the two most powerful ones presently available for doing such calculations, but they are approximate. By sacrificing exactness, they avoid the exponential scaling of the Monte Carlo errors with system size that typically accompanies the simulation of systems of interacting electrons. This exponential scaling is called the Fermion sign problem . After a few general comments about the sign problem, we outline both methods, noting points of similarity and difference, plus points of strength and weakness. We also discuss the constrained-phase method, an extension of the constrained-path method, which controls the phase problem that develops when the ground state wave function cannot be real. Sign problem The “sign problem” refers to the exponential increase of the Monte Carlo errors with increasing system size or decreasing temperature (e.g., Loh et al., 1990, 2005; Gubernatis and Zhang, 1994) that often accompanies a Markov chain simulation whose limiting distribution is not everywhere positive. Such a case generally arises in simulations of Fermion and frustrated quantum-spin systems. It seems so inherent to Monte Carlo simulations of Fermion systems that the phrase “the sign problem” to many seems almost synonymous with the phrase “the Fermion sign problem.” Explanations for the cause of the sign problem vary and are still debated. In this chapter, we choose to summarize two explanations that seem to connect the causes in ground state Fermion simulations in the continuum and on the lattice. The sign problem, of course, is not limited to ground state calculations or even to Fermion simulations. While the cause we discuss in Sections 11.2 and 11.3 focuses on the low-lying states of diffusion-like operators, several topological pictures have been proposed (Muramatsu et al., 1992; Samson, 1993; Gubernatis and Zhang, 1994; Samson, 1995). Some of these discussions are done in the context of the zero- and finite-temperature determinant methods (Muramatsu et al., 1992; Gubernatis and Zhang, 1994). Others are done more analytically from a Feynman path-integral point of view (Samson, 1993, 1995). Some are for particles with statistics other than Fermions. The presentation of the sign problem in this chapter is appropriate for the Monte Carlo methods discussed in this chapter.
A continuous-time path integral quantum Monte Carlo method using the directed-loop algorithm is developed to simulate the Anderson single-impurity model in the occupation number basis. Although the method suffers from a sign problem at low temperatures, the new algorithm has many advantages over conventional algorithms. For example, the model can be easily simulated in the Kondo limit without time discretization errors. Furthermore, many observables including the impurity susceptibility and a variety of fermionic observables can be calculated efficiently. Finally the new approach allows us to explore a general technique, called the multilevel algorithm, to solve the sign problem. We find that the multilevel algorithm is able to generate an exponentially large number of configurations with an effort that grows as a polynomial in inverse temperature such that configurations with a positive sign dominate over those with negative signs. Our algorithm can be easily generalized to other multi-impurity problems.