One of the main difficulties for the Path Integral Monte Carlo (PIMC) simulation of the quantum systems of particles is the so called “sign problem”. The “sign problem” arises in the simulations of the Wigner and Feynman path integrals, describing quantum systems and the finite density quantum chromodynamics due to the fast oscillations of the integrand defined by the complex-valued action. This integrand does not give a real and positive Boltzmann-like weight (for example, by the Wick rotation) to resort to the traditional Monte Carlo methods. The so-called reweighting algorithm is highly ineffective when the imaginary part of the action becomes very large, because one needs to take a sample from a configuration space, where the weights of nearby configurations have almost the same amplitudes but very different phases.
There have been many proposals to circumvent the “sign problem”. Basic possible approach to this problem is to consider the variables, which are assumed to be real in the original formulation, to be complex and to extend the cycle of path-integration to a complex space in order to achieve better convergence.
So long under the typical physical conditions the integrand is holomorphic in the new complex variables and the final value of the path integral is unchanged by Cauchy’s theorem. Making use of the Picard-Lefschetz theory and a complex version of Morse theory we can select the cycle approaching the saddle point at the path-integration, where the imaginary part of the complex action stays constant (Lefschetz thimbles)   . Since the imaginary part of the action is constant on each thimble, the “sign problem” disappears and the integral can be calculated much more effectively.
However, since different thimbles are strongly separated, one needs to develop method allowing incorporating contributions from all relevant thimbles. One of the natural ways to incorporate the relevant thimbles   is to use a gradient flow of action starting from the original real space of integration and creating a new manifold at a finite flow time, which is equivalent to the integration over original real space. In particular, when the flow time approaches infinity, the new manifold is composed of Lefschetz thimbles. In practise, as long as the finite flow-time is large enough then the “sign problem” will be alleviated, as integrals turn into integrals of an oscillating function with decaying amplitude. However reducing the amount of flow time may also reduce the effectiveness against the “sign problem” and the multimodal problem simultaneously.
The alternative approach of sampling at calculation of the path-integrals on thimbles is based on the making use of the complexified Langevin equation   . Of course, application of the noise leads to departures from the thimble that accumulates and needs to be corrected. Numerically, this procedure can be made stable.
Besides, the Langevin algorithm, other algorithms have been proposed: an Hybrid Monte Carlo algorithm , that however is essentially as expensive as the Langevin algorithm; two Metropolis algorithms   that are simpler and faster, but have the risk of poor acceptance for large systems and an alternative algorithm  that ensures a control of the thimble at the price of limited scalability.
In this work we present the new Metropolis-Hastings algorithm for searching critical points and subsequent generation of the Lefschetz thimbles. The algorithm allows to find the saddle points and to sample initial conditions for downward flows from vicinity of the saddle points. The developed approach combines the basic ideas of the Metropolis and Hasting algorithms. So to increase efficiency of numerical procedure we have separated the Markovian transition on the complex plane in two sub-steps: the proposal and the acceptance-rejection. The proposal probability allows proposing a new state for given one. Here we are free in choosing proposing probability as it affects only the efficiency of the sampling the main contribution to the integrals and does not change the final result of calculations. The acceptance distribution is the conditional probability to accept/reject the proposed state.
The integrals involved in our test calculations are one variable integral and can be performed analytically or independent numerically. However, it provides an interesting benchmark which can be seen as a limiting case of more realistic path integrals. It is non-trivial from the point of view of a Monte Carlo integration. For comparison with analytical results we present some calculations for the Airy function and some results on the Fourier transform of basic 1D factors comprising the Wiener path integral representation of the Wigner function in phase space. It also provides a case where different aspects of our approach can be clearly visualized.
This paper is organized as follows. In Section 2 we remind the basic ideas of the Wigner formulation of quantum mechanics. Section 3 is devoted to the brief deriving the path integral representation of the Wigner function. In Section 4 we explain the basic ideas of the complexification of the variables in path integrals and introduce in complex-valued space of the path integration the manyfold approaching the saddle point, where the imaginary part of the path integral action is constant (Lefschetz thimble). Path integration on the thimble allows reducing the “sign problem”. In Section 5 we derive the Metropolis-Hasting algorithm allowing finding the saddle points in complex-valued space of integration. Vicinities of the saddle pints are used as initial conditions to generate the Lefschetz thimbles. Section 6 presents results of the test calculations for 1D case with known analytical answer. Conclusion of the work is given in Section 7.
2. Wigner Approach to Quantum Mechanics
We consider a one-dimensional quantum-mechanical system consisting of one particle in potential field . The Hamilton function of this system is
where p is the momentum of particle, q is its coordinate. Everywhere in this paper, we will assume that the potential field is analytical function. We assume that the system is in thermodynamic equilibrium with a thermostat. In other words, we consider a canonical ensemble with temperature T and volume V (V is one-dimensional).
The quantum canonical ensemble can be fully characterized by the Wigner function , which is essentially a density matrix in the mixed coordinate-momentum representation and defined as a Fourier transform of the density matrix:
where , is Hamiltonian, obtained from (1) by replacing by momentum and coordinate operators respectively. The Wigner function can be formally considered as quantum generalization of classical distribution function in the phase space. This interpretation is noncompletely correct, because may be non-positive. However momentum and coordinate distribution functions, as well as average values of physical quantities depending on p and q, can be obtained from the Wigner function in classical-like way:
where is so-called Weyl symbol of operator .
3. Path Integral Representation
In general case, the density matrix in (2) cannot be calculated directly, since the kinetic and potential energy operators in Hamiltonian are non-commutative, so the statistical operator does not split into and . Therefore, we use the following procedure, leading to representation of the density matrix in form of path integrals (Winer path integral form).
Firstly, the statistical operator should be represented as product of 2K operators , assuming that K is large number. Secondly, one should insert unit operators and replace each of them with completeness relation for states with a certain coordinate :
For large values of K, “high-temperature” statistical operators can be decomposed into the product of the operators and with accuracy . After this step,
corresponding matrix elements can be easily calculated, using the completeness relations for states with a certain momentum and the wave functions . Finally, we obtain the representation of the Wigner function in form of 2K-dimensional integral over variables , and :
Here we assume that . Parameter is small and tends to zero for ; while the formula becomes exact.
4. Basics of the Complexification on Lefschetz Thimbles
According to the Morse theory    the regions of integration over each real in the path integrals (5) is equivalent to the integration over complex valued set of Lefschetz thimbles which is homologically equivalent due to the Cauchy’s integral theorem to the integration on real cycle . Assuming that takes the complex values and the action is extended to a holomorphic function of q let us consider the set of critical points (saddle
points) , which satisfy condition . The real Morse function in our case can be defined as and the associate gradient (downward) flow equations are given by  :
The Morse function h is always strictly decreasing along a flow. Associated with a critical point , a Lefschetz thimble  is defined by the union of all downward flows, which trace back to at . Let us note that if equals a critical point at some l, then the flow equation implies that is constant for all l. So a non-constant flow can only reach a critical point at .
One can also introduce another submanifold of by the union of all upward flows, satisfying equation with opposite sign to Equation (6)   
which converge to at , so that its intersection number with is unity and vanishing otherwise, .
Strictly speaking this means that if is the solution of Equation (6) and for any positive (maybe very small) there exists the positive (maybe very large) that for all negative l such that we have . This allows in numerical simulation to use the following approximation. Due to the restrictions on computational time at solving Equation (6), (7) it is necessary to exclude the small vicinity of critical point, where the parameter . So in numerical simulations the staring points for downward flow have to be chosen outside of a small vicinity of and the averaging results of calculations by the Monte Carlo method can be done over ensemble of the downward flows related to decreasing small . Algorithm of this MC approach, sampling the main contribution in integrals like (5) will be discussed below.
Then, according to Morse theory   , it follows that
which holds in the homological sense. As consequence, for the critical points satisfying , , it holds that and the associated thimbles do not contribute to the path integration. On the other hand, it holds that if the associated thimbles contribute with the relative weights proportional to . Now, for example, the momentum distribution function Equation (3) can be given by the formula
5. Numerical Algorithm
To do simulations we are going to combine the Monte Carlo method (MC)   for searching the critical points and the finite-difference methods for solving Equation (6) with initial conditions obtained by MC method in the small vicinity of .
Used here MC method is based on the Metropolis-Hastings algorithm  , which resides in designing a Markov process (by constructing transition probabilities ), such that its stationary distribution to be equal to . The derivation of the algorithm starts with the condition of detailed balance:
which can be rewritten as
To increase efficiency of the numerical procedure we are going to separate the transition in two sub-steps: the proposal and the acceptance-rejection. The transition probability can be written as the product: . The proposal distribution is the conditional probability of proposing a state for given . The acceptance distribution is the conditional probability to accept the proposed state .
Inserting this relation in the previous equation, we have
Then it is necessary to choose an acceptance that fulfills detailed balance. One common choice is the Metropolis’s suggestion:
This means that we always accept when the acceptance is bigger than 1 and we can accept or reject when the acceptance is smaller than 1.
It is important to notice that it is not clear, in a general problem, which distribution one should use. It is a free parameter of the method which has to be adjusted to the particular problem “in hand”. The probability affects only the efficiency of sampling the main contribution to the integrals and does not change the final result of calculations. For optimization of the MC finding the main contribution to the integral (9) the choice of the may be the following with free appropriate fit parameter . To optimize the MC search of the critical points ( ) we define the probability as
with parameter . The ideal acceptance rate,
which is the fraction of proposed samples that is accepted during the last N samples, have to be in interval of 23% - 50%.
The Metropolis-Hastings algorithm consists in the following steps:
1) Initialization: pick an initial state point at random.
2) Randomly pick a state , according to probability .
3) Accept the state according to the probability . If not accepted, that means that , and so there is no need to update anything. Else, the system transits to .
4) Go to 2 until many M states were generated to “forget” initial and to obtain the average position of the critical point .
5) If carry out several iterations by complex-valued extension of the Newton’s method to produce better approximations to the roots (or zeroes) of the complex-valued function . Else go to 2.
6) Save the state .
7) At random pick an initial point at the small vicinity of the zero point of the complex-valued space (maybe in any given quarter).
8) Analogously randomly pick a new state according to the probability .
9) Go to 8 many times to “forget” initial state and to obtain the average value of the .
10) Solve equation for upward flow with initial conditions of to check if . If go to 11, otherwise go to 2.
11) Solve Equation (6) with initial conditions of until modulus of the integrand in (9) will be smaller of several order of magnitude of its initial value and calculate the integral sum related to (9).
12) Go to 2 many times and calculate the integrals (9).
Function (9) has be averaged over the set of downward flows-solutions of the Equation (6) with initial conditions provided by MC procedure from neighborhood of .
6. Results of Numerical Test Calculations
Before calculations of multidimensional integrals (5) we have to test the algorithm proposed above by calculations of some simpler integrals with known answer. It is reasonable to begin with consideration of low dimensional improper integrals of strongly oscillating functions.
6.1. The Airy Function
Let us consider a classic example: the Airy function is defined as the integral over the real axis and can be considered as a Fourier transform:
The integrand is strongly oscillating function on , which makes a direct numerical evaluation infeasible. The left plot of Figure 1 shows lines of the constant imaginary part of the power in exponent in (14) on complex plane, while increasing and lowering values are denoted by the red and blue regions. The critical points are in the left upper and the right bottom quarters of the complex plane. We can deform the integration path in the complex plane of variable , as long as the new path belongs to the original relative homology class, which connects regions of strongly decaying modulus of the integrand at infinity (blue regions on the centre plot of Figure 1). Right panel of this figure shows the contour plot of the MC probability with two red circles at its maximum values at the critical points.
Testing the proposed approach starts from finding critical points by suggested MC method. It turns out that the Markovian chain traveling on the whole complex plane always stabilizes in the vicinity of the critical point (point in the left upper quarter of the complex plane in Figure 1) ignoring the second critical point ( ) in the favoure of the first one. So to
Figure 1. (Color online) The contour plot of the imaginary part (left panel) and the real part (central panel) of the power in exponent in (14) on complex plane for . (Right plot) Contour plot of the probability .
force the Markovian chain to stabilize in the vicinity of the second critical point we have to use the special restrictions. Reason of this behavior of the Markovian chain is the asymmetry of the contour plots of the real and imaginary parts of the power in exponent in (14) (see Figure 1).
Solution of the complex valued differential Equations (6 and 7) with MC initial conditions nearby both critical points allow to obtain averaged downward (red lines) and upward (blue lines) flows (see both plots of Figure 2). Right plot of this figure shows in detail the downward and upward flows from different quarters of the small enough vicinities of the critical points. Let us note that initial conditions for red downward and blue upward flows were the same to test their fast converge to the related and respectively. Let us note that the power low grows on the complex plane of the right part of differential Equations (6) and (7) results in limitations on the “time” l of obtained solutions at needed given accuracy.
As only the blue line for red point crosses the real axis ( ) we calculate integral defined the Airy function along the red Lefschetz thimble. As we mentioned above the Markovian chain traveling on the whole complex plane prefer namely this critical point ignoring the second one. The reason of this interesting fact has been further investigated.
Results of the MC calculation at are presented in Table 1 as well as results of some additional calculations for and . Comparison of obtained MC results with well known values of Airy function demonstrates a good enough agreement. Discrepancy between exact values of the Airy function and related values obtained by proposed procedure can be explained by approximations used in transitions from initial integral to its Lefschetz thimbles representation accounting for only the main contribution to the contour integrals.
Figure 2. (Color online) (Left plot) The averaged downward flows are lines-1 ( ) and the upward flows are lines-2 ( ). The critical points are points 3 and 4 ( ) of the integrand in (14). Red critical point and the associated thimbles contribute to the contour integral of the Airy function (14) as , while the blue point not, as . (Right plot) Details of initial conditions obtained by MC method in different quarters of small vicinity of the critical point.
Table 1. The MC results versus the exact Airy function.
6.2. Short Time Wigner Path Integral
Now to test the developed approach let us consider elementary factor in the finite dimensional approximation of the path integral, which may be rewritten in the form like (see (5)):
where, for example, .
The left and right plots of Figure 3 are the contour plots of the image and real parts of the power of exponent in integrand in (15) respectively. Right plot of Figure 3 presents contour plot of the probability, which with conditional probability allows finding by MC method the critical points and provides the initial conditions for solution of the Equations (6) and (7). According to the Monte Carlo simulation the critical points are , and , which agree with the regions of the saddle-like behaviour of the contour lines on left and right plots of Figure 3. Here the Markovian chain traveling on the whole complex plane always stabilizes in the vicinity of the critical point and ignoring the point .
As before solution of the complex valued differential Equations (6) and (7) with MC initial conditions nearby both upper critical points allow to obtain averaged downward (red lines) and upward (blue lines) flows (see Figure 4). As both blue lines for red point cross the real axis ( ) we calculate sum of the contributions to the integral (15) along the both red Lefschetz thimbles with opposite sign due to the different thimble orientation. According to the Morse theory contribution of the bottom critical point has to be ignored as the related blue line does not cross real axis (here not shown) and the maximum of the integrand on the real axis is smaller than the value of the integrand at this critical point.
As before details the MC initial conditions and related downward and upward flows are presented by right plot of Figure 4. Let us note that red and blue lines start at the same MC initial points. Reason of asymmetry in behavior of the red and blue lines is in asymmetry of the real and imaginary parts of the power in exponent (see Figure 4). Let us stress the fast convergence of the upward and downward flows to the related limit lines and . Comparison of the Monte Carlo result for with independent exact calculations
Figure 3. (Color online) The contour plot of imaginary part(left panel) and real part (central panel) of the of the power in exponent in (15) on complex plane for . (Right plot) Contour plot of the probability .
Figure 4. (Color online) The averaged downward flows are lines-1 ( ) and the upward flows are lines-2 ( ) at and and . The critical points of the integrand in (15) are points 3 ( ). Red critical point and the associated thimbles contribute to the contour integral (15) as . (Right plot) Details of MC initial conditions in different quarters of small vicinity of the critical points.
demonstrate a good enough accuracy of the developed approach.
6.3. Short Time Feynman Path Integral
As the second example, we consider an elementary factor in discrete form of path integral (5) with imaginary parameter :
Contour plots on Figure 5 show imaginary and real parts of the complex-valued action , when and
. Two critical points and its Lefschetz thimble should be taken into account according to the explained above procedure (see red and blue lines on the right plot of Figure 5). In this case analytical estimations of the integral (16) are not available, while the independent numerical estimations due to the fast oscillations of the integrand in (16) is not reliable. The Monte Carlo calculations of the (16) demonstrate the fast convergence and will be considered later.
Figure 5. The contour plot of phase (left panel) and modulus (central panel) of the integrand from (16) on complex-valued plane for and . Averaged downward and upward flows from the neighborhood of the two critical points (red and blue lines on the right plot correspondingly).
The main goal of this paper is to develop a new effective Monte Carlo method for numerical evaluation of a Feynman path integrals suffering to the “sign problem”. This approach combines the basic ideas of the Metropolis and Hasting algorithms and is based on the Picard-Lefschetz theory and complex-valued version of Morse theory. Developed approach allows also simulating the path integral representation of the Wigner function. The basic ideas from mathematics come from Picard-Lefschetz theory and from Morse theory based on selection of the manifolds approaching the saddle points of the integrand, where the imaginary part of the complex-valued action stays constant (Lefschetz thimbles). Since the imaginary part of the action is constant on each thimble, the “sign problem” on the thimble disappears and the Feynman integrals can be calculated much more effectively. Some simple 1D test calculations and comparisons with available analytical results have been carried out. We hope that this method can also provide a new perspective in the path integration.
We acknowledge stimulating discussions with D. Blaschke and Yu.B. Ivanov.
 Alexandru A., Başar, G. and Bedaque, P. (2016) Monte Carlo Algorithm for Simulating Fermions on Lefschetz Thimbles. Physical Review D, 93, Article ID: 014504.
 Alexandru, A., Başar, G., Bedaque, P.F. and Ridgway, G. (2017) Schwinger-Keldysh Formalism on the Lattice: A Faster Algorithm and Its Application to Field Theory. Physical Review D, 95, Article ID: 114501.
 Klauder, J.R. (1984) Coherent-State Langevin Equations for Canonical Quantum Systems with Applications to the Quantized Hall Effect. Physical Review A, 29, 2036.
 Fujii, H., Honda, D., Kato, M., Kikukawa, Y., Komatsu, S. and Sano, T. (2013) Hybrid Monte Carlo on Lefschetz Thimbles—A Study of the Residual Sign Problem. Journal of High Energy Physics, 2013, Article No. 147.
 Mukherjee, A., Cristoforetti, M. and Scorzato, L. (2013) Metropolis Monte Carlo Integration on the Lefschetz Thimble: Application to a One-Plaquette Model. Physical Review D, 88, Article ID: 051502.
 Di Renzo, F. and Eruzzi, G. (2015) Thimble Regularization at Work: From Toy Models to Chiral Random Matrix Theories. Physical Review D, 92, Article ID: 085030.
 Cristoforetti, M., Di Renzo, F., Scorzato, L., Collaboration, A., et al. (2012) New Approach to the Sign Problem in Quantum Field Theories: High Density QCD on a Lefschetz Thimble. Physical Review D, 86, Article ID: 074506.
 Mou, Z.-G., Saffin, P.M., Tranberg, A. and Woodward, S. (2019) Real-Time Quantum Dynamics, Path Integrals and the Method of Thimbles. Journal of High Energy Physics, 2019, Article No. 94.
 Berges, J., Borsanyi, S., Sexty, D. and Stamatescu, I.-O. (2007) Lattice Simulations of Real-Time Quantum Fields. Physical Review D, 75, Article ID: 045007.
 Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E. (1953) Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21, 1087.