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.
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.
Quantum Monte Carlo and quantum simulation are both important tools for
understanding quantum many-body systems. As a classical algorithm, quantum
Monte Carlo suffers from the sign problem, preventing its applications to most
fermion systems and real-time dynamics. In contrast, on a quantum computer, we
can simulate time evolution of general systems with local interactions, yet
such algorithms usually require the development of fault-tolerant quantum
technologies. In this paper, we introduce a novel non-variational algorithm
using quantum computing as a subroutine to accelerate quantum Monte Carlo. On a
fault-tolerant quantum computer, the complexity of our algorithm is polynomial
as the same as conventional quantum simulation algorithms. On a noisy quantum
computer, our algorithm incorporating error mitigation eases the sign problem.
Even when the circuit noise is significant, our algorithm can reduce the Monte
Carlo variance by orders of magnitude.