Search

We introduce regular language states, a family of quantum many-body states. They are built from a special class of formal languages, called regular, which has been thoroughly studied in the field of computer science. They can be understood as the superposition of all the words in a regular language and encompass physically relevant states such as the GHZ-, W- or Dicke-states. By leveraging the theory of regular languages, we develop a theoretical framework to describe them. First, we express them in terms of matrix product states, providing efficient criteria to recognize them. We then develop a canonical form which allows us to formulate a fundamental theorem for the equivalence of regular language states, including under local unitary operations. We also exploit the theory of tensor networks to find an efficient criterion to determine when regular languages are shift-invariant., Comment: 12 pages, 1 figure

Matrix-product unitaries (MPU) are 1D tensor networks describing time evolution and unitary symmetries of quantum systems. MPU which are formed by a single repeated tensor are known to coincide with 1D quantum cellular automata (QCA), i.e., unitaries with an exact light cone. However, this correspondence breaks down for MPU with open boundary conditions, even if the resulting operator is translation-invariant. Here we make the first steps towards a theory of MPU with uniform bulk but arbitrary boundary. In particular, we study the structure of a subclass with a direct-sum form which maximally violates the QCA property. We also consider the general case of MPU formed by site-dependent (nonuniform) tensors and show a correspondence between MPU and locally maximally entanglable states.

The accessibility of the Hawking-Page transition in AdS$_5$ through a 1d Heisenberg spin chain is demonstrated. We use the random matrix formulation of the Loschmidt echo for a set of spin chains, and randomize the ferromagnetic spin interaction. It is shown that the thermal Loschmidt echo, when averaged, detects the predicted increase in entropy across the Hawking-Page transition. This suggests that a 1d spin chain exhibits characteristics of black hole physics in 4+1 dimensions. We show that this approach is equally applicable to free fermion systems with a general dispersion relation., Comment: 5+13 pages, 2+3 figures. v2: minor improvements, references added, published version

We investigate the link between quantum position-verification (QPV) and holography established in [MPS19] using holographic quantum error correcting codes as toy models. By inserting the "temporal" scaling of the AdS metric by hand via the bulk Hamiltonian interaction strength, we recover a toy model with consistent causality structure. This leads to an interesting implication between two topics in quantum information: if position-based verification is secure against attacks with small entanglement then there are new fundamental lower bounds for resources required for one Hamiltonian to simulate another., Comment: (v2: updated presentation)

Tensor networks are factorizations of high-dimensional tensors into networks of smaller tensors. They have applications in physics and mathematics, and recently have been proposed as promising machine learning architectures. To ease the integration of tensor networks in machine learning pipelines, we introduce TensorKrowch, an open source Python library built on top of PyTorch. Providing a user-friendly interface, TensorKrowch allows users to construct any tensor network, train it, and integrate it as a layer in more intricate deep learning models. In this paper, we describe the main functionality and basic usage of TensorKrowch, and provide technical details on its building blocks and the optimizations performed to achieve efficient operation., Comment: 20 pages, 2 figures. The TensorKrowch GitHub repository is in https://github.com/joserapa98/tensorkrowch and the TensorKrowch documentation is in https://joserapa98.github.io/tensorkrowch. V3: Accepted version, corrected acknowledgments

Within the setting of the AdS/CFT correspondence, we ask about the power of computers in the presence of gravity. We show that there are computations on $n$ qubits which cannot be implemented inside of black holes with entropy less than $O(2^n)$. To establish our claim, we argue computations happening inside the black hole must be implementable in a programmable quantum processor, so long as the inputs and description of the unitary to be run are not too large. We then prove a bound on quantum processors which shows many unitaries cannot be implemented inside the black hole, and further show some of these have short descriptions and act on small systems. These unitaries with short descriptions must be computationally forbidden from happening inside the black hole.

Tensor networks have a gauge degree of freedom on the virtual degrees of freedom that are contracted. A canonical form is a choice of fixing this degree of freedom. For matrix product states, choosing a canonical form is a powerful tool, both for theoretical and numerical purposes. On the other hand, for tensor networks in dimension two or greater there is only limited understanding of the gauge symmetry. Here we introduce a new canonical form, the minimal canonical form, which applies to projected entangled pair states (PEPS) in any dimension, and prove a corresponding fundamental theorem. Already for matrix product states this gives a new canonical form, while in higher dimensions it is the first rigorous definition of a canonical form valid for any choice of tensor. We show that two tensors have the same minimal canonical forms if and only if they are gauge equivalent up to taking limits; moreover, this is the case if and only if they give the same quantum state for any geometry. In particular, this implies that the latter problem is decidable - in contrast to the well-known undecidability for PEPS on grids. We also provide rigorous algorithms for computing minimal canonical forms. To achieve this we draw on geometric invariant theory and recent progress in theoretical computer science in non-commutative group optimization., Comment: 51 pages, more than 8 figures

