Source author record

David Perez-Garcia

David Perez-Garcia appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

28works
13topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

28 published item(s)

preprint2022arXiv

Undecidability of the Spectral Gap (full 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.

preprint2020arXiv

Undecidability of the Spectral Gap in One Dimension

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.

preprint2016arXiv

Comment on "On the uncomputability of the spectral gap"

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)].

preprint2016arXiv

Constructing topological models by symmetrization: A PEPS study

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$.

preprint2015arXiv

Stability of local quantum dissipative systems

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.

preprint2014arXiv

Entanglement and the three-dimensionality of the Bloch ball

We consider a very natural generalization of quantum theory by letting the dimension of the Bloch ball be not necessarily three. We analyze bipartite state spaces where each of the components has a d-dimensional Euclidean ball as state space. In addition to this we impose two very natural assumptions: the continuity and reversibility of dynamics, and the possibility of characterizing bipartite states by local measurements. We classify all these bipartite state spaces and prove that, except for the quantum two-qubit state space, none of them contains entangled states. Equivalently, in any of these non-quantum theories interacting dynamics is impossible. This result reveals that "existence of entanglement" is the requirement with minimal logical content which singles out quantum theory from our family of theories.

preprint2014arXiv

Unbounded number of channel uses are required to see quantum capacity

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.

preprint2013arXiv

Existence of an information unit as a postulate of quantum theory

Does information play a significant role in the foundations of physics? Information is the abstraction that allows us to refer to the states of systems when we choose to ignore the systems themselves. This is only possible in very particular frameworks, like in classical or quantum theory, or more generally, whenever there exists an information unit such that the state of any system can be reversibly encoded in a sufficient number of such units. In this work we show how the abstract formalism of quantum theory can be deduced solely from the existence of an information unit with suitable properties, together with two further natural assumptions: the continuity and reversibility of dynamics, and the possibility of characterizing the state of a composite system by local measurements. This constitutes a new set of postulates for quantum theory with a simple and direct physical meaning, like the ones of special relativity or thermodynamics, and it articulates a strong connection between physics and information.

preprint2013arXiv

Testing microscopic discretization

What can we say about the spectra of a collection of microscopic variables when only their coarse-grained sums are experimentally accessible? In this paper, using the tools and methodology from the study of quantum nonlocality, we develop a mathematical theory of the macroscopic fluctuations generated by ensembles of independent microscopic discrete systems. We provide algorithms to decide which multivariate gaussian distributions can be approximated by sums of finitely-valued random vectors. We study non-trivial cases where the microscopic variables have an unbounded range, as well as asymptotic scenarios with infinitely many macroscopic variables. From a foundational point of view, our results imply that bipartite gaussian states of light cannot be understood as beams of independent d-dimensional particle pairs. It is also shown that the classical description of certain macroscopic optical experiments, as opposed to the quantum one, requires variables with infinite cardinality spectra.

preprint2013arXiv

Topological order in PEPS: Transfer operator and boundary Hamiltonians

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.

preprint2012arXiv

An order parameter for symmetry-protected phases in one dimension

We introduce an order parameter for symmetry-protected phases in one dimension which allows to directly identify those phases. The order parameter consists of string-like operators and swaps, but differs from conventional string order operators in that it only depends on the symmetry but not on the state. We verify our framework through numerical simulations for the SO(3) invariant spin-1 bilinear-biquadratic model which exhibits a dimerized and a Haldane phase, and find that the order parameter not only works very well for the dimerized and the Haldane phase, but it also returns a distinct signature for gapless phases. Finally, we discuss possible ways to measure the order parameter in experiments with cold atoms.

preprint2012arXiv

Joint system quantum descriptions arising from local quantumness

Bipartite correlations generated by non-signalling physical systems that admit a finite-dimensional local quantum description cannot exceed the quantum limits, i.e., they can always be interpreted as distant measurements of a bipartite quantum state. Here we consider the effect of dropping the assumption of finite dimensionality. Remarkably, we find that the same result holds provided that we relax the tensor structure of space-like separated measurements to mere commutativity. We argue why an extension of this result to tensor representations seems unlikely.

preprint2012arXiv

Preparing topological PEPS on a quantum computer

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.

preprint2012arXiv

Quantum Steering and Space-Like Separation

