Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2001.08050

Universal Translationally-Invariant Hamiltonians

Stephen Piddock, Johannes Bausch

Published Jan 22, 2020• 3 citations
arXivHTMLPDF

Abstract

In this work we extend the notion of universal quantum Hamiltonians to the setting of translationally-invariant systems. We present a construction that allows a two-dimensional spin lattice with nearest-neighbour interactions, open boundaries, and translational symmetry to simulate any local target Hamiltonian---i.e. to reproduce the whole of the target system within its low-energy subspace to arbitrarily-high precision. Since this implies the capability to simulate non-translationally-invariant many-body systems with translationally-invariant couplings, any effect such as characteristics commonly associated to systems with external disorder, e.g. many-body localization, can also occur within the low-energy Hilbert space sector of translationally-invariant systems. Then we sketch a variant of the universal lattice construction optimized for simulating translationally-invariant target Hamiltonians. Finally we prove that qubit Hamiltonians consisting of Heisenberg or XY interactions of varying interaction strengths restricted to the edges of a connected translationally-invariant graph embedded in $\mathbb{R}^D$ are universal, and can efficiently simulate any geometrically local Hamiltonian in $\mathbb{R}^D$.

DOI
10.48550/arxiv.2001.08050

Related papers

Translationally Invariant Universal Classical Hamiltonians

Tamara Kohler, Toby S. Cubitt

Spin models are widely studied in the natural sciences, from investigating magnetic materials in condensed matter physics to studying neural networks. Previous work has demonstrated that there exist simple classical spin models that are universal: they can replicate—in a precise and rigorous sense—the complete physics of any other classical spin model, to any desired accuracy. However, all previously known universal models break translational invariance. In this paper we show that there exist translationally invariant universal models. Our main result is an explicit construction of a translationally invariant, 2D, nearest-neighbour, universal classical Hamiltonian with a single free parameter. The proof draws on techniques from theoretical computer science, in particular recent complexity theoretic results on tiling problems. Our results imply that there exists a single Hamiltonian which encompasses all classical spin physics, just by tuning a single parameter and varying the size of the lattice. We also prove that our construction is optimal in terms of the number of parameters in the Hamiltonian; there cannot exist a translationally invariant universal Hamiltonian with only the lattice size as a parameter.

arXiv:1807.01715•Journal of Statistical Physics•Apr 30, 2019•7 citations

Translationally Invariant Universal Classical Hamiltonians

Tamara Kohler, Toby S. Cubitt

Spin models are widely studied in the natural sciences, from investigating magnetic materials in condensed matter physics to studying neural networks. Previous work has demonstrated that there exist simple classical spin models that are universal: they can replicate—in a precise and rigorous sense—the complete physics of any other classical spin model, to any desired accuracy. However, all previously known universal models break translational invariance. In this paper we show that there exist translationally invariant universal models. Our main result is an explicit construction of a translationally invariant, 2D, nearest-neighbour, universal classical Hamiltonian with a single free parameter. The proof draws on techniques from theoretical computer science, in particular recent complexity theoretic results on tiling problems. Our results imply that there exists a single Hamiltonian which encompasses all classical spin physics, just by tuning a single parameter and varying the size of the lattice. We also prove that our construction is optimal in terms of the number of parameters in the Hamiltonian; there cannot exist a translationally invariant universal Hamiltonian with only the lattice size as a parameter.

•Apr 30, 2019•9 citations

Translationally Invariant Universal Quantum Hamiltonians in 1D

Tamara Kohler, Stephen Piddock, Johannes Bausch +1 more

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.

arXiv:2003.13753•Annales Henri Poincaré•Oct 23, 2021•16 citations

The complexity of translationally invariant low-dimensional spin lattices in 3D

Johannes Bausch, Stephen Piddock

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.

arXiv:1702.08830•Journal of Mathematical Physics•Nov 1, 2017•13 citations

Complexity and simulation of many-body quantum systems

Stephen Piddock

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-

•Jan 1, 2019•0 citations

Generic Local Hamiltonians are Gapless

Ramis Movassagh