We uncover a novel dynamical quantum phase transition, using random matrix theory and its associated notion of planar limit. We study it for the isotropic XY Heisenberg spin chain. For this, we probe its real-time dynamics through the Loschmidt echo. This leads to the study of a random matrix ensemble with a complex weight, whose analysis requires novel technical considerations, that we develop. We obtain three main results: 1) There is a third order phase transition at a rescaled critical time, that we determine. 2) The third order phase transition persists away from the thermodynamic limit. 3) For times below the critical value, the difference between the thermodynamic limit and a finite chain decreases exponentially with the system size. All these results depend in a rich manner on the parity of the number of flipped spins of the quantum state conforming the fidelity., Comment: v2: 60 pages, 18 figures, published version

The classification of topological phases of matter is fundamental to understand and characterize the properties of quantum materials. In this paper we study phases of matter in one-dimensional open quantum systems. We define two mixed states to be in the same phase if both states can be transformed into the other by a shallow circuit of local quantum channels. We aim to understand the phase diagram of matrix product density operators that are renormalization fixed points. These states arise, for example, as boundaries of two-dimensional topologically ordered states. We first construct families of such states based on C*-weak Hopf algebras, the algebras whose representations form a fusion category. More concretely, we provide explicit local fine-graining and local coarse-graining quantum channels for the renormalization procedure of these states. Finally, we prove that those arising from C*-Hopf algebras are in the trivial phase.

Matrix Product Operators (MPOs) are tensor networks representing operators acting on 1D systems. They model a wide variety of situations, including communication channels with memory effects, quantum cellular automata, mixed states in 1D quantum systems, or holographic boundary models associated to 2D quantum systems. A scenario where MPOs have proven particularly useful is to represent algebras of non-trivial symmetries. Concretely, the boundary of both symmetry protected and topologically ordered phases in 2D quantum systems exhibit symmetries in the form of MPOs. In this paper, we develop a theory of MPOs as representations of algebraic structures. We establish a dictionary between algebra and MPO properties which allows to transfer results between both setups, covering the cases of pre-bialgebras, weak bialgebras, and weak Hopf algebras. We define the notion of pulling-through algebras, which abstracts the minimal requirements needed to define topologically ordered 2D tensor networks from MPO algebras. We show, as one of our main results, that any semisimple pivotal weak Hopf algebra is a pulling-trough algebra. We demonstrate the power of this framework by showing that they can be used to construct Kitaev's quantum double models for Hopf algebras solely from an MPO representation of the Hopf algebra, in the exact same way as MPO symmetries obtained from fusion categories can be used to construct Levin-Wen string-net models, and to explain all their topological features; it thus allows to describe both Kitaev and string-net models on the same formal footing.

Tensor networks, widely used for providing efficient representations of low-energy states of local quantum many-body systems, have been recently proposed as machine learning architectures which could present advantages with respect to traditional ones. In this work we show that tensor network architectures have especially prospective properties for privacy-preserving machine learning, which is important in tasks such as the processing of medical records. First, we describe a new privacy vulnerability that is present in feedforward neural networks, illustrating it in synthetic and real-world datasets. Then, we develop well-defined conditions to guarantee robustness to such vulnerability, which involve the characterization of models equivalent under gauge symmetry. We rigorously prove that such conditions are satisfied by tensor-network architectures. In doing so, we define a novel canonical form for matrix product states, which has a high degree of regularity and fixes the residual gauge that is left in the canonical forms based on singular value decompositions. We supplement the analytical findings with practical examples where matrix product states are trained on datasets of medical records, which show large reductions on the probability of an attacker extracting information about the training dataset from the model's parameters. Given the growing expertise in training tensor-network architectures, these results imply that one may not have to be forced to make a choice between accuracy in prediction and ensuring the privacy of the information processed., Comment: 16 pages, 2 figures. Quantumarticle 6.1. The computational appendix is available at https://www.github.com/apozas/private-tn V3: Published version

Quantum computing is the process of performing calculations using quantum mechanics. This field studies the quantum behavior of certain subatomic particles for subsequent use in performing calculations, as well as for large-scale information processing. These capabilities can give quantum computers an advantage in terms of computational time and cost over classical computers. Nowadays, there are scientific challenges that are impossible to perform by classical computation due to computational complexity or the time the calculation would take, and quantum computation is one of the possible answers. However, current quantum devices have not yet the necessary qubits and are not fault-tolerant enough to achieve these goals. Nonetheless, there are other fields like machine learning or chemistry where quantum computation could be useful with current quantum devices. This manuscript aims to present a Systematic Literature Review of the papers published between 2017 and 2023 to identify, analyze and classify the different algorithms used in quantum machine learning and their applications. Consequently, this study identified 94 articles that used quantum machine learning techniques and algorithms. The main types of found algorithms are quantum implementations of classical machine learning algorithms, such as support vector machines or the k-nearest neighbor model, and classical deep learning algorithms, like quantum neural networks. Many articles try to solve problems currently answered by classical machine learning but using quantum devices and algorithms. Even though results are promising, quantum machine learning is far from achieving its full potential. An improvement in the quantum hardware is required since the existing quantum computers lack enough quality, speed, and scale to allow quantum computing to achieve its full potential., Comment: 28 pages, 25 figures

