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:2003.13753 · Annales Henri Poincaré

Translationally Invariant Universal Quantum Hamiltonians in 1D

Tamara Kohler, Stephen Piddock, Johannes Bausch, Toby S. Cubitt

Published Oct 23, 2021• 22 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1007/s00023-021-01111-7

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•14 citations

The Complexity of Translationally Invariant Spin Chains with Low Local Dimension

Johannes Bausch, Toby S. Cubitt, Māris Ozols

We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on a 1D spin chain is $$\textsf {QMA}_{{\textsf {EXP}}}$$ -complete, even for systems of low local dimension ( $$\approx 40$$ ). This is an improvement over the best previously known result by several orders of magnitude, and it shows that spin-glass-like frustration can occur in translationally invariant quantum systems with a local dimension comparable to the smallest-known non-translationally invariant systems with similar behaviour. While previous constructions of such systems rely on standard models of quantum computation, we construct a new model that is particularly well-suited for encoding quantum computation into the ground state of a translationally invariant system. This allows us to shift the proof burden from optimizing the Hamiltonian encoding a standard computational model, to proving universality of a simple model. Previous techniques for encoding quantum computation into the ground state of a local Hamiltonian allow only a linear sequence of gates, hence only a linear (or nearly linear) path in the graph of all computational states. We extend these techniques by allowing significantly more general paths, including branching and cycles, thus enabling a highly efficient encoding of our computational model. However, this requires more sophisticated techniques for analysing the spectrum of the resulting Hamiltonian. To address this, we introduce a framework of graphs with unitary edge labels. After relating our Hamiltonian to the Laplacian of such a unitary labelled graph, we analyse its spectrum by combining matrix analysis and spectral graph theory techniques.

arXiv:1605.01718•Annales Henri Poincaré•Oct 29, 2017•46 citations

General Conditions for Universality of Quantum Hamiltonians

Tamara Kohler, Stephen Piddock, Johannes Bausch +1 more

Recent work has demonstrated the existence of universal Hamiltonians-simple spin-lattice models that can simulate any other quantum many-body system to any desired level of accuracy.Until now, proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians.In this work, we go beyond this approach and completely classify the simulation ability of quantum Hamiltonians by their complexity classes.We do this by deriving necessary and sufficient complexitytheoretic conditions characterizing universal quantum Hamiltonians.Although the result concerns the theory of analog Hamiltonian simulation-a promising application of near-term quantum technology-the proof relies on abstract complexity-theoretic concepts and the theory of quantum computation.As well as providing simplified proofs of previous Hamiltonian universality results and offering a route to new universal constructions, the results in this paper give insight into the origins of universality; for example, finally explaining the previously noted coincidences between families of universal Hamiltonian and classes of Hamiltonians appearing in complexity theory.

arXiv:2101.12319•PRX Quantum•Jan 13, 2022•9 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•15 citations

Universal Hamiltonian simulators in one and two dimensions

Leo Zhou, Dorit Aharonov

Abstract A major quantum computing application is analog Hamiltonian simulations, in which the low-lying spectrum of a simulator Hamiltonian $${H}^{{\prime} }$$ H ′ encodes the physics of a target Hamiltonian H . Some families of 2D spin-lattice Hamiltonians—such as the Heisenberg or XY model on the square lattice—are known to be “universal” simulators, in the sense that they can simulate any target Hamiltonian. Unfortunately, while the known simulations of 1D or 2D target Hamiltonians are efficient, they require resources growing exponentially with system sizes for target Hamiltonians with general connectivity. This leaves many important cases such as 3D or all-to-all-connected target Hamiltonians out of reach in practice. Here, we remedy this situation and show how the known 2D universal families of Hamiltonians and a new 1D family can simulate all target local Hamiltonians, with only polynomial-scaling overhead. This exponential improvement is achieved by a nonperturbative method combining the quantum phase-estimation algorithm and the circuit-to-Hamiltonian construction. Furthermore, all Hamiltonians efficiently simulable by quantum circuits, including nonlocal ones, also have efficient analog simulators in our 2D and 1D universal families. Our work establishes that analog simulations of general Hamiltonians can be made efficient, significantly expanding the application potential of analog Hamiltonian simulations in near-term quantum technologies.

arXiv:2102.02991•Nature Communications•Apr 21, 2026•36 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
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.
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.
We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on a 1D spin chain is QMAEXP\textsf {QMA}_{{\textsf {EXP}}}QMAEXP​ -complete, even for systems of low local dimension ( ≈40\approx 40≈40 ). This is an improvement over the best previously known result by several orders of magnitude, and it shows that spin-glass-like frustration can occur in translationally invariant quantum systems with a local dimension comparable to the smallest-known non-translationally invariant systems with similar behaviour. While previous constructions of such systems rely on standard models of quantum computation, we construct a new model that is particularly well-suited for encoding quantum computation into the ground state of a translationally invariant system. This allows us to shift the proof burden from optimizing the Hamiltonian encoding a standard computational model, to proving universality of a simple model. Previous techniques for encoding quantum computation into the ground state of a local Hamiltonian allow only a linear sequence of gates, hence only a linear (or nearly linear) path in the graph of all computational states. We extend these techniques by allowing significantly more general paths, including branching and cycles, thus enabling a highly efficient encoding of our computational model. However, this requires more sophisticated techniques for analysing the spectrum of the resulting Hamiltonian. To address this, we introduce a framework of graphs with unitary edge labels. After relating our Hamiltonian to the Laplacian of such a unitary labelled graph, we analyse its spectrum by combining matrix analysis and spectral graph theory techniques.
Recent work has demonstrated the existence of universal Hamiltonians-simple spin-lattice models that can simulate any other quantum many-body system to any desired level of accuracy.Until now, proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians.In this work, we go beyond this approach and completely classify the simulation ability of quantum Hamiltonians by their complexity classes.We do this by deriving necessary and sufficient complexitytheoretic conditions characterizing universal quantum Hamiltonians.Although the result concerns the theory of analog Hamiltonian simulation-a promising application of near-term quantum technology-the proof relies on abstract complexity-theoretic concepts and the theory of quantum computation.As well as providing simplified proofs of previous Hamiltonian universality results and offering a route to new universal constructions, the results in this paper give insight into the origins of universality; for example, finally explaining the previously noted coincidences between families of universal Hamiltonian and classes of Hamiltonians appearing in 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 A major quantum computing application is analog Hamiltonian simulations, in which the low-lying spectrum of a simulator Hamiltonian H′{H}^{{\prime} }H′ H ′ encodes the physics of a target Hamiltonian H . Some families of 2D spin-lattice Hamiltonians—such as the Heisenberg or XY model on the square lattice—are known to be “universal” simulators, in the sense that they can simulate any target Hamiltonian. Unfortunately, while the known simulations of 1D or 2D target Hamiltonians are efficient, they require resources growing exponentially with system sizes for target Hamiltonians with general connectivity. This leaves many important cases such as 3D or all-to-all-connected target Hamiltonians out of reach in practice. Here, we remedy this situation and show how the known 2D universal families of Hamiltonians and a new 1D family can simulate all target local Hamiltonians, with only polynomial-scaling overhead. This exponential improvement is achieved by a nonperturbative method combining the quantum phase-estimation algorithm and the circuit-to-Hamiltonian construction. Furthermore, all Hamiltonians efficiently simulable by quantum circuits, including nonlocal ones, also have efficient analog simulators in our 2D and 1D universal families. Our work establishes that analog simulations of general Hamiltonians can be made efficient, significantly expanding the application potential of analog Hamiltonian simulations in near-term quantum technologies.
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-