We prove that generic quantum local Hamiltonians are gapless. In fact, we prove that there is a continuous density of states above the ground state. The Hamiltonian can be on a lattice in any spatial dimension or on a graph with a bounded maximum vertex degree. The type of interactions allowed for include translational invariance in a disorder (i.e., probabilistic) sense with some assumptions on the local distributions. Examples include many-body localization and random spin models. We calculate the scaling of the gap with the system's size when the local terms are distributed according to a Gaussian β orthogonal random matrix ensemble. As a corollary, there exist finite size partitions with respect to which the ground state is arbitrarily close to a product state. When the local eigenvalue distribution is discrete, in addition to the lack of an energy gap in the limit, we prove that the ground state has finite size degeneracies. The proofs are simple and constructive. This work excludes the important class of truly translationally invariant Hamiltonians where the local terms are all equal.

arXiv:1606.09313•Physical Review Letters•Nov 29, 2017•21 citations
In this work we extend the notion of universal quantum Hamiltonians to the setting of translationally-invariant systems. We present a construction that allows a two-dimensional spin lattice with nearest-neighbour interactions, open boundaries, and translational symmetry to simulate any local target Hamiltonian---i.e. to reproduce the whole of the target system within its low-energy subspace to arbitrarily-high precision. Since this implies the capability to simulate non-translationally-invariant many-body systems with translationally-invariant couplings, any effect such as characteristics commonly associated to systems with external disorder, e.g. many-body localization, can also occur within the low-energy Hilbert space sector of translationally-invariant systems. Then we sketch a variant of the universal lattice construction optimized for simulating translationally-invariant target Hamiltonians. Finally we prove that qubit Hamiltonians consisting of Heisenberg or XY interactions of varying interaction strengths restricted to the edges of a connected translationally-invariant graph embedded in RD\mathbb{R}^DRD are universal, and can efficiently simulate any geometrically local Hamiltonian in RD\mathbb{R}^DRD.
Spin models are widely studied in the natural sciences, from investigating magnetic materials in condensed matter physics to studying neural networks. Previous work has demonstrated that there exist simple classical spin models that are universal: they can replicate—in a precise and rigorous sense—the complete physics of any other classical spin model, to any desired accuracy. However, all previously known universal models break translational invariance. In this paper we show that there exist translationally invariant universal models. Our main result is an explicit construction of a translationally invariant, 2D, nearest-neighbour, universal classical Hamiltonian with a single free parameter. The proof draws on techniques from theoretical computer science, in particular recent complexity theoretic results on tiling problems. Our results imply that there exists a single Hamiltonian which encompasses all classical spin physics, just by tuning a single parameter and varying the size of the lattice. We also prove that our construction is optimal in terms of the number of parameters in the Hamiltonian; there cannot exist a translationally invariant universal Hamiltonian with only the lattice size as a parameter.
Spin models are widely studied in the natural sciences, from investigating magnetic materials in condensed matter physics to studying neural networks. Previous work has demonstrated that there exist simple classical spin models that are universal: they can replicate—in a precise and rigorous sense—the complete physics of any other classical spin model, to any desired accuracy. However, all previously known universal models break translational invariance. In this paper we show that there exist translationally invariant universal models. Our main result is an explicit construction of a translationally invariant, 2D, nearest-neighbour, universal classical Hamiltonian with a single free parameter. The proof draws on techniques from theoretical computer science, in particular recent complexity theoretic results on tiling problems. Our results imply that there exists a single Hamiltonian which encompasses all classical spin physics, just by tuning a single parameter and varying the size of the lattice. We also prove that our construction is optimal in terms of the number of parameters in the Hamiltonian; there cannot exist a translationally invariant universal Hamiltonian with only the lattice size as a parameter.
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.
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.
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-
We prove that generic quantum local Hamiltonians are gapless. In fact, we prove that there is a continuous density of states above the ground state. The Hamiltonian can be on a lattice in any spatial dimension or on a graph with a bounded maximum vertex degree. The type of interactions allowed for include translational invariance in a disorder (i.e., probabilistic) sense with some assumptions on the local distributions. Examples include many-body localization and random spin models. We calculate the scaling of the gap with the system's size when the local terms are distributed according to a Gaussian β orthogonal random matrix ensemble. As a corollary, there exist finite size partitions with respect to which the ground state is arbitrarily close to a product state. When the local eigenvalue distribution is discrete, in addition to the lack of an energy gap in the limit, we prove that the ground state has finite size degeneracies. The proofs are simple and constructive. This work excludes the important class of truly translationally invariant Hamiltonians where the local terms are all equal.