Given a finite-range, translation-invariant commuting system Hamiltonians on a spin chain, we show that the Davies semigroup describing the reduced dynamics resulting from the joint Hamiltonian evolution of a spin chain weakly coupled to a large heat bath thermalizes rapidly at any temperature. More precisely, we prove that the relative entropy between any evolved state and the equilibrium Gibbs state contracts exponentially fast with an exponent that scales logarithmically with the length of the chain. Our theorem extends a seminal result of Holley and Stroock to the quantum setting, up to a logarithmic overhead, as well as provides an exponential improvement over the non-closure of the gap proved by Brandao and Kastoryano. This has wide-ranging applications to the study of many-body in and out-of-equilibrium quantum systems. Our proof relies upon a recently derived strong decay of correlations for Gibbs states of one dimensional, translation-invariant local Hamiltonians, and tools from the theory of operator spaces., Comment: 44 pages, 6 figures

We prove that spin chains weakly coupled to a large heat bath thermalize rapidly at any temperature for finite-range, translation-invariant commuting Hamiltonians, reaching equilibrium in a time which scales logarithmically with the system size. Our main result is a generalization to the quantum setting of a seminal result of Holley and Stroock for classical spin chains and represents an exponential improvement over bounds based on the non-closure of the spectral gap. From a physical point of view, our result rigorously establishes the absence of dissipative phase transition for Davies evolutions over translation-invariant spin chains. The result also applies in the case of Symmetry Protected Topological phases where the evolution is respecting the symmetry of the phase. This has wide-ranging applications to the study of many-body in and out-of-equilibrium quantum systems., Comment: 5 pages + 3 pages, 3 figures

We show that the Davies generator associated to any 2D Kitaev's quantum double model has a non-vanishing spectral gap in the thermodynamic limit. This validates rigorously the extended belief that those models are useless as self-correcting quantum memories, even in the non-abelian case. The proof uses recent ideas and results regarding the characterization of the spectral gap for parent Hamiltonians associated to Projected Entangled Pair States in terms of a bulk-boundary correspondence., Comment: 80 pages. The paper has been restructured significantly. Some proofs have been corrected and simplified, and additional details have been provided throughout the paper

We introduce a Metropolis-Hastings Markov chain for Boltzmann distributions of classical spin systems. It relies on approximate tensor network contractions to propose correlated collective updates at each step of the evolution. We present benchmarks for a wide variety of instances of the two-dimensional Ising model, including ferromagnetic, antiferromagnetic, (fully) frustrated and Edwards-Anderson spin glass cases, and we show that, with modest computational effort, our Markov chain achieves sizeable acceptance rates, even in the vicinity of critical points. In each of the situations we have considered, the Markov chain compares well with other Monte Carlo schemes such as the Metropolis or Wolff algorithm: equilibration times appear to be reduced by a factor that varies between 40 and 2000, depending on the model and the observable being monitored. We also present an extension to three spatial dimensions, and demonstrate that it exhibits fast equilibration for finite ferro and antiferromagnetic instances. Additionally, and although it is originally designed for a square lattice of finite degrees of freedom with open boundary conditions, the proposed scheme can be used as such, or with slight modifications, to study triangular lattices, systems with continuous degrees of freedom, matrix models, a confined gas of hard spheres, or to deal with arbitrary boundary conditions., Comment: 21 pages, 25 figures

In this work we initiate the study of Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a Position Verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above., Comment: Presentation substantially improved. A couple of sections were removed for the sake of conciseness and some clarifications added

The theory of entanglement provides a fundamentally new language for describing interactions and correlations in many body systems. Its vocabulary consists of qubits and entangled pairs, and the syntax is provided by tensor networks. We review how matrix product states and projected entangled pair states describe many-body wavefunctions in terms of local tensors. These tensors express how the entanglement is routed, act as a novel type of non-local order parameter, and we describe how their symmetries are reflections of the global entanglement patterns in the full system. We will discuss how tensor networks enable the construction of real-space renormalization group flows and fixed points, and examine the entanglement structure of states exhibiting topological quantum order. Finally, we provide a summary of the mathematical results of matrix product states and projected entangled pair states, highlighting the fundamental theorem of matrix product vectors and its applications., Comment: Review article. 72 pages

It is a generalized belief that there are no thermal phase transitions in short range 1D quantum systems. However, the only known case for which this is rigorously proven is for the particular case of finite range translational invariant interactions. The proof was obtained by Araki in his seminal paper of 1969 as a consequence of pioneering locality estimates for the time-evolution operator that allowed him to prove its analiticity on the whole complex plane, when applied to a local observable. However, as for now there is no mathematical proof of the abscence of 1D thermal phase transitions if one allows exponential tails in the interactions. In this work we extend Araki's result to include exponential (or faster) tails. Our main result is the analyticity of the time-evolution operator applied on a local observable on a suitable strip around the real line. As a consequence we obtain that thermal states in 1D exhibit exponential decay of correlations above a threshold temperature that decays to zero with the exponent of the interaction decay, recovering Araki's result as a particular case. Our result however still leaves open the possibility of 1D thermal short range phase transitions. We conclude with an application of our result to the spectral gap problem for Projected Entangled Pair States (PEPS) on 2D lattices, via the holographic duality due to Cirac et al., Comment: 38 pages

