Classical spin Hamiltonians are a powerful tool to model complex systems, characterized by a local structure given by the local Hamiltonians. One of the best understood local structures is the grammar of formal languages, which are central in computer science and linguistics, and have a natural complexity measure given by the Chomsky hierarchy. If we see classical spin Hamiltonians as languages, what grammar do the local Hamiltonians correspond to? Here, we cast classical spin Hamiltonians as formal languages, and classify them in the Chomsky hierarchy. We prove that the language of (effectively) zero-dimensional spin Hamiltonians is regular, one-dimensional spin Hamiltonians is deterministic context-free, and higher-dimensional and all-to-all spin Hamiltonians is context-sensitive. This provides a new complexity measure for classical spin Hamiltonians, which captures the hardness of recognizing spin configurations and their energies. We compare it with the computational complexity of the ground state energy problem, and find a different easy-to-hard threshold for the Ising model. We also investigate the dependence on the language of the spin Hamiltonian. Finally, we define the language of the time evolution of a spin Hamiltonian and classify it in the Chomsky hierarchy. Our work suggests that universal spin models are weaker than universal Turing machines.
Classical spin Hamiltonians are a powerful tool to model complex systems, characterized by a local structure given by the local Hamiltonians. One of the best understood local structures is the grammar of formal languages, which are central in computer science and linguistics, and have a natural complexity measure given by the Chomsky hierarchy. If we see classical spin Hamiltonians as languages, what grammar do the local Hamiltonians correspond to? Here, we cast classical spin Hamiltonians as formal languages, and classify them in the Chomsky hierarchy. We prove that the language of (effectively) zero-dimensional spin Hamiltonians is regular, one-dimensional spin Hamiltonians is deterministic context-free, and higher-dimensional and all-to-all spin Hamiltonians is context-sensitive. This provides a new complexity measure for classical spin Hamiltonians, which captures the hardness of recognizing spin configurations and their energies. We compare it with the computational complexity of the ground state energy problem, and find a different easy-to-hard threshold for the Ising model. We also investigate the dependence on the language of the spin Hamiltonian. Finally, we define the language of the time evolution of a spin Hamiltonian and classify it in the Chomsky hierarchy. Our work suggests that universal spin models are weaker than universal Turing machines.
A broad range of quantum optimisation problems can be phrased as the question whether a specific system has a ground state at zero energy, i.e. whether its Hamiltonian is frustration free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms in order to, at least, partially answer this question. Here we prove a general criterion -- a sufficient condition -- under which a local Hamiltonian is guaranteed to be frustration free by lifting Shearer's theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hard-core lattice gas at negative fugacity on the Hamiltonian's interaction graph which as a statistical mechanics problem is of interest in their own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass theory which permit us to obtain new bounds on the SAT/UNSAT transition in random quantum satisfiability. These also lead us to natural conjectures for when such bounds will be exact (tight), as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.
In this theoretical paper, we consider spin systems in three spatial dimensions and consider the computational complexity of estimating the ground state energy, known as the local Hamiltonian problem, for translationally invariant Hamiltonians. We prove that the local Hamiltonian problem for 3D lattices with face-centered cubic unit cells and 4-local translationally invariant interactions between spin-3/2 particles and open boundary conditions is QMAEXP-complete, where QMAEXP is the class of problems which can be verified in exponential time on a quantum computer. We go beyond a mere embedding of past hard 1D history state constructions, for which the local spin dimension is enormous: even state-of-the-art constructions have local dimension 42. We avoid such a large local dimension by combining some different techniques in a novel way. For the verifier circuit which we embed into the ground space of the local Hamiltonian, we utilize a recently developed computational model, called a quantum ring machine, which is especially well suited for translationally invariant history state constructions. This is encoded with a new and particularly simple universal gate set, which consists of a single 2-qubit gate applied only to nearest-neighbour qubits. The Hamiltonian construction involves a classical Wang tiling problem as a binary counter which translates one cube side length into a binary description for the encoded verifier input and a carefully engineered history state construction that implements the ring machine on the cubic lattice faces. These novel techniques allow us to significantly lower the local spin dimension, surpassing the best translationally invariant result to date by two orders of magnitude (in the number of degrees of freedom per coupling). This brings our models on par with the best non-translationally invariant construction.
Abstract Recent work has characterized rigorously what it means for one quantum system to simulate another and demonstrated the existence of universal Hamiltonians—simple spin lattice Hamiltonians that can replicate the entire physics of any other quantum many-body system. Previous universality results have required proofs involving complicated ‘chains’ of perturbative ‘gadgets.’ In this paper, we derive a significantly simpler and more powerful method of proving universality of Hamiltonians, directly leveraging the ability to encode quantum computation into ground states. This provides new insight into the origins of universal models and suggests a deep connection between universality and complexity. We apply this new approach to show that there are universal models even in translationally invariant spin chains in 1D. This gives as a corollary a new Hamiltonian complexity result that the local Hamiltonian problem for translationally invariant spin chains in one dimension with an exponentially small promise gap is PSPACE-complete. Finally, we use these new universal models to construct the first known toy model of 2D–1D holographic duality between local Hamiltonians.
A broad range of quantum optimization problems can be phrased as the question of whether a specific system has a ground state at zero energy, i.e., whether its Hamiltonian is frustration-free. Frustration-free Hamiltonians, in turn, play a central role for constructing and understanding new phases of matter in quantum many-body physics. Unfortunately, determining whether this is the case is known to be a complexity-theoretically intractable problem. This makes it highly desirable to search for efficient heuristics and algorithms to, at least, partially answer this question. Here we prove a general criterion-a sufficient condition-under which a local Hamiltonian is guaranteed to be frustration-free by lifting Shearer's theorem from classical probability theory to the quantum world. Remarkably, evaluating this condition proceeds via a fully classical analysis of a hardcore lattice gas at negative fugacity on the Hamiltonian's interaction graph, which, as a statistical mechanics problem, is of interest in its own right. We concretely apply this criterion to local Hamiltonians on various regular lattices, while bringing to bear the tools of spin glass physics that permit us to obtain new bounds on the satisfiable to unsatisfiable transition in random quantum satisfiability. We are then led to natural conjectures for when such bounds will be tight, as well as to a novel notion of universality for these computer science problems. Besides providing concrete algorithms leading to detailed and quantitative insights, this work underscores the power of marrying classical statistical mechanics with quantum computation and complexity theory.
The Hamiltonians of quantum many-body systems can display an extremely diverse range of behaviours.In this thesis we show that there exist simple systems which can simulate all other quantum many-body systems, including all of their physical properties.We call these universal Hamiltonians.We first define a notion of analogue simulation which captures what it means for the Hamiltonian of one system to be reproduced in the Hamiltonian of another physical system.Then we obtain a full classification of simulation power in the case of families of Hamiltonians built up as a linear combination of 2-local qubit interactions.The generalised Heisenberg model and generalised XY model are important special cases which are universal in this classification.We also prove universality for other restricted classes of Hamiltonians such as those for which all the interaction strengths have the same sign or for Hamiltonians with spatially restricted interaction graphs.And we prove universality for large classes of qudit Hamiltonians (where the local dimension d > 2).Universality of a family of Hamiltonians implies that the problem of estimating the ground state energy, known as the Local Hamiltonian problem, is QMA-complete for Hamiltonians from that family.Our results prove that this is the case for many restricted families of Hamiltonians, for which the complexity of the Local Hamiltonian problem was not previously known.We also show that the Local Hamiltonian problem is QMA EXPcomplete for a translationally invariant Hamiltonian of 4-local interactions between spins of dimension d = 4, arranged on a face-centred cubic lattice, by directly encoding a verifier circuit into the interaction terms.Finally we consider the problem of simulating a local measurement in the ground space of a local Hamiltonian, introduced by Ambainis as APX-SIM.We simplify some of the prior work on this problem and prove some previously unknown complexity class inequalities.We show that our notion of simulation preserves hardness of this problem and obtain a complexity classification of APX-SIM for Hamiltonians of 2-local qubit interactions.i Dedication and acknowledgements First and foremost, I must thank my supervisor, Ashley Montanaro, for all of his help over the last few years.He has always made himself available to discuss work, and I am grateful for all of his advice, his problem suggestions, and his excellent proof-reading skills!I must also thank all of my other co-
The theory of spin models intersects with condensed matter physics, complex systems, graph theory, combinatorial optimization, computational complexity and neural networks. Many ensuing applications rely on transforming complicated spin models to simpler ones. What is the structure of such transformations? Here, we provide a framework to study and construct emulations between spin models. A spin model is a set of spin systems, and emulations are efficiently computable families of simulations with arbitrary energy cut-off, where a source spin system simulates a target system if, below the cut-off, the target Hamiltonian is encoded in the source Hamiltonian. We prove that emulations preserve important properties, as they induce reductions between computational problems such as computing ground states, approximating partition functions and approximate sampling from Boltzmann distributions. Emulations are modular (they can be added, scaled and composed), and allow for universality, i.e., under emulations, certain spin models have maximal reach. We prove that a spin model is universal if and only if it is scalable, closed and functional complete. Because the characterization is constructive, it provides a step-by-step guide to construct emulations. We prove that the 2d Ising model with fields is universal, for which we also provide two new crossing gadgets. Finally, we show that simulations can be computed by linear programs. While some ideas of this work are contained in G. De las Cuevas and T. S. Cubitt, Science 351, 1180 (2016), we provide new definitions and theorems. This framework provides a toolbox for applications involving emulations of spin models.