Simple proof that there is no sign problem in path integral Monte Carlo simulations of fermions in one dimension.

It is widely known that there is no sign problem in path integral Monte Carlo (PIMC) simulations of fermions in one dimension. As far as the author is aware, there is no direct proof of this in the literature. This work shows that the sign of the N-fermion antisymmetric free propagator is given by the product of all possible pairs of particle separations, or relative displacements. For a nonvanishing closed-loop product of such propagators, as required by PIMC, all relative displacements from adjacent propagators are paired into perfect squares, and therefore the loop product must be positive, but only in one dimension. By comparison, permutation sampling, which does not evaluate the determinant of the antisymmetric propagator exactly, remains plagued by a low-level sign problem, even in one dimension.

Analytical evaluations of the path integral Monte Carlo thermodynamic and Hamiltonian energies for the harmonic oscillator.

By using the recently derived universal discrete imaginary-time propagator of the harmonic oscillator, both thermodynamic and Hamiltonian energies can be given analytically and evaluated numerically at each imaginary time step for any short-time propagator. This work shows that, using only currently known short-time propagators, the Hamiltonian energy can be optimized to the twelfth-order, converging to the ground state energy of the harmonic oscillator in as few as three beads. This study makes it absolutely clear that the widely used second-order primitive approximation propagator, when used in computing thermodynamic energy, converges extremely slowly with an increasing number of beads.

Anatomy of path integral Monte Carlo: Algebraic derivation of the harmonic oscillator's universal discrete imaginary-time propagator and its sequential optimization.

The direct integration of the harmonic oscillator path integral obscures the fundamental structure of its discrete, imaginary time propagator (density matrix). This work, by first proving an operator identity for contracting two free propagators into one in the presence of interaction, derives the discrete propagator by simple algebra without doing any integration. This discrete propagator is universal, having the same two hyperbolic coefficient functions for all short-time propagators. Individual short-time propagator only modifies the coefficient function's argument, its portal parameter, whose convergent order is the same as the thermodynamic energy. Moreover, the thermodynamic energy can be given in a closed form for any short-time propagator. Since the portal parameter can be systematically optimized by matching the expansion of the product of the two coefficients, any short-time propagator can be optimized sequentially, order by order, by matching the product coefficient's expansion alone, without computing the energy. Previous empirical findings on the convergence of fourth and sixth-order propagators can now be understood analytically. An eight-order convergent short-time propagator is also derived.

No sign problem in one-dimensional path integral Monte Carlo simulation of fermions: A topological proof.

This paper shows that, in one dimension, due to its topology, a closed-loop product of short-time propagators is always positive, despite the fact that each antisymmetric free fermion propagator can be of either sign.

Fundamental derivation of two Boris solvers and the Ge-Marsden theorem.

It has been known for some time that when one uses the Lorentz force law, rather than Hamilton's equation, one can derive two basic algorithms for solving trajectories in a magnetic field formally similar to the velocity-Verlet (VV) and position-Verlet (PV) symplectic integrators independent of any finite-difference approximation. Because the Lorentz force law uses the mechanical rather than the canonical momentum, the resulting magnetic field algorithms are exact energy conserving, rather than symplectic. In general, both types of algorithms can only yield the exact trajectory in the limit of vanishing small time steps. This work shows that, for a constant magnetic field, both magnetic algorithms can be further modified so that their trajectories are exactly on the gyrocircle at finite time steps. The magnetic form of the PV integrator then becomes the well-known Boris solver, while the VV form yields a second, previously unknown Boris-type algorithm, unrelated to any finite-difference scheme. Remarkably, the modification needed for the trajectory to be exact is a reparametrization of the time step, reminiscent of the Ge-Marsden theorem.

Solving fermion problems without solving the sign problem: Symmetry-breaking wave functions from similarity-transformed propagators for solving two-dimensional quantum dots.

It is well known that the use of the primitive second-order propagator in path-integral Monte Carlo calculations of many-fermion systems leads to the sign problem. This work will show that by using the similarity-transformed Fokker-Planck propagator, it is possible to solve for the ground state of a large quantum dot, with up to 100 polarized electrons, without solving the sign problem. These similarity-transformed propagators naturally produce rotational symmetry-breaking ground-state wave functions previously used in the study of quantum dots and quantum Hall effects. However, instead of localizing the electrons at positions that minimize the potential energy, this derivation shows that they should be located at positions that maximize the bosonic ground-state wave function. Further improvements in the energy can be obtained by using these as initial wave functions in a ground-state path-integral Monte Carlo calculation with second- and fourth-order propagators.

Peak-height formula for higher-order breathers of the nonlinear Schrödinger equation on nonuniform backgrounds.

Given any background (or seed) solution of the nonlinear Schrödinger equation, the Darboux transformation can be used to generate higher-order breathers with much greater peak intensities. In this work, we use the Darboux transformation to prove, in a unified manner and without knowing the analytical form of the background solution, that the peak height of a high-order breather is just a sum of peak heights of first-order breathers plus that of the background, irrespective of the specific choice of the background. Detailed results are verified for breathers on a cnoidal background. Generalizations to more extended nonlinear Schrödinger equations, such as the Hirota equation, are indicated.