The mixing time of Markovian dissipative evolutions of open quantum many-body systems can be bounded using optimal constants of certain quantum functional inequalities, such as the modified logarithmic Sobolev constant. For classical spin systems, the positivity of such constants follows from a mixing condition for the Gibbs measure, via quasi-factorization results for the entropy. Inspired by the classical case, we present a strategy to derive the positivity of the modified logarithmic Sobolev constant associated to the dynamics of certain quantum systems from some clustering conditions on the Gibbs state of a local, commuting Hamiltonian. In particular we show that for the heat-bath dynamics for 1D systems, the modified logarithmic Sobolev constant is positive under the assumptions of a mixing condition on the Gibbs state and a strong quasi-factorization of the relative entropy., Comment: 28 pages, 4 figures. Included some additional comments and updated results in light of recent advances in the literature

Tensor network states are used extensively as a mathematically convenient description of physically relevant states of many-body quantum systems. Those built on regular lattices, i.e. matrix product states (MPS) in dimension 1 and projected entangled pair states (PEPS) in dimension 2 or higher, are of particular interest in condensed matter physics. The general goal of this work is to characterize which features of MPS and PEPS are generic and which are, on the contrary, exceptional. This problem can be rephrased as follows: given an MPS or PEPS sampled at random, what are the features that it displays with either high or low probability? One property which we are particularly interested in is that of having either rapidly decaying or long-range correlations. In a nutshell, our main result is that translation-invariant MPS and PEPS typically exhibit exponential decay of correlations at a high rate. We have two distinct ways of getting to this conclusion, depending on the dimensional regime under consideration. Both yield intermediate results which are of independent interest, namely: the parent Hamiltonian and the transfer operator of such MPS and PEPS typically have a large spectral gap. In all these statements, our aim is to get a quantitative estimate of the considered quantity (generic correlation length or spectral gap), which has the best possible dependency on the physical and bond dimensions of the random MPS or PEPS., Comment: 53 pages, 7 figures. v2: a bug in Section 4 has been fixed and a few changes have been made to the presentation. v3: published version

Projected Entangled Pair States (PEPS) are used in practice as an efficient parametrization of the set of ground states of quantum many body systems. The aim of this paper is to present, for a broad mathematical audience, some mathematical questions about PEPS., Comment: Notes associated to the Santal\'o Lecture 2017, Universidad Complutense de Madrid (UCM), minor typos corrected

We propose the following definition of topological quantum phases valid for mixed states: two states are in the same phase if there exists a time independent, fast and local Lindbladian evolution driving one state into the other. The underlying idea, motivated by K\"onig and Pastawski in 2013, is that it takes time to create new topological correlations, even with the use of dissipation. We show that it is a good definition in the following sense: (1) It divides the set of states into equivalent classes and it establishes a partial order between those according to their level of "topological complexity". (2) It provides a path between any two states belonging to the same phase where observables behave smoothly. We then focus on pure states to relate the new definition in this particular case with the usual definition for quantum phases of closed systems in terms of the existence of a gapped path of Hamiltonians connecting both states in the corresponding ground state path. We show first that if two pure states are in the same phase in the Hamiltonian sense, they are also in the same phase in the Lindbladian sense considered here. We then turn to analyse the reverse implication, where we point out a very different behaviour in the case of symmetry protected topological (SPT) phases in 1D. Whereas at the Hamiltonian level, phases are known to be classified with the second cohomology group of the symmetry group, we show that symmetry cannot give any protection in 1D in the Lindbladian sense: there is only one SPT phase in 1D independently of the symmetry group. We finish analysing the case of 2D topological quantum systems. There we expect that different topological phases in the Hamiltonian sense remain different in the Lindbladian sense. We show this formally only for the $\mathbb{Z}_n$ quantum double models., Comment: 46 pages, v3: published version

The spectral gap problem - determining whether the energy spectrum of a system has an energy gap above ground state, or if there is a continuous range of low-energy excitations - pervades quantum many-body physics. Recently, this important problem was shown to be undecidable for quantum spin systems in two (or more) spatial dimensions: there exists no algorithm that determines in general whether a system is gapped or gapless, a result which has many unexpected consequences for the physics of such systems. However, there are many indications that one dimensional spin systems are simpler than their higher-dimensional counterparts: for example, they cannot have thermal phase transitions or topological order, and there exist highly-effective numerical algorithms such as DMRG - and even provably polynomial-time ones - for gapped 1D systems, exploiting the fact that such systems obey an entropy area-law. Furthermore, the spectral gap undecidability construction crucially relied on aperiodic tilings, which are not possible in 1D. So does the spectral gap problem become decidable in 1D? In this paper we prove this is not the case, by constructing a family of 1D spin chains with translationally-invariant nearest neighbour interactions for which no algorithm can determine the presence of a spectral gap. This not only proves that the spectral gap of 1D systems is just as intractable as in higher dimensions, but also predicts the existence of qualitatively new types of complex physics in 1D spin chains. In particular, it implies there are 1D systems with constant spectral gap and non-degenerate classical ground state for all systems sizes up to an uncomputably large size, whereupon they switch to a gapless behaviour with dense spectrum., Comment: 7 figures

