The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. On a fundamental level, such an investigation sheds light on the intrinsic computational power that is harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-ups over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. On the other hand, classical simulation of many-body systems is a challenging task, as the dimension of the Hilbert space scales with the number of particles. Therefore, to understand the properties of the systems, suitable approximation methods need to be employed. The lectures will be divided into two parts. In the first part we discuss classical simulation of quantum computation from several perspectives. We review a number of well-known examples of classically simulatable quantum computations, such as the Gottesman-Knill theorem, matchgate simulation and tensor contraction methods. We further discuss simulation methods that are centred on classical sampling methods (‘weak simulation’), and illustrate how these techniques outperform methods that rely on the exact computation of measurement probabilities (‘strong simulation’). The second part focuses on "Entanglement and variational wavefunctions in quantum many body physics". We review the idea of entanglement in quantum many-body systems and how it helps us to understand the success of numerical renormalization group methods. In particular we will discuss a few variational wave-function based methods for simulating strongly correlated quantum systems, which include (1) matrix product states (2) multiscale entanglement renormalization ansatz (3) projected entangled pair states and (4) continuous matrix product states for quantum field theories.
The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. On a fundamental level, such an investigation sheds light on the intrinsic computational power that is harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-ups over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. On the other hand, classical simulation of many-body systems is a challenging task, as the dimension of the Hilbert space scales with the number of particles. Therefore, to understand the properties of the systems, suitable approximation methods need to be employed. The lectures will be divided into two parts. In the first part we discuss classical simulation of quantum computation from several perspectives. We review a number of well-known examples of classically simulatable quantum computations, such as the Gottesman-Knill theorem, matchgate simulation and tensor contraction methods. We further discuss simulation methods that are centred on classical sampling methods (‘weak simulation’), and illustrate how these techniques outperform methods that rely on the exact computation of measurement probabilities (‘strong simulation’). The second part focuses on "Entanglement and variational wavefunctions in quantum many body physics". We review the idea of entanglement in quantum many-body systems and how it helps us to understand the success of numerical renormalization group methods. In particular we will discuss a few variational wave-function based methods for simulating strongly correlated quantum systems, which include (1) matrix product states (2) multiscale entanglement renormalization ansatz (3) projected entangled pair states and (4) continuous matrix product states for quantum field theories.
The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. On a fundamental level, such an investigation sheds light on the intrinsic computational power that is harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-ups over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. On the other hand, classical simulation of many-body systems is a challenging task, as the dimension of the Hilbert space scales with the number of particles. Therefore, to understand the properties of the systems, suitable approximation methods need to be employed. The lectures will be divided into two parts. In the first part we discuss classical simulation of quantum computation from several perspectives. We review a number of well-known examples of classically simulatable quantum computations, such as the Gottesman-Knill theorem, matchgate simulation and tensor contraction methods. We further discuss simulation methods that are centred on classical sampling methods (‘weak simulation’), and illustrate how these techniques outperform methods that rely on the exact computation of measurement probabilities (‘strong simulation’). The second part focuses on "Entanglement and variational wavefunctions in quantum many body physics". We review the idea of entanglement in quantum many-body systems and how it helps us to understand the success of numerical renormalization group methods. In particular we will discuss a few variational wave-function based methods for simulating strongly correlated quantum systems, which include (1) matrix product states (2) multiscale entanglement renormalization ansatz (3) projected entangled pair states and (4) continuous matrix product states for quantum field theories.
Classical simulation of quantum many-body systems is in general a challenging problem for the simple reason that the dimension of the Hilbert space grows exponentially with the system size. In particular, merely encoding a generic quantum many-body state requires an exponential number of bits. However, condensed matter physicists are mostly interested in local Hamiltonians and especially their ground states, which are highly non-generic. Thus, we might hope that at least some physical systems allow efficient classical simulation.Starting with one-dimensional (1D) quantum systems (i.e., the simplest nontrivial case), the first basic question is: Which classes of states have efficient classical representations? It turns out that this question is quantitatively related to the amount of entanglement in the state, for states with ``little entanglement'' are well approximated by matrix product states (a data structure that can be manipulated efficiently on a classical computer). At a technical level, the mathematical notion for ``little entanglement'' is area law, which has been proved for unique ground states in 1D gapped systems. We establish an area law for constant-fold degenerate ground states in 1D gapped systems and thus explain the effectiveness of matrix-product-state methods in (e.g.) symmetry breaking phases. This result might not be intuitively trivial as degenerate ground states in gapped systems can be long-range correlated.Suppose an efficient classical representation exists. How can one find it efficiently? The density matrix renormalization group is the leading numerical method for computing ground states in 1D quantum systems. However, it is a heuristic algorithm and the possibility that it may fail in some cases cannot be completely ruled out. Recently, a provably efficient variant of the density matrix renormalization group has been developed for frustration-free 1D gapped systems. We generalize this algorithm to all (i.e., possibly frustrated) 1D gapped systems. Note that the ground-state energy of 1D gapless Hamiltonians is computationally intractable even in the presence of translational invariance.It is tempting to extend methods and tools in 1D to two and higher dimensions (2+D), e.g., matrix product states are generalized to tensor network states. Since an area law for entanglement (if formulated properly) implies efficient matrix product state representations in 1D, an interesting question is whether a similar implication holds in 2+D. Roughly speaking, we show that an area law for entanglement (in any reasonable formulation) does not always imply efficient tensor network representations of the ground states of 2+D local Hamiltonians even in the presence of translational invariance. It should be emphasized that this result does not contradict with the common sense that in practice quantum states with more entanglement usually require more space to be stored classically; rather, it demonstrates that the relationship between entanglement and efficient classical representations is still far from being well understood.Excited eigenstates participate in the dynamics of quantum systems and are particularly relevant to the phenomenon of many-body localization (absence of transport at finite temperature in strongly correlated systems). We study the entanglement of excited eigenstates in random spin chains and expect that its singularities coincide with dynamical quantum phase transitions. This expectation is confirmed in the disordered quantum Ising chain using both analytical and numerical methods.Finally, we study the problem of generating ground states (possibly with topological order) in 1D gapped systems using quantum circuits. This is an interesting problem both in theory and in practice. It not only characterizes the essential difference between the entanglement patterns that give rise to trivial and nontrivial topological order, but also quantifies the difficulty of preparing quantum states with a quantum computer (in experiments).
The study of quantum computations that can be simulated efficiently classically is of interest for numerous reasons. From a fundamental point of view, such an investigation sheds light on the intrinsic computational power harnessed in quantum mechanics as compared to classical physics. More practically, understanding which quantum computations do not offer any speed-up over classical computation provides insights in where (not) to look for novel quantum algorithmic primitives. In this talk we discuss novel classical simulation methods that are centered on probabilistic methods ('weak simulation'). We show how these techniques outperform existing methods that rely on the exact computation of measurement probabilities ('strong simulation'). Using weak simulation methods, several new classes of simulatable quantum circuits are generated. For example, we show that various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform an! d other circuits are classically simulatable. Finally, we focus on famous quantum algorithms and investigate the origin of their computational power, or their lack thereof.
The study of interacting quantum many-body systems is one of the central challenges in modern physics. Interestingly, by understanding the physical properties of such systems from a microscopic description, one can explain many complex quantum phenomena such as the high-temperature superconductivity, fractional quantum Hall effect, etc. However, due to high complexity of these systems, theoretical investigations such as analytical and perturbation theories are limited to studying only a small subset of problems. In the past few decades, numerical simulation has emerged as an indispensable method for studying many phenomena, and has led to immense success and progress in recent years. The main obstacle in addressing quantum many-body systems is that the number of parameters required to represent a state of the system scales exponentially with the system size. However, one hardly needs the full Hilbert space but only a small subspace to describe physical properties of the system. From the point of view in quantum information theory, quantum entanglement is one of the main factors that is responsible for the complexity of studying quantum many-body systems. In particular, the amount of quantum entanglement in such system quantifies the correlation between constituents and therefore it determines how big the subspace is required to represent the system. In this thesis, we are interested in using tensor network states, a new emerging numerical technique to study dynamical and ground state properties of the system. The key ingredient is that a tensor network state which consists of a fairly small number of parameters can represent very well the complete wave function of a system. In one spatial dimension, Matrix Product State (MPS) has become a standard tool, combined with related algorithms such as Time Evolving Block Decimation algorithm (TEBD) to study dynamical properties of a locally-perturbed quantum lattice system. In this thesis, we introduce a technique called ``infinite boundary conditions'' that allows us to use a finite-size MPS to represent the state of an infinite-size system. As a result, one can simulate dynamics of a system for a longer time with a significant computational cost reduction compared to traditional methods. In two spatial dimensions, the tensor network known as Projected Entangled Pair States (PEPS) is emerging as a useful approach. However algorithms for optimizing the matrix elements of these tensors are complex and not very efficient. In particular, the efficiency of the optimization depends critically on the quality of the so-called ``environment'', which is expensive to compute. We have introduced a new method to accelerate the convergence of calculating the PEPS ground state by recycling the environment tensors for many optimization steps, vastly reducing the number of times that the full environment needs to be calculated.
This thesis focuses on the development, application, and high-performance implementation of numerical methods for simulating quantum many-body systems. In the first chapter, I provide an overview of several most successful conventional approaches for simulating quantum many-body systems, along with their current limitations. Then, the basic properties of the quantum spin model, which will be the subject of study in the following chapters, and its ground state are briefly summarized. Additionally, I discuss the background and the motivations of the research projects carried out during my PhD research. Chapter 2 introduces two numerical algorithms that are extensively used in this thesis, which are exact diagonalization (ED) and variational Monte Carlo. I outline the process of constructing a Hamiltonian matrix and employing iterative methods for exact diagonalization. Subsequently, I introduce the mechanism of the four important components in the ``standard" variational Monte Carlo that are widely used in the most recent research. In Chapter 3, we propose a symmetry-projected variational ansatz in the form of linear combinations of simple restricted Boltzmann machines. This construction allows one to explore states outside of the original variational manifold and increase the representation power with moderate computational effort. Besides allowing one to restore spatial symmetries, an expansion in terms of Krylov states using a Lanczos recursion offers a solution that can further improve the quantum state accuracy. We illustrate these ideas with an application to the Heisenberg J1−J2 model on the square lattice, a paradigmatic problem under debate in condensed matter physics,and achieve state-of-the-art accuracy in the representation of the ground state. In Chapter 4, we present a variational approach based on a Chebyshev expansion of the spectral function, and each Chebyshev polynomial is represented by a neural network quantum state. The Chebyshev moments are obtained by recursively applying the Hamiltonian and projecting on the space of variational states using a modified natural gradient descent method. We compare this approach with a modified approximation of the spectral function which uses a Krylov subspace constructed from the "Chebyshev wave functions." We present results for the one-dimensional and two-dimensional Heisenberg models on the square lattice and compare them with those obtained by other methods in the literature. In Chapter 5, we describe a method to carry out thermodynamic simulations of quantum many-body models using typicality and variational representations of quantum states. Minimally entangled typical thermal states (METTS) are a construction that allows one to solve for the imaginary time evolution of quantum many-body systems. By using wave functions that are weakly entangled, one can take advantage of efficient representations in the form of matrixproduct states. We generalize these ideas to arbitrary variational wave functions and we focus, as an illustration, on the particular case of restricted Boltzmann machines. We demonstrate the application of the method to quantum spin systems in one and two spatial dimensions. In Chapter 6, we study the properties of the impurity band in heavily doped nonmagnetic semiconductors using the Jacobi-Davidson algorithm and the supervised deep learning method. The disorder averaged inverse participation ratio and Thouless number calculation show us the rich structure inside the impurity band. A convolutional neural network model, which is trained to distinguish the extended/localized phase of the Anderson model with high accuracy, shows us the results in good agreement with the conventional approach. Together, we find that there are three mobility edges in the impurity band for a specific on-site impurity potential, which means the presence of the extended states while filling the impurity band. In the final chapter, Chapter 7, we discuss the implementation of architecture-aware optimizations for spin dynamics simulations on x86 CPUs and Nvidia GPUs. The time cost of evaluating the spin-spin correlation functions in real space increases quadratically as the number of spins N, leading to significant computational effort, making the simulation of large spin systems very challenging. We propose to use a highly optimized general matrix multiply (GEMM) subroutine to calculate the dynamical spin-spin correlation function that can achieve near-optimal hardware utilization. Furthermore, we fuse the element-wise operations in the calculation of S(q,t) into the in-house GEMM kernel to reduce memory latency. On Nvidia GPU, we perform the on-the-fly calculation in the epilogue of the GEMM subroutine to avoid saving intermediate results on global memory, which significantly reduces memory usage and achieves better performance than cuBLAS.--Author's abstract
In this thesis, the numerical simulation of strongly-interacting many-body quantum-mechanical systems using matrix product states (MPS) is considered. Compared to classical systems, quantum many-body systems possess an exponentially enlarged number of degrees of freedom, significantly complicating a simulation on a classical computer. Matrix-Product-States are a novel representation of arbitrary quantum many-body states. Using quantum information theory, it is possible to show that Matrix-Product-States provide a polynomial-sized representation of one-dimensional quantum systems, thus allowing an efficient simulation of one-dimensional quantum system on classical computers. Matrix-Product-States form the conceptual framework of the density-matrix renormalization group (DMRG). Based upon this connection, deeper understanding of the density matrix renormalization group can be obtained. After a general introduction in the first chapter of this thesis, the second chapter deals with Matrix-Product-States, focusing on the development of fast and stable algorithms. It is possible to extend the Matrix-Product-States approach to be able to represent arbitrary operators, the so-called Matrix-Product-Operators, which allows a fast and flexible calculation of arbitrary expectation values. To obtain algorithms to efficiently calculate groundstates, the density-matrix renormalization group is reformulated using the Matrix-Product-States framework. Further, time-dependent problems are considered. Two different algorithms are presented, one based on a Trotter decomposition of the time-evolution operator, the other one on Krylov subspaces. Finally, the evaluation of dynamical spectral functions is discussed, and a correction vector-based method is presented. In the following chapters, the methods presented in the second chapter, are applied to a number of different physical problems. The third chapter deals with the existence of chiral phases in isotropic one-dimensional quantum spin systems. A preceding analytical study based on a mean-field approach indicated the possible existence of those phases in an isotopic Heisenberg model with a frustrating zig-zag interaction and a magnetic field. In this thesis, the existence of the chiral phases will be shown numerically by using Matrix-Product-States-based algorithms. A key effect of interacting one-dimensional quantum-mechanical many-body systems is the spin-charge separation. However, up to now only signs of the spin-charge separation have been observed in experiments. In the fourth chapter, we propose an experiment using ultracold atomic gases in optical lattices, which allows a well controlled observation of the spin-charge separation (of different hyperfine states of the ultracold atoms) with current state of the art experimental techniques. Ultracold atoms in optical lattices are well described by (Bose)-Hubbard models. In order to support this proposal, we present numerical results for realistic system parameters. Matrix-Product-States are an excellent tool for the simulation of one-dimensional quantum systems, however, they are not well suited for the simulation of higher dimensional systems. For strongly-correlated systems, for instance cuprates-based high-temperature superconductors, quantum fluctuations play an essential role. Classical mean-field theories neglect any kind of fluctuations, thus they are not suitable to describe strongly-correlated systems. The dynamical mean-field theory (DMFT) fully takes local quantum fluctuations into account but neglects any kind of spatial fluctuations. The many-body problem on the lattice is mapped onto an impurity problem, which needs to be solved self-consistently. In the last chapter of this thesis, Matrix-Product-States-based algorithms are used to solve the impurity problem of the dynamical mean-field theory. We present results for a Hubbard model on a one-dimensional lattice and on a Bethe lattice obtained by the dynamical mean-field and compare them with exact results.