In non-relativistic quantum mechanics, measurements performed by separate observers are modeled via tensor products. In Algebraic Quantum Field Theory, though, local observables corresponding to space-like separated parties are just required to commute. The problem of determining whether these two definitions of "separation" lead to the same set of bipartite correlations is known in non-locality as Tsirelson's problem. In this article, we prove that the analog of Tsirelson's problem in steering scenarios is false. That is, there exists a steering inequality that can be violated or not depending on how we define space-like separation at the operator level.

preprint2012arXiv

Resonating valence bond states in the PEPS formalism

We study resonating valence bond (RVB) states in the Projected Entangled Pair States (PEPS) formalism. Based on symmetries in the PEPS description, we establish relations between the toric code state, the orthogonal dimer state, and the SU(2) singlet RVB state on the kagome lattice: We prove the equivalence of toric code and dimer state, and devise an interpolation between the dimer state and the RVB state. This interpolation corresponds to a continuous path in Hamiltonian space, proving that the RVB state is the four-fold degenerate ground state of a local Hamiltonian on the (finite) kagome lattice. We investigate this interpolation using numerical PEPS methods, studying the decay of correlation functions, the change of overlap, and the entanglement spectrum, none of which exhibits signs of a phase transition.

preprint2011arXiv

A physical approach to Tsirelson's problem

Tsirelson's problem deals with how to model separate measurements in quantum mechanics. In addition to its theoretical importance, the resolution of Tsirelson's problem could have great consequences for device independent quantum key distribution and certified randomness. Unfortunately, understanding present literature on the subject requires a heavy mathematical background. In this paper, we introduce quansality, a new theoretical concept that allows to reinterpret Tsirelson's problem from a foundational point of view. Using quansality as a guide, we recover all known results on Tsirelson's problem in a clear and intuitive way.

preprint2011arXiv

Are problems in Quantum Information Theory (un)decidable?

This note is intended to foster a discussion about the extent to which typical problems arising in quantum information theory are algorithmically decidable (in principle rather than in practice). Various problems in the context of entanglement theory and quantum channels turn out to be decidable via quantifier elimination as long as they admit a compact formulation without quantification over integers. For many asymptotically defined properties which have to hold for all or for one integer N, however, effective procedures seem to be difficult if not impossible to find. We review some of the main tools for (dis)proving decidability and apply them to problems in quantum information theory. We find that questions like "can we overcome fidelity 1/2 w.r.t. a two-qubit singlet state?" easily become undecidable. A closer look at such questions might rule out some of the "single-letter" formulas sought in quantum information theory.

preprint2011arXiv

Classifying quantum phases using Matrix Product States and PEPS

We give a classification of gapped quantum phases of one-dimensional systems in the framework of Matrix Product States (MPS) and their associated parent Hamiltonians, for systems with unique as well as degenerate ground states, and both in the absence and presence of symmetries. We find that without symmetries, all systems are in the same phase, up to accidental ground state degeneracies. If symmetries are imposed, phases without symmetry breaking (i.e., with unique ground states) are classified by the cohomology classes of the symmetry group, this is, the equivalence classes of its projective representations, a result first derived in [X. Chen, Z.-C. Gu, and X.-G. Wen, Phys. Rev. B 83, 035107 (2011); arXiv:1008.3745]. For phases with symmetry breaking (i.e., degenerate ground states), we find that the symmetry consists of two parts, one of which acts by permuting the ground states, while the other acts on individual ground states, and phases are labelled by both the permutation action of the former and the cohomology class of the latter. Using Projected Entangled Pair States (PEPS), we subsequently extend our framework to the classification of two-dimensional phases in the neighborhood of a number of important cases, in particular systems with unique ground states, degenerate ground states with a local order parameter, and topological order. We also show that in two dimensions, imposing symmetries does not constrain the phase diagram in the same way it does in one dimension. As a central tool, we introduce the isometric form, a normal form for MPS and PEPS which is a renormalization fixed point. Transforming a state to its isometric form does not change the phase, and thus, we can focus on to the classification of isometric forms.

preprint2011arXiv

Tripartite probability distributions and communication complexity