We consider a random time evolution operator composed of a circuit of random unitaries coupling even and odd neighboring spins on a chain in turn. In spirit of Floquet evolution, the circuit is time-periodic; each timestep is repeated with the same random instances. We obtain analytical results for arbitrary local Hilbert space dimension d: On a single site, average time evolution acts as a depolarising channel. In the spin 1/2 (d=2) case, this is further quantified numerically. For that, we develop a new numerical method that reduces complexity by an exponential factor. Haar-distributed unitaries lead to full depolarization after many timesteps, i.e. local thermalization. A unitary probability distribution with tunable coupling strength allows us to observe a many-body localization transition. In addition to a spin chain under a unitary circuit, we consider the analogous problem with Gaussian circuits. We can make stronger statements about the entire covariance matrix instead of single sites only, and find that the dynamics is localising. For a random time evolution operator homogeneous in space, however, the system delocalizes.

The no-programming theorem prohibits the existence of a Universal Programmable Quantum Processor. This statement has several implications in relation to quantum computation, but also to other tasks of quantum information processing, making this construction a central notion in this context. Nonetheless, it is well known that even when the strict model is not implementable, it is possible to conceive of it in an approximate sense. Unfortunately, the minimal resources necessary for this aim are still not completely understood. Here, we investigate quantitative statements of the theorem, improving exponentially previous bounds on the resources required by such a hypothetical machine. The proofs exploit a new connection between quantum channels and embeddings between Banach spaces which allows us to use classical tools from geometric Banach space theory in a clean and simple way., Comment: 14 (6+8) pages, 1 table. Changes implemented in order to match the published version

The existence of a positive log-Sobolev constant implies a bound on the mixing time of a quantum dissipative evolution under the Markov approximation. For classical spin systems, such constant was proven to exist, under the assumption of a mixing condition in the Gibbs measure associated to their dynamics, via a quasi-factorization of the entropy in terms of the conditional entropy in some sub-$\sigma$-algebras. In this work we analyze analogous quasi-factorization results in the quantum case. For that, we define the quantum conditional relative entropy and prove several quasi-factorization results for it. As an illustration of their potential, we use one of them to obtain a positive log-Sobolev constant for the heat-bath dynamics with product fixed point., Comment: v2: Final version, minor changes, 39 pages, 2 figures

Tensor networks are generated by a set of small rank tensors and define many-body quantum states in a succinct form. The corresponding map is not one-to-one: different sets of tensors may generate the very same state. A fundamental question in the study of tensor networks naturally arises: what is then the relation between those sets? The answer to this question in one dimensional setups has found several applications, like the characterization of local and global symmetries, the classification of phases of matter and unitary evolutions, or the determination of the fixed points of renormalization procedures. Here we answer this question for projected entangled-pair states (PEPS) in any dimension and lattice geometry, as long as the tensors generating the states are normal, which constitute an important and generic class.

Proving that the parent Hamiltonian of a Projected Entangled Pair State (PEPS) is gapped remains an important open problem. We take a step forward in solving this problem by showing two results: first, we identify an approximate factorization condition on the boundary state of rectangular subregions that is sufficient to prove that the parent Hamiltonian of the bulk 2D PEPS has a constant gap in the thermodynamic limit; second, we then show that Gibbs state of a local, finite-range Hamiltonian satisfy such condition. The proof applies to the case of injective and MPO-injective PEPS, employs the martingale method of nearly commuting projectors, and exploits a result of Araki on the robustness of one dimensional Gibbs states. Our result provides one of the first rigorous connections between boundary theories and dynamical properties in an interacting many body system., Comment: 31 pages, 9 figures. Revised version

We determine which translationally invariant matrix product states have a continuum limit, that is, which can be considered as discretized versions of states defined in the continuum. To do this, we analyse a fine-graining renormalization procedure in real space, characterise the set of limiting states of its flow, and find that it strictly contains the set of continuous matrix product states. We also analyse which states have a continuum limit after a finite number of a coarse-graining renormalization steps. We give several examples of states with and without the different kinds of continuum limits., Comment: 7 pages, 2 figures. New version: somewhat expanded, some explanations added. Close to published version

The canonical form of Matrix Product States (MPS) and the associated fundamental theorem, which relates different MPS representations of a state, are the theoretical framework underlying many of the analytical results derived through MPS, such as the classification of symmetry-protected phases in one dimension. Yet, the canonical form is only defined for MPS without non-trivial periods, and thus cannot fully capture paradigmatic states such as the antiferromagnet. Here, we introduce a new standard form for MPS, the irreducible form, which is defined for arbitrary MPS, including periodic states, and show that any tensor can be transformed into a tensor in irreducible form describing the same MPS. We then prove a fundamental theorem for MPS in irreducible form: If two tensors in irreducible form give rise to the same MPS, then they must be related by a similarity transform, together with a matrix of phases. We provide two applications of this result: an equivalence between the refinement properties of a state and the divisibility properties of its transfer matrix, and a more general characterisation of tensors that give rise to matrix product states with symmetries., Comment: 12 pages

