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.
Quantum computers are expected to significantly outperform classical computers for certain computational tasks. One of the most promising applications is the simulation of many-body systems such as complex molecules or materials. In this thesis, we present several quantum algorithms for simulating many-body systems that can provide considerably better scaling than prior approaches. First, we describe a fully coherent quantum algorithm for simulating molecular dynamics within the Born-Oppenheimer approximation that leads to super-polynomially better scaling with respect to the error tolerance than previous work. Our algorithm utilizes the Koopman-von Neumann formulation of classical mechanics. This allows us to express the classical equations of motion as unitary dynamics which can be efficiently simulated on a quantum computer. We demonstrate that these simulations can be performed either at constant energy or at constant temperature. The latter allows us to estimate thermodynamic properties such as the Helmholtz free energy of the system. Next, we present two closely related quantum algorithms for solving continuous optimization problems such as finding the equilibrium configurations of molecules. These algorithms do not require any explicit gradient estimations. Instead, we encode the optimization problem into the dynamics of a quantum or classical system with friction. The dynamics are governed by a carefully chosen time-dependent Hamiltonian and thus can be simulated using efficient Hamiltonian simulation algorithms. We provide evidence that our fully coherent quantum algorithms can, in certain cases, provide exponentially better asymptotic scaling than approaches based on gradient descent. Lastly, we present a quantum algorithm for preparing the ground state of a set of interacting systems that can circumvent the exponential scaling suggested by the Van Vleck catastrophe. Our algorithm utilizes a divide-and-conquer strategy that repeatedly uses phase estimation to merge ground states of increasingly larger subsystems. We provide rigorous bounds for this approach and show that, under certain assumptions, our algorithm scales only quasi-polynomially with the number of systems.