Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.
Tensor network states constitute an important variational set of quantum states for numerical studies of strongly correlated systems in condensed-matter physics, as well as in mathematical physics. This is specifically true for finitely correlated states or matrix-product operators, designed to capture mixed states of one-dimensional quantum systems. It is a well-known open problem to find an efficient algorithm that decides whether a given matrix-product operator actually represents a physical state that in particular has no negative eigenvalues. We address and answer this question by showing that the problem is provably undecidable in the thermodynamic limit and that the bounded version of the problem is NP-hard (nondeterministic-polynomial-time hard) in the system size. Furthermore, we discuss numerous connections between tensor network methods and (seemingly) different concepts treated before in the literature, such as hidden Markov models and tensor trains.
The term Tensor Network States (TNS) refers to a number of families of states that represent different ansätze for the efficient description of the state of a quantum many-body system.Matrix Product States (MPS) are one particular case of TNS, and have become the most precise tool for the numerical study of one dimensional quantum many-body systems, as the basis of the Density Matrix Renormalization Group method.Lattice Gauge Theories (LGT), in their Hamiltonian version, offer a challenging scenario for these techniques.While the dimensions and sizes of the systems amenable to TNS studies are still far from those achievable by 4-dimensional LGT tools, Tensor Networks can be readily used for problems which more standard techniques, such as Markov chain Monte Carlo simulations, cannot easily tackle.Examples of such problems are the presence of a chemical potential or out-of-equilibrium dynamics.We have explored the performance of Matrix Product States in the case of the Schwinger model, as a widely used testbench for lattice techniques.Using finite-size, open boundary MPS, we are able to determine the low energy states of the model in a fully non-perturbative manner.The precision achieved by the method allows for accurate finite size and continuum limit extrapolations of the ground state energy, but also of the chiral condensate and the mass gaps, thus showing the feasibility of these techniques for gauge theory problems.
The Thesis explores the application of Matrix Product States (MPS) in the domain of quantum many-body systems and quantum computing, show casing the versatility and effectiveness of MPS for addressing complex com putational challenges. The opening chapter introduces essential tools for Tensor Networks, addressing the curse of dimensionality and elucidating the main characteristics of Matrix Product States and Matrix Product Op erators. The discussion encompasses also important numerical techniques, including Density Matrix Renormalization Group and Time Evolving Block Decimation. Furthermore, the relation between MPS and quantum circuits is discussed. The subsequent Chapters delve into specific applications of MPS. In the second Chapter, we introduce a Tensor Network ansatz inspired by the backflow transformation for correlated systems. This extension of the MPS representation ensures an area law for entanglement in dimensions one or greater. We employ an optimization scheme combining DMRG and variational Monte Carlo algorithms for efficient ground-state search. Bench marking against spin models demonstrates high accuracy. The third Chapter explores quantum annealing for optimizing complex classical spin Hamil tonians, as the Hopfield model and the binary perceptron. We introduce an efficient Tensor Network representation for the adiabatic time evolution of quantum annealing, enabling scalable classical simulations. The use of MPS in mitigating Trotter errors and mapping to quantum circuits is also explored. In the fourth Chapter we present a novel method for evaluating the amount of nonstabilizerness (also known as quantum magic) contained in an MPS. We overcome the exponentially hard evaluation of this quan tity by employing a simple perfect sampling technique of Pauli string. Our innovative MPS approach enables efficient computation. Benchmarked on magic states and the quantum Ising chain ground state, this method offers easy access to the non-equilibrium dynamics of nonstabilizerness following a quantum quench. The Appendices provide additional insights, including: an introduction to variational Monte Carlo, technical details on MPS simula tions for the quantum annealing and a comprehensive overview on stabilizer formalism and nonstabilizerness.
<!--HTML-->*Theory Colloquium* The term Tensor Network States (TNS) designates a number of ansatzes that can efficiently represent certain states of quantum many-body systems. In particular, ground states and thermal equilibrium of local Hamiltonians, and, to some extent, real time evolution can be numerically studied with TNS methods. Quantum information theory provides tools to understand why they are good ansatzes for physically relevant states, and some of the limitations connected to the simulation algorithms. Originally introduced in the context of condensed matter physics, these methods have become a state-of-the-art technique for strongly correlated one-dimensional systems. Their applicability extends nevertheless to other fields. As an example, in the last few years it has been shown that TNS are also suitable to study lattice gauge theories and other quantum field problems. This talk gives an overview of the possibilities and limitations of these methods, and some of their recent applications to this kind of problems.
Abstract Understanding extreme non-locality in many-body quantum systems can help resolve questions in thermostatistics and laser physics. The existence of symmetry selection rules for Hamiltonians with non-decaying terms on infinite-size lattices can lead to finite energies per site, which deserves attention. Here, we present a tensor network approach to construct the ground states of nontrivial symmetric infinite-dimensional spin Hamiltonians based on constrained optimizations of their infinite matrix product states description, which contains no truncation step, offers a very simple mathematical structure, and other minor advantages at the cost of slightly higher polynomial complexity in comparison to an existing method. More precisely speaking, our proposed algorithm is in part equivalent to the more generic and well-established solvers of infinite density-matrix renormalization-group and variational uniform matrix product states, which are, in principle, capable of accurately representing the ground states of such infinite-range-interacting many-body systems. However, we employ some mathematical simplifications that would allow for efficient brute-force optimizations of tensor-network matrices for the specific cases of highly-symmetric infinite-size infinite-range models. As a toy-model example, we showcase the effectiveness and explain some features of our method by finding the ground state of the U(1)-symmetric infinite-dimensional antiferromagnetic XX Heisenberg model.
Tensor networks are an important tool in condensed matter physics. In this paper, we study the task of tensor network non-zero testing (\tnit): Given a tensor network T, does T represent a non-zero vector? We show that \tnit~is not in the Polynomial-Time Hierarchy unless the hierarchy collapses. We next show (among other results) that the special cases of \tnit~on non-negative and injective tensor networks are in NP. Using this, we make a simple observation: The commuting variant of the MA-complete stoquastic k-SAT problem on D-dimensional qudits is in NP for k∈O(logn) and D∈O(1). This reveals the first class of quantum Hamiltonians whose commuting variant is known to be in NP for all (1) logarithmic k, (2) constant D, and (3) for arbitrary interaction graphs.
This is a set of lectures on tensor networks with a strong emphasis on the core algorithms involving Matrix Product States (MPS) and Matrix Product Operators (MPO). Compared to other presentations, particular care has been given to disentangle aspects of tensor networks from the quantum many-body problem: MPO/MPS algorithms are presented as a way to deal with linear algebra on extremely (exponentially) large matrices and vectors, regardless of any particular application. The lectures include well-known algorithms to find eigenvectors of MPOs (the celebrated DMRG), solve linear problems, and recent learning algorithms that allow one to map a known function into an MPS (the Tensor Cross Interpolation, or TCI, algorithm). The lectures end with a discussion of how to represent functions and perform calculus with tensor networks using the "quantics" representation. They include the detailed analytical construction of important MPOs such as those for differentiation, indefinite integration, convolution, and the quantum Fourier transform. Three concrete applications are discussed in detail: the simulation of a quantum computer (either exactly or with compression), the simulation of a quantum annealer, and techniques to solve partial differential equations (e.g. Poisson, diffusion, or Gross-Pitaevskii) within the "quantics" representation. The lectures have been designed to be accessible to a first-year PhD student and include detailed proofs of all statements.