The property of superadditivity of the quantum relative entropy states that, in a bipartite system $\mathcal{H}_{AB}=\mathcal{H}_A \otimes \mathcal{H}_B$, for every density operator $\rho_{AB}$ one has $ D( \rho_{AB} || \sigma_A \otimes \sigma_B ) \ge D( \rho_A || \sigma_A ) +D( \rho_B || \sigma_B) $. In this work, we provide an extension of this inequality for arbitrary density operators $ \sigma_{AB} $. More specifically, we prove that $ \alpha (\sigma_{AB})\cdot D({\rho_{AB}}||{\sigma_{AB}}) \ge D({\rho_A}||{\sigma_A})+D({\rho_B}||{\sigma_B})$ holds for all bipartite states $\rho_{AB}$ and $\sigma_{AB}$, where $\alpha(\sigma_{AB})= 1+2 || \sigma_A^{-1/2} \otimes \sigma_B^{-1/2} \, \sigma_{AB} \, \sigma_A^{-1/2} \otimes \sigma_B^{-1/2} - \mathbb{1}_{AB} ||_\infty$., Comment: 14 pages. v3: Final version. The main theorem has been improved, adding a fourth step to its proof and also some remarks. v2: There was a flaw in the proof of the previous version. This has been corrected in this version. The constant appearing in the main Theorem has changed accordingly

Matrix Product Vectors form the appropriate framework to study and classify one-dimensional quantum systems. In this work, we develop the structure theory of Matrix Product Unitary operators (MPUs) which appear e.g. in the description of time evolutions of one-dimensional systems. We prove that all MPUs have a strict causal cone, making them Quantum Cellular Automata (QCAs), and derive a canonical form for MPUs which relates different MPU representations of the same unitary through a local gauge. We use this canonical form to prove an Index Theorem for MPUs which gives the precise conditions under which two MPUs are adiabatically connected, providing an alternative derivation to that of [Commun. Math. Phys. 310, 419 (2012), arXiv:0910.3675] for QCAs. We also discuss the effect of symmetries on the MPU classification. In particular, we characterize the tensors corresponding to MPU that are invariant under conjugation, time reversal, or transposition. In the first case, we give a full characterization of all equivalence classes. Finally, we give several examples of MPU possessing different symmetries., Comment: v2: Minor corrections. See also the related work arXiv:1704.01943 by Sahinoglu et al

Topological ordered phases are related to changes in the properties of their quasi-particle excitations (anyons). We study these relations in the framework of projected entanglement pair states (\textsf{PEPS}) and show how condensing and confining anyons reduces a local gauge symmetry to a global on-site symmetry. We also study the action of this global symmetry over the quasiparticle excitations. As a byproduct, we observe that this symmetry reduction effect can be applied to one-dimensional systems as well, and brings about appealing physical interpretations on the classification of phases with symmetries using matrix product states (\textsf{MPS}). The case of $\mathbb{Z}_2$ on-site symmetry is studied in detail., Comment: 21+5 pages, 15+3 figures. Introduction and conclusions enlarged, references and figure added, minor typos corrected, appendix about dyons added

Symmetrization of topologically ordered wavefunctions is a powerful method for constructing new topological models. Here, we study wavefunctions obtained by symmetrizing quantum double models of a group $G$ in the Projected Entangled Pair States (PEPS) formalism. We show that symmetrization naturally gives rise to a larger symmetry group $\tilde G$ which is always non-abelian. We prove that by symmetrizing on sufficiently large blocks, one can always construct wavefunctions in the same phase as the double model of $\tilde G$. In order to understand the effect of symmetrization on smaller patches, we carry out numerical studies for the toric code model, where we find strong evidence that symmetrizing on individual spins gives rise to a critical model which is at the phase transitions of two inequivalent toric codes, obtained by anyon condensation from the double model of $\tilde G$., Comment: 10 pages. v2: accepted version

The aim of this short note is to clarify some of the claims made in the comparison made in [S. Lloyd, On the uncomputability of the spectral gap, arXiv:1602.05924] between our recent result [T.S. Cubitt, D. Perez-Garcia, M.M. Wolf, Undecidability of the spectral gap, Nature 528, 207-211 (2015), arXiv:1502.04573] and his 1994 paper [S. Lloyd, Necessary and sufficient conditions for quantum computation, J. Mod. Opt. 41(12), 2503-2520 (1994)].

Most communication channels are subjected to noise. One of the goals of Information Theory is to add redundancy in the transmission of information so that the information is transmitted reliably and the amount of information transmitted through the channel is as large as possible. The maximum rate at which reliable transmission is possible is called the capacity. If the channel does not keep memory of its past, the capacity is given by a simple optimization problem and can be efficiently computed. The situation of channels with memory is less clear. Here we show that for channels with memory the capacity cannot be computed to within precision 1/5. Our result holds even if we consider one of the simplest families of such channels -information-stable finite state machine channels-, restrict the input and output of the channel to 4 and 1 bit respectively and allow 6 bits of memory., Comment: Improved presentation and clarified claims