We show that every tripartite quantum correlation generated with a Schmidt state (in particular every correlation generated with the GHZ state) can be simulated with the sending of two bits of classical communication from Alice to Bob and Charlie plus the sending of two bits of classical communication from Bob to Charlie. This extends recent results which showed that the maximal violation of Bell inequalities attainable by these correlations is uniformly bounded. For simplicity, we state and prove the result for three parties, but the generalization to the case of $n$ parties follows easily. We also show that every $n$-partite probability distribution generated with local resources plus $c$-bits of local communication can violate a Bell inequality by at most a factor of $2^c$.

preprint2010arXiv

PEPS as ground states: degeneracy and topology

We introduce a framework for characterizing Matrix Product States (MPS) and Projected Entangled Pair States (PEPS) in terms of symmetries. This allows us to understand how PEPS appear as ground states of local Hamiltonians with finitely degenerate ground states and to characterize the ground state subspace. Subsequently, we apply our framework to show how the topological properties of these ground states can be explained solely from the symmetry: We prove that ground states are locally indistinguishable and can be transformed into each other by acting on a restricted region, we explain the origin of the topological entropy, and we discuss how to renormalize these states based on their symmetries. Finally, we show how the anyonic character of excitations can be understood as a consequence of the underlying symmetries.

preprint2010arXiv

Sequential Strong Measurements and Heat Vision

We study scenarios where a finite set of non-demolition von-Neumann measurements are available. We note that, in some situations, repeated application of such measurements allows estimating an infinite number of parameters of the initial quantum state, and illustrate the point with a physical example. We then move on to study how the system under observation is perturbed after several rounds of projective measurements. While in the finite dimensional case the effect of this perturbation always saturates, there are some instances of infinite dimensional systems where such a perturbation is accumulative, and the act of retrieving information about the system increases its energy indefinitely (i.e., we have `Heat Vision'). We analyze this effect and discuss a specific physical system with two dichotomic von-Neumann measurements where Heat Vision is expected to show.

preprint2010arXiv

The inverse eigenvalue problem for quantum channels

Given a list of n complex numbers, when can it be the spectrum of a quantum channel, i.e., a completely positive trace preserving map? We provide an explicit solution for the n=4 case and show that in general the characterization of the non-zero part of the spectrum can essentially be given in terms of its classical counterpart - the non-zero spectrum of a stochastic matrix. A detailed comparison between the classical and quantum case is given. We discuss applications of our findings in the analysis of time-series and correlation functions and provide a general characterization of the peripheral spectrum, i.e., the set of eigenvalues of modulus one. We show that while the peripheral eigen-system has the same structure for all Schwarz maps, the constraints imposed on the rest of the spectrum change immediately if one departs from complete positivity.

preprint2009arXiv

Assessing dimensions from evolution

Using tools from classical signal processing, we show how to determine the dimensionality of a quantum system as well as the effective size of the environment's memory from observable dynamics in a model-independent way. We discuss the dependence on the number of conserved quantities, the relation to ergodicity and prove a converse showing that a Hilbert space of dimension D+2 is sufficient to describe every bounded sequence of measurements originating from any D-dimensional linear equations of motion. This is in sharp contrast to classical stochastic processes which are subject to more severe restrictions: a simple spectral analysis shows that the gap between the required dimensionality of a quantum and a classical description of an observed evolution can be arbitrary large.

preprint2009arXiv

Measurements incompatible in Quantum Theory cannot be measured jointly in any other local theory

It is well known that jointly measurable observables cannot lead to a violation of any Bell inequality - independent of the state and the measurements chosen at the other site. In this letter we prove the converse: every pair of incompatible quantum observables enables the violation of a Bell inequality and therefore must remain incompatible within any other no-signaling theory. While in the case of von Neumann measurements it is sufficient to use the same pair of observables at both sites, general measurements can require different choices. The main result is obtained by showing that for arbitrary dimension the CHSH inequality provides the Lagrangian dual of the characterization of joint measurability. This leads to a simple criterion for joint measurability beyond the known qubit case.

preprint2006arXiv

Contractivity of positive and trace preserving maps under $L_p$ norms

We provide a complete picture of contractivity of trace preserving positive maps with respect to $p$-norms. We show that for $p>1$ contractivity holds in general if and only if the map is unital. When the domain is restricted to the traceless subspace of Hermitian matrices, then contractivity is shown to hold in the case of qubits for arbitrary $p\geq 1$ and in the case of qutrits if and only if $p=1,\infty$. In all non-contractive cases best possible bounds on the $p$-norms are derived.