We analyze the efficiency of available algorithms for the simulation of classical fidelity and show that their computational costs increase exponentially with the number of degrees of freedom. Then we present an algorithm for which the number of trajectories needed for convergence is independent of the system's dimensionality and show that, within a continuous family of algorithms, this algorithm is the only one with this property. Simultaneously we propose a general analytical approach to estimate efficiency of trajectory-based methods and suggest how to use it to accelerate calculations of other classical correlation functions. Converged numerical results are provided for systems with phase space volume 2^{1700} times larger than the volume of the initial state.
We analyze the efficiency of available algorithms for the simulation of classical fidelity and show that their computational costs increase exponentially with the number of degrees of freedom. Then we present an algorithm for which the number of trajectories needed for convergence is independent of the system's dimensionality and show that, within a continuous family of algorithms, this algorithm is the only one with this property. Simultaneously we propose a general analytical approach to estimate efficiency of trajectory-based methods and suggest how to use it to accelerate calculations of other classical correlation functions. Converged numerical results are provided for systems with phase space volume 2^{1700} times larger than the volume of the initial state.
This thesis is focused on classical and semiclassical approximations of a specific quantum time correlation function, the “quantum fidelity.” Namely, we rigorously study the efficiency of a continuous class of algorithms for the evaluation of its classical limit and both the cost and the error of a particular semiclassical approximation of it. In the physics domain, quantum fidelity can be used to study the cross section of inelastic neutron scattering and phenomena like decoherence and irreversibility in NMR experiments. In chemical physics, quantum fidelity can be employed to compute the spectrum of a quantum state, to evaluate the accuracy of quantum dynamics on an approximate potential energy surface, and to verify the importance of nonadiabatic electronic transitions in molecules. Unfortunately, as for any numerical simulation of a quantum dynamical object, many-dimensional calculations of quantum fidelity are extremely expensive computationally. Classical methods, not including any quantum effect, are generally believed to be efficient approximations for the numerical evaluation of large systems’ properties when quantum effects are not important. We prove that, previous to this research, the computational costs of available algorithms for the simulation of classical fidelity increased exponentially with the number of degrees of freedom and we single out, within a continuous family of algorithms, the only one for which the number of trajectories needed for convergence is independent of the system’s dimensionality. Recently a semiclassical method, called “dephasing representation” (DR), has been proposed to approximate quantum fidelity accurately and efficiently. Although semiclassical methods, approximately including all types of quantum effects, are generally more accurate but much less efficient than classical methods, we prove that for the semiclassical DR there exists at least one algorithm for which the number of trajectories needed for convergence is independent of dimensionality and also that this semiclassical algorithm is even faster than the most efficient classical fidelity algorithm previously singled out. Encouraged by the surprising efficiency of the specific semiclassical method, we investigate the error of the DR compared to the quantum benchmark.
While rigorous quantum dynamical simulations of many-body systems are extremely difficult (or impossible) due to exponential scaling with dimensionality, the corresponding classical simulations ignore quantum effects. Semiclassical methods are generally more efficient but less accurate than quantum methods and more accurate but less efficient than classical methods. We find a remarkable exception to this rule by showing that a semiclassical method can be both more accurate and faster than a classical simulation. Specifically, we prove that for the semiclassical dephasing representation the number of trajectories needed to simulate quantum fidelity is independent of dimensionality and also that this semiclassical method is even faster than the most efficient corresponding classical algorithm. Analytical results are confirmed with simulations of fidelity in up to 100 dimensions with 2(1700)-dimensional Hilbert space.
Quantum algorithms for simulating electronic ground states are slower than popular classical mean-field algorithms such as Hartree-Fock and density functional theory but offer higher accuracy. Accordingly, quantum computers have been predominantly regarded as competitors to only the most accurate and costly classical methods for treating electron correlation. However, here we tighten bounds showing that certain first-quantized quantum algorithms enable exact time evolution of electronic systems with exponentially less space and polynomially fewer operations in basis set size than conventional real-time time-dependent Hartree-Fock and density functional theory. Although the need to sample observables in the quantum algorithm reduces the speedup, we show that one can estimate all elements of the k-particle reduced density matrix with a number of samples scaling only polylogarithmically in basis set size. We also introduce a more efficient quantum algorithm for first-quantized mean-field state preparation that is likely cheaper than the cost of time evolution. We conclude that quantum speedup is most pronounced for finite-temperature simulations and suggest several practically important electron dynamics problems with potential quantum advantage.
Computing quantum dynamics in condensed matter systems is an open challenge due to the exponential scaling of exact algorithms with the number of degrees of freedom. Current methods try to reduce the cost of the calculation using classical dynamics as the key ingredient of approximations of the quantum time evolution. Two main approaches exist, quantum classical and semi-classical, but they suffer from various difficulties, in particular when trying to go beyond the classical approximation. It may then be useful to reconsider the problem focusing on statistical time-dependent averages rather than directly on the dynamics. In this paper, we discuss a recently developed scheme for calculating symmetrized correlation functions. In this scheme, the full (complex time) evolution is broken into segments alternating thermal and real-time propagation, and the latter is reduced to classical dynamics via a linearization approximation. Increasing the number of segments systematically improves the result with respect to full classical dynamics, but at a cost which is still prohibitive. If only one segment is considered, a cumulant expansion can be used to obtain a computationally efficient algorithm, which has proven accurate for condensed phase systems in moderately quantum regimes. This scheme is summarized in the second part of the paper. We conclude by outlining how the cumulant expansion formally provides a way to improve convergence also for more than one segment. Future work will focus on testing the numerical performance of this extension and, more importantly, on investigating the limit for the number of segments that goes to infinity of the approximate expression for the symmetrized correlation function to assess formally its convergence to the exact result.
Our discussion of Markov chains, with the exception of mentioning the Metropolis and heat-bath algorithms, has so far been very general with little contact with issues and opportunities related to specific applications. In this chapter, we recall that our target is many-body problems defined on a lattice and introduce several frameworks exploiting what is special about Markov processes for these types of problems. We consider here classical many-body problems, using the Ising model as the representative. Our discussion will be extended to various quantum many-body problems and algorithms in subsequent chapters. Many-body phase space The numerical difficulty of studying many-body problems on a lattice arises from the fact that their phase space Ω is a direct product of many phase spaces of local degrees of freedom. Generally, a local phase space is associated with each lattice site. If n is the size of this phase space and N is the number of lattice sites, then the number of states |Ω| available to the whole system is n N . In other words, the number of states in the phase space grows exponentially fast with the physical size of the system. For example, in the Ising model, the Ising spin s i on each site can take one of the two values ±1, and hence the number of states in the total phase space is 2 N . In Chapter 1, we noted that this exponential scaling thwarts deterministic solutions and is a reason why we use the Monte Carlo method. The exponentially large number of states implies that the enumeration of all states, which requires a computational effort proportional to the size of the phase space, is not an option for a problem with a large number of sites. As discussed in Section 2.7, the Monte Carlo method generally samples from a compressed phase space, avoiding the need to solve the entire problem. However, even with this advantage, can we reduce the computational effort to a manageable level? An obvious requirement is that we can equilibrate the simulation in a reasonable amount of computer time. We know that the Markov process converges to a stationary state sampling some distribution (Section 2.4), and for detailed balance algorithms, Rosenbluth's theorem (Section 2.6) guarantees monotonic convergence.
A technique for simulating quantum dynamics in phase space i discussed. It makes use of ensembles of classical trajectories to approximate the distribution functions and their derivatives by implementing Adaptive Kernel Density Estimation. It is found to improve the accuracy and stability of the simulations compared to more conventional particle methods. Formulation of the method in higher dimensions is straightforward. Complete analytical description of physical systems exist only for the most simple ideal cases. The vast majority of physical problems require the solution of approximate equations most fre- quently by using numerical calculations. To this end, much effort has been devoted to the devel- opment of suitable techniques to be used in computer simulations. The increasing computational power makes possible the description of more complicated, that is, less ideal systems allowing for more precise predictions of their properties as well as for a better understanding of the underlying phenomena. Among the wealth of numerical approaches to solve dynamical equations by means of discretization, particle methods have gained attention in the last few decades as a conceptu- ally appealing alternative. Conventional numerical solvers rely on a regular discretization of the independent variables to facilitate the evaluation of derivatives to a given order of accuracy. As a consequence, a mesh needs to be defined as the base of the simulations, parts of which remain empty at any given simulation time even with the most sophisticated mesh schemes. The cen- tral idea of particle methods consists of representing functions by sets of particles conveniently located and weighted such that the function is appropriately sampled by the particles. Evolution of the functions is then accomplished by an equivalent evolution of the particles. This meshless or Lagrangian type of discretization has some intrinsic computational efficiency advantages because there is no wasted space. The advantage, however, comes at the expense of having to evaluate derivatives of functions on unstructured arrays of sampling points. The issues about convergence and stability of the resulting algorithms have been the subject of active and fruitfull research. Currently there are some well established techniques to solve dynamical equations with particle methods. Our interest is to provide an alternative ingredient to further improve the performance of numerical solutions of dynamical problems of physical relevance. In the present work we discuss, in the context of particle methods, the implementation of a technique for representing functions and derivatives with adaptive parameters. Adaptiveness require the parameters to be automatically ad- justed to optimal values according to the location of the particles. As shown below, the proposed scheme is conceptually simple and has been tested in a number of different situations. In some simple test models the present work focuses on quantum dynamics, previously treated with more