Can the properties of the thermodynamic limit of a many-body quantum system be extrapolated by analysing a sequence of finite-size cases? We present a model for which such an approach gives completely misleading results: a translationally invariant, local Hamiltonian on a square lattice with open boundary conditions and constant spectral gap, which has a classical product ground state for all system sizes smaller than a particular threshold size, but a ground state with topological degeneracy for all system sizes larger than this threshold. Starting from a minimal case with spins of dimension 6 and threshold lattice size 15 x 15, we show that the latter grows faster than any computable function with increasing local spin dimension. The resulting effect may be viewed as a new type of quantum phase transition that is driven by the size of the system rather than by an external field or coupling strength. We prove that the construction is thermally robust, opening the possibility that these effects are accessible to experimental observation., Comment: 20 pages. Final version

We prove an area law with a logarithmic correction for the mutual information for fixed points of local dissipative quantum system satisfying a rapid mixing condition, under either of the following assumptions: the fixed point is pure, or the system is frustration free., Comment: 17 pages, 1 figure. Final version

We show that the spectral gap problem is undecidable. Specifically, we construct families of translationally-invariant, nearest-neighbour Hamiltonians on a 2D square lattice of d-level quantum systems (d constant), for which determining whether the system is gapped or gapless is an undecidable problem. This is true even with the promise that each Hamiltonian is either gapped or gapless in the strongest sense: it is promised to either have continuous spectrum above the ground state in the thermodynamic limit, or its spectral gap is lower-bounded by a constant in the thermodynamic limit. Moreover, this constant can be taken equal to the local interaction strength of the Hamiltonian., Comment: v1: 146 pages, 56 theorems etc, 15 figs. See shorter companion paper arXiv:1502.04135 for version omitting technical details. v2: Small fix to abstract wording. v3: Simplified and shortened parts of proof. 127p, 55 thms, 10 figs. v4: Minor intro edits. v5: Published version. Adds explanatory pseudo-code for all Turing Machines, and other presentational improvements. 150 pages, 55 thms, 13 figs

The spectral gap - the energy difference between the ground state and first excited state - is central to quantum many-body physics. Many challenging open problems, such as the Haldane conjecture, existence of gapped topological spin liquid phases, or the Yang-Mills gap conjecture, concern spectral gaps. These and other problems are particular cases of the general spectral gap problem: given a quantum many-body Hamiltonian, is it gapped or gapless? Here we prove that this is an undecidable problem. We construct families of quantum spin systems on a 2D lattice with translationally-invariant, nearest-neighbour interactions for which the spectral gap problem is undecidable. This result extends to undecidability of other low energy properties, such as existence of algebraically decaying ground-state correlations. The proof combines Hamiltonian complexity techniques with aperiodic tilings, to construct a Hamiltonian whose ground state encodes the evolution of a quantum phase-estimation algorithm followed by a universal Turing Machine. The spectral gap depends on the outcome of the corresponding Halting Problem. Our result implies that there exists no algorithm to determine whether an arbitrary model is gapped or gapless. It also implies that there exist models for which the presence or absence of a spectral gap is independent of the axioms of mathematics., Comment: v2: published version. 7 pages, 3 figures. See long companion paper arXiv:1502.04573 (same title and authors) for full technical details. v3: Added supplementary material as ancilliary file (previously part of arXiv:1502.04573v2)

The physics of many materials is modeled by quantum many-body systems with local interactions. If the model of the system is sensitive to noise from the environment, or small perturbations to the original interactions, it will not properly model the robustness of the real physical system it aims to describe, or be useful when engineering novel systems for quantum information processing. We show that local observables and correlation functions of local Liouvillians are stable to local perturbations if the dynamics is rapidly mixing and has a unique fixed point. No other condition is required., Comment: 5 pages, 1 figure. Final version

Transmitting data reliably over noisy communication channels is one of the most important applications of information theory, and well understood when the channel is accurately modelled by classical physics. However, when quantum effects are involved, we do not know how to compute channel capacities. The capacity to transmit quantum information is essential to quantum cryptography and computing, but the formula involves maximising the coherent information over arbitrarily many channel uses. This is because entanglement across channel uses can increase the coherent information, even from zero to non-zero! However, in all known examples, at least to detect whether the capacity is non-zero, two channel uses already suffice. Maybe a finite number of channel uses is always sufficient? Here, we show this is emphatically not the case: for any n, there are channels for which the coherent information is zero for n uses, but which nonetheless have capacity. This may be a first indication that the quantum capacity is uncomputable., Comment: 11 pages, 1 figure