High-order path-integral Monte Carlo methods for solving quantum dot problems.

The conventional second-order path-integral Monte Carlo method is plagued with the sign problem in solving many-fermion systems. This is due to the large number of antisymmetric free-fermion propagators that are needed to extract the ground state wave function at large imaginary time. In this work we show that optimized fourth-order path-integral Monte Carlo methods, which use no more than five free-fermion propagators, can yield accurate quantum dot energies for up to 20 polarized electrons with the use of the Hamiltonian energy estimator.

Anatomy of the Akhmediev breather: Cascading instability, first formation time, and Fermi-Pasta-Ulam recurrence.

By invoking Bogoliubov's spectrum, we show that for the nonlinear Schrödinger equation, the modulation instability (MI) of its n=1 Fourier mode on a finite background automatically triggers a further cascading instability, forcing all the higher modes to grow exponentially in locked step with the n=1 mode. This fundamental insight, the enslavement of all higher modes to the n=1 mode, explains the formation of a triangular-shaped spectrum that generates the Akhmediev breather, predicts its formation time analytically from the initial modulation amplitude, and shows that the Fermi-Pasta-Ulam (FPU) recurrence is just a matter of energy conservation with a period twice the breather's formation time. For higher-order MI with more than one initial unstable mode, while most evolutions are expected to be chaotic, we show that it is possible to have isolated cases of "super-recurrence," where the FPU period is much longer than that of a single unstable mode.

Extrapolated high-order propagators for path integral Monte Carlo simulations.

We present a new class of high-order imaginary time propagators for path integral Monte Carlo simulations that require no higher order derivatives of the potential nor explicit quadratures of Gaussian trajectories. Higher orders are achieved by an extrapolation of the primitive second-order propagator involving subtractions. By requiring all terms of the extrapolated propagator to have the same Gaussian trajectory, the subtraction only affects the potential part of the path integral. The resulting violation of positivity has surprisingly little effects on the accuracy of the algorithms at practical time steps. Thus in principle, arbitrarily high order algorithms can be devised for path integral Monte Carlo simulations. We verified the fourth, sixth, and eighth order convergences of these algorithms by solving for the ground state energy and pair distribution function of liquid (4)He, which is representative of a dense, and strongly interacting, quantum many-body system.

Explicit symplectic integrators for solving nonseparable Hamiltonians.

By exploiting the error functions of explicit symplectic integrators for solving separable Hamiltonians, I show that it is possible to develop explicit time-reversible symplectic integrators for solving nonseparable Hamiltonians of the product form. The algorithms are unusual in that they are of fractional orders.

Symplectic and energy-conserving algorithms for solving magnetic field trajectories.

The exponential splitting of the classical evolution operator yields symplectic integrators if the canonical Hamiltonian is separable. Similar splitting of the noncanonical evolution operator for a charged particle in a magnetic field produces exact energy-conserving algorithms. The latter algorithms evaluate the magnetic field directly with no need of a vector potential and are more stable with far less phase errors than symplectic integrators. For a combined electric and magnetic field, these algorithms from splitting the noncanonical evolution operator are neither fully symplectic nor exactly energy conserving, yet they behave exactly like symplectic algorithms in having qualitatively correct trajectories and bounded periodic energy errors. This work shows that exponential-splitting algorithms of any order for solving particle trajectories in a general electric and magnetic field can be systematically derived by use of the angular momentum operator of quantum mechanics. The use of operator analysis in this work fully comprehends the intertwining interaction between electric and magnetic forces and makes possible the derivation of highly nontrivial integrators.

Physics of symplectic integrators: perihelion advances and symplectic corrector algorithms.

Symplectic integrators evolve dynamical systems according to modified Hamiltonians whose error terms are also well-defined Hamiltonians. The error of the algorithm is the sum of each error Hamiltonian's perturbation on the exact solution. When symplectic integrators are applied to the Kepler problem, these error terms cause the orbit to precess. In this work, by developing a general method of computing the perihelion advance via the Laplace-Runge-Lenz vector even for nonseparable Hamiltonians, I show that the precession error in symplectic integrators can be computed analytically. It is found that at leading order, each paired error Hamiltonians cause the orbit to precess oppositely by exactly the same amount after each period. Hence, symplectic corrector, or process integrators, which have equal coefficients for these paired error terms, will have their precession errors cancel at that order after each period. With the use of correctable algorithms, both the energy and precession error are of effective order n+2 where n is the nominal order of the algorithm. Thus the physics of symplectic integrators determines the optimal algorithm for integrating long-time periodic motions.

Higher-order splitting algorithms for solving the nonlinear Schrödinger equation and their instabilities.