We construct a 1d spin chain Hamiltonian with generic interactions and prove that the thermal correlation functions of the model admit an explicit random matrix representation. As an application of the result, we show how the observables of $U(N)$ Chern-Simons theory on $S^{3}$ can be reproduced with the thermal correlation functions of the 1d spin chain, which is of the XX type, with a suitable choice of exponentially decaying interactions between infinitely many neighbours. We show that for this model, the correlation functions of the spin chain at a finite temperature $\beta =1$ give the Chern-Simons partition function, quantum dimensions and the full topological $S$-matrix., Comment: v2, 11 pages. Expanded, more detailed version. Misprints corrected

We analyze the description of quantum many-body mixed states using matrix product states and operators. We consider two such descriptions: (i) as a matrix product density operator of bond dimension D, and (ii) as a purification that is written as a matrix product state of bond dimension D'. We show that these descriptions are inequivalent in the sense that D' cannot be upper bounded by D only. Then we provide two constructive methods to obtain (ii) out of (i). The sum of squares (sos) polynomial method scales exponentially in the number of different eigenvalues, and its approximate version is formulated as a Semidefinite Program, which gives efficient approximate purifications whose D' only depends on D. The eigenbasis method scales quadratically in the number of eigenvalues, and its approximate version is very efficient for rapidly decaying distributions of eigenvalues. Our results imply that a description of mixed states which is both efficient and locally positive semidefinite does not exist, but that good approximations do., Comment: 11 pages (+3 of appendices), 10 figures. Minor changes; very similar to published version

By using random matrix models we uncover a connection between the low energy sector of four dimensional QCD at finite volume and the Heisenberg XX model in a 1d spin chain. This connection allows to relate crucial properties of QCD with physically meaningful properties of the spin chain, establishing a dictionary between both worlds. We predict for the spin chain a third-order phase transition and a Tracy-Widom law in the transition region. We postulate that this dictionary goes beyond the particular example analyzed here and can be applied to other QFT and spin chain models. We finally comment on possible numerical implications of the connection as well as on possible experimental implementations., Comment: 12 pages. v3 Final version to appear in Phys. Rev. X; discussion on experimental accessibility extended; title modified in journal

Open quantum systems weakly coupled to the environment are modeled by completely positive, trace preserving semigroups of linear maps. The generators of such evolutions are called Lindbladians. In the setting of quantum many-body systems on a lattice it is natural to consider Lindbladians that decompose into a sum of local interactions with decreasing strength with respect to the size of their support. For both practical and theoretical reasons, it is crucial to estimate the impact that perturbations in the generating Lindbladian, arising as noise or errors, can have on the evolution. These local perturbations are potentially unbounded, but constrained to respect the underlying lattice structure. We show that even for polynomially decaying errors in the Lindbladian, local observables and correlation functions are stable if the unperturbed Lindbladian has a unique fixed point and a mixing time which scales logarithmically with the system size. The proof relies on Lieb-Robinson bounds, which describe a finite group velocity for propagation of information in local systems. As a main example, we prove that classical Glauber dynamics is stable under local perturbations, including perturbations in the transition rates which may not preserve detailed balance., Comment: 38 pages, 3 figures. Final version

Simulating of exotic phases of matter that are not amenable to classical techniques is one of the most important potential applications of quantum information processing. We present an efficient algorithm for preparing a large class of topological quantum states -- the G-injective Projected Entangled Pair States (PEPS) -- on a quantum computer. Important examples include the resonant valence bond (RVB) states, conjectured to be topological spin liquids. The runtime of the algorithm scales polynomially with the condition number of the PEPS projectors, and inverse-polynomially in the spectral gap of the PEPS parent Hamiltonian., Comment: 7 pages, 2 figures, REVTeX format

For every Matrix Product State (MPS) one can always construct a so-called parent Hamiltonian. This is a local, frustration free, Hamiltonian which has the MPS as ground state and is gapped. Whenever that parent Hamiltonian has a degenerate ground state (the so-called non-injective case), we construct another 'uncle' Hamiltonian which is local and frustration free but gapless, and its spectrum is $\R^+$. The construction is obtained by linearly perturbing the matrices building up the state in a random direction, and then taking the limit where the perturbation goes to zero. For MPS where the parent Hamiltonian has a unique ground state (the so-called injective case) we also build such uncle Hamiltonian with the same properties in the thermodynamic limit., Comment: 36 pages, new version with some contents rearranged, and a correction in the injective case

We study the structure of topological phases and their boundaries in the Projected Entangled Pair States (PEPS) formalism. We show how topological order in a system can be identified from the structure of the PEPS transfer operator, and subsequently use these findings to analyze the structure of the boundary Hamiltonian, acting on the bond variables, which reflects the entanglement properties of the system. We find that in a topological phase, the boundary Hamiltonian consists of two parts: A universal non-local part which encodes the nature of the topological phase, and a non-universal part which is local and inherits the symmetries of the topological model, which helps to infer the structure of the boundary Hamiltonian and thus possibly of the physical edge modes., Comment: 4+2 pages, 4+1 figures. v2: Major improvements and additions, with the focus shifted towards the transfer operator. Paper largely rewritten and significantly extended, title changed. v3: Minor changes, accepted version, Journal-Ref added