Since the kinetic and potential energy terms of the real-time nonlinear Schrödinger equation can each be solved exactly, the entire equation can be solved to any order via splitting algorithms. We verified the fourth-order convergence of some well-known algorithms by solving the Gross-Pitaevskii equation numerically. All such splitting algorithms suffer from a latent numerical instability even when the total energy is very well conserved. A detail error analysis reveals that the noise, or elementary excitations of the nonlinear Schrödinger equation, obeys the Bogoliubov spectrum and the instability is due to the exponential growth of high-wave-number noises caused by the splitting process. For a continuum wave function, this instability is unavoidable no matter how small the time step. For a discrete wave function, the instability can be avoided only for Deltatkmax2 < or =2pi, where kmax=pi/Deltax.

Complete characterization of fourth-order symplectic integrators with extended-linear coefficients.

The structure of symplectic integrators up to fourth order can be completely and analytically understood when the factorization (split) coefficients are related linearly but with a uniform nonlinear proportional factor. The analytic form of these extended-linear symplectic integrators greatly simplified proofs of their general properties and allowed easy construction of both forward and nonforward fourth-order algorithms with an arbitrary number of operators. Most fourth-order forward integrators can now be derived analytically from this extended-linear formulation without the use of symbolic algebra.

Gradient symplectic algorithms for solving the radial Schrodinger equation.

The radial Schrodinger equation for a spherically symmetric potential can be regarded as a one-dimensional classical harmonic oscillator with a time-dependent spring constant. For solving classical dynamics problems, symplectic integrators are well known for their excellent conservation properties. The class of gradient symplectic algorithms is particularly suited for solving harmonic-oscillator dynamics. By use of Suzuki's rule [Proc. Jpn. Acad., Ser. B: Phys. Biol. Sci. 69, 161 (1993)] for decomposing time-ordered operators, these algorithms can be easily applied to the Schrodinger equation. We demonstrate the power of this class of gradient algorithms by solving the spectrum of highly singular radial potentials using Killingbeck's method [J. Phys. A 18, 245 (1985)] of backward Newton-Ralphson iterations.

Fourth-order algorithms for solving the imaginary-time Gross-Pitaevskii equation in a rotating anisotropic trap.

By implementing the exact density matrix for the rotating anisotropic harmonic trap, we derive a class of very fast and accurate fourth-order algorithms for evolving the Gross-Pitaevskii equation in imaginary time. Such fourth-order algorithms are possible only with the use of forward, positive time step factorization schemes. These fourth-order algorithms converge at time-step sizes an order-of-magnitude larger than conventional second-order algorithms. Our use of time-dependent factorization schemes provides a systematic way of devising algorithms for solving this type of nonlinear equations.

Forward symplectic integrators and the long-time phase error in periodic motions.

We show that when time-reversible symplectic algorithms are used to solve periodic motions, the energy error after one period is generally two orders higher than that of the algorithm. By use of correctable algorithms, we show that the phase error can also be eliminated two orders higher than that of the integrator. The use of fourth order forward time step integrators can result in sixth order accuracy for the phase error and eighth order accuracy in the periodic energy. We study the one-dimensional harmonic oscillator and the two-dimensional Kepler problem in great detail, and compare the effectiveness of some recent fourth order algorithms.

Structure of positive decompositions of exponential operators.

The solution of many physical evolution equations can be expressed as an exponential of two or more operators acting on initial data. Accurate solutions can be systematically derived by decomposing the exponential in a product form. For time-reversible equations, such as the Hamilton or the Schrödinger equation, it is immaterial whether or not the decomposition coefficients are positive. In fact, most symplectic algorithms for solving classical dynamics contain some negative coefficients. For time-irreversible systems, such as the Fokker-Planck equation or the quantum statistical propagator, only positive-coefficient decompositions, which respect the time-irreversibility of the diffusion kernel, can yield practical algorithms. These positive time steps only, forward decompositions, are a highly effective class of factorization algorithms. This work presents a framework for understanding the structure of these algorithms. By a suitable representation of the factorization coefficients, we show that specific error terms and order conditions can be solved analytically. Using this framework, we can go beyond the Sheng-Suzuki theorem and derive a lower bound for the error coefficient e(VTV). By generalizing the framework perturbatively, we can further prove that it is not possible to have a sixth-order forward algorithm by including only the commutator [VTV] tripple bond [V, [T,V]]. The pattern of these higher-order forward algorithms is that in going from the (2n)th to the (2n+2)th order, one must include a different commutator [V T(2n-1)V] in the decomposition process.

Dynamical multiple-time stepping methods for overcoming resonance instabilities.

Current molecular dynamics simulations of biomolecules using multiple time steps to update the slowly changing force are hampered by instabilities beginning at time steps near the half period of the fastest vibrating mode. These "resonance" instabilities have became a critical barrier preventing the long time simulation of biomolecular dynamics. Attempts to tame these instabilities by altering the slowly changing force and efforts to damp them out by Langevin dynamics do not address the fundamental cause of these instabilities. In this work, we trace the instability to the nonanalytic character of the underlying spectrum and show that a correct splitting of the Hamiltonian, which renders the spectrum analytic, restores stability. The resulting Hamiltonian dictates that in addition to updating the momentum due to the slowly changing force, one must also update the position with a modified mass. Thus multiple-time stepping must be done dynamically.