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:quant-ph/0612186 · Physical Review A

Graph states as ground states of many-body spin- 1∕2 Hamiltonians

M. Van den Nest, K. Luttmer, Wolfgang Dür, Hans J. Briegel

Published Jan 3, 2008• 44 citations
arXivHTMLPDF

Abstract

We consider the problem of whether graph states can be ground states of local interaction Hamiltonians. For Hamiltonians acting on $n$ qubits that involve at most two-body interactions, we show that no $n$-qubit graph state can be the exact, nondegenerate ground state. We determine for any graph state the minimal $d$ such that it is the nondegenerate ground state of a $d$-body interaction Hamiltonian, while we show for ${d}^{\ensuremath{'}}$-body Hamiltonians $H$ with ${d}^{\ensuremath{'}}<d$ that the resulting ground state can only be close to the graph state at the cost of $H$ having a small energy gap relative to the total energy. When allowing for ancilla particles, we show how to utilize a gadget construction introduced in the context of the $k$-local Hamiltonian problem, to obtain $n$-qubit graph states as nondegenerate (quasi)ground states of a two-body Hamiltonian acting on ${n}^{\ensuremath{'}}>n$ spins.

DOI
10.1103/physreva.77.012301

Related papers

Graph states as ground states of two-body frustration-free Hamiltonians

Andrew S Darmawan, Stephen D. Bartlett

The framework of measurement-based quantum computation (MBQC) allows us to view the ground states of local Hamiltonians as potential resources for universal quantum computation. A central goal in this field is to find models with ground states that are universal for MBQC and that are also natural in the sense that they involve only two-body interactions and have a small local Hilbert space dimension. Graph states are the original resource states for MBQC, and while it is not possible to obtain graph states as exact ground states of two-body Hamiltonians here we construct two-body frustration-free Hamiltonians that have arbitrarily good approximations of graph states as unique ground states. The construction involves taking a two-body frustration-free model that has a ground state convertible to a graph state with stochastic local operations, then deforming the model such that its ground state is close to a graph state. Each graph state qubit resides in a subspace of a higher dimensional particle. This deformation can be applied to two-body frustration-free Affleck-Kennedy-Lieb-Tasaki (AKLT) models, yielding Hamiltonians that are exactly solvable with exact tensor network expressions for ground states. For the star-lattice AKLT model, the ground state of which is not expected to be a universal resource for MBQC, applying such a deformation appears to enhance the computational power of the ground state, promoting it to a universal resource for MBQC. Transitions in computational power, similar to percolation phase transitions, can be observed when Hamiltonians are deformed in this way. Improving the fidelity of the ground state comes at the cost of a shrinking gap. While analytically proving gap properties for these types of models is difficult in general, we provide a detailed analysis of the deformation of a spin-1 AKLT state to a linear graph state.

arXiv:1403.2402•New Journal of Physics•Jul 9, 2014•20 citations

Spin lattices with two-body Hamiltonians for which the ground state encodes a cluster state

Tom Griffin, Stephen D. Bartlett

We present a general procedure for constructing lattices of qubits with a Hamiltonian composed of nearest-neighbor two-body interactions such that the ground state encodes a cluster state. We give specific details for lattices in one, two, and three dimensions, investigating both periodic and fixed boundary conditions, as well as present a proof for the applicability of this procedure to any graph. We determine the energy gap of these systems, which is shown to be independent of the size of the lattice but dependent on the type of lattice (in particular, the coordination number), and investigate the scaling of this gap in terms of the coupling constants of the Hamiltonian. We provide a comparative analysis of the different lattice types with respect to their usefulness for measurement-based quantum computation.

arXiv:0805.2980•Physical Review A•Dec 4, 2008•19 citations

Correlations in excited states of local Hamiltonians

Jianxin Chen, Zhengfeng Ji, Zhaohui Wei +1 more

Physical properties of the ground and excited states of a $k$-local Hamiltonian are largely determined by the $k$-particle reduced density matrices ($k$-RDMs), or simply the $k$-matrix for fermionic systems---they are at least enough for the calculation of the ground-state and excited-state energies. Moreover, for a nondegenerate ground state of a $k$-local Hamiltonian, even the state itself is completely determined by its $k$-RDMs, and therefore contains no genuine $>k$-particle correlations, as they can be inferred from $k$-particle correlation functions. It is natural to ask whether a similar result holds for nondegenerate excited states. In fact, for fermionic systems, it has been conjectured that any nondegenerate excited state of a 2-local Hamiltonian is simultaneously a unique ground state of another 2-local Hamiltonian, hence is uniquely determined by its 2-matrix. And a weaker version of this conjecture states that any nondegenerate excited state of a 2-local Hamiltonian is uniquely determined by its 2-matrix among all the pure $n$-particle states. We construct explicit counterexamples to show that both conjectures are false. We further show that any nondegenerate excited state of a $k$-local Hamiltonian is a unique ground state of another $2k$-local Hamiltonian, hence is uniquely determined by its $2k$-RDMs (or $2k$-matrix). These results set up a solid framework for the study of excited-state properties of many-body systems.

arXiv:1106.1373•Physical Review A•Apr 9, 2012•9 citations

Nonperturbative Gadget for Topological Quantum Codes

Samuel A. Ocko, Beni Yoshida

Many-body entangled systems, in particular topologically ordered spin systems proposed as resources for quantum information processing tasks, often involve highly nonlocal interaction terms. While one may approximate such systems through two-body interactions perturbatively, these approaches have a number of drawbacks in practice. In this Letter, we propose a scheme to simulate many-body spin Hamiltonians with two-body Hamiltonians nonperturbatively. Unlike previous approaches, our Hamiltonians are not only exactly solvable with exact ground state degeneracy, but also support completely localized quasiparticle excitations, which are ideal for quantum information processing tasks. Our construction is limited to simulating the toric code and quantum double models, but generalizations to other nonlocal spin Hamiltonians may be possible.

arXiv:1107.2697•Physical Review Letters•Dec 14, 2011•23 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•24 citations

On the mathematical structure of quantum models of computation based on Hamiltonian minimisation

Jacob Biamonte

Determining properties of ground states of spin Hamiltonians remains a topic of central relevance connecting disciplines of mathematical, theoretical and applied physics. In the last few decades, ground state properties of physical systems have been increasingly considered as computational resources. This thesis develops parts of the mathematical apparatus to create (program) ground states relevant for quantum and classical computation. The core findings presented in this thesis (now over a decade old) including that (i) logic operations (gates) can be embedded into the low-energy sector of Ising spins whereas three (and higher) body Ising interaction terms can be mimicked through the minimisation of 2- and 1-body Ising terms yet require the introduction of slack spins; (ii) Perturbation theory gadgets enable the emulation of interactions not present in a given Hamiltonian, e.g.~$YY$ interactions can be realized from $ZZ$, $XX$, the thesis contains a result from 2007 showing that physically relevant two-body model Hamiltonian's have a QMA-hard ground state energy decision problem. Merged with other results, this established that these models provide a universal resource for ground state quantum computation. More recent findings include the proof that an idealised version of the contemporary variational approach to quantum algorithms enables a universal model of quantum computation. Other related results are also presented as they relate to ground state quantum computation and the minimisation of Hamiltonians by quantum circuits. The topics covered include: Ising model reductions, stochastic versus quantum processes on graphs, quantum gates and circuits as tensor networks, variational quantum algorithms and Hamiltonian gadgets.

arXiv:2009.10088•Sep 21, 2020•1 citation
We consider the problem of whether graph states can be ground states of local interaction Hamiltonians. For Hamiltonians acting on nnn qubits that involve at most two-body interactions, we show that no nnn-qubit graph state can be the exact, nondegenerate ground state. We determine for any graph state the minimal ddd such that it is the nondegenerate ground state of a ddd-body interaction Hamiltonian, while we show for d\ensuremath′{d}^{\ensuremath{'}}d\ensuremath′-body Hamiltonians HHH with d\ensuremath′<d{d}^{\ensuremath{'}}<dd\ensuremath′<d that the resulting ground state can only be close to the graph state at the cost of HHH having a small energy gap relative to the total energy. When allowing for ancilla particles, we show how to utilize a gadget construction introduced in the context of the kkk-local Hamiltonian problem, to obtain nnn-qubit graph states as nondegenerate (quasi)ground states of a two-body Hamiltonian acting on n\ensuremath′>n{n}^{\ensuremath{'}}>nn\ensuremath′>n spins.
The framework of measurement-based quantum computation (MBQC) allows us to view the ground states of local Hamiltonians as potential resources for universal quantum computation. A central goal in this field is to find models with ground states that are universal for MBQC and that are also natural in the sense that they involve only two-body interactions and have a small local Hilbert space dimension. Graph states are the original resource states for MBQC, and while it is not possible to obtain graph states as exact ground states of two-body Hamiltonians here we construct two-body frustration-free Hamiltonians that have arbitrarily good approximations of graph states as unique ground states. The construction involves taking a two-body frustration-free model that has a ground state convertible to a graph state with stochastic local operations, then deforming the model such that its ground state is close to a graph state. Each graph state qubit resides in a subspace of a higher dimensional particle. This deformation can be applied to two-body frustration-free Affleck-Kennedy-Lieb-Tasaki (AKLT) models, yielding Hamiltonians that are exactly solvable with exact tensor network expressions for ground states. For the star-lattice AKLT model, the ground state of which is not expected to be a universal resource for MBQC, applying such a deformation appears to enhance the computational power of the ground state, promoting it to a universal resource for MBQC. Transitions in computational power, similar to percolation phase transitions, can be observed when Hamiltonians are deformed in this way. Improving the fidelity of the ground state comes at the cost of a shrinking gap. While analytically proving gap properties for these types of models is difficult in general, we provide a detailed analysis of the deformation of a spin-1 AKLT state to a linear graph state.
We present a general procedure for constructing lattices of qubits with a Hamiltonian composed of nearest-neighbor two-body interactions such that the ground state encodes a cluster state. We give specific details for lattices in one, two, and three dimensions, investigating both periodic and fixed boundary conditions, as well as present a proof for the applicability of this procedure to any graph. We determine the energy gap of these systems, which is shown to be independent of the size of the lattice but dependent on the type of lattice (in particular, the coordination number), and investigate the scaling of this gap in terms of the coupling constants of the Hamiltonian. We provide a comparative analysis of the different lattice types with respect to their usefulness for measurement-based quantum computation.
Physical properties of the ground and excited states of a kkk-local Hamiltonian are largely determined by the kkk-particle reduced density matrices (kkk-RDMs), or simply the kkk-matrix for fermionic systems---they are at least enough for the calculation of the ground-state and excited-state energies. Moreover, for a nondegenerate ground state of a kkk-local Hamiltonian, even the state itself is completely determined by its kkk-RDMs, and therefore contains no genuine >k>k>k-particle correlations, as they can be inferred from kkk-particle correlation functions. It is natural to ask whether a similar result holds for nondegenerate excited states. In fact, for fermionic systems, it has been conjectured that any nondegenerate excited state of a 2-local Hamiltonian is simultaneously a unique ground state of another 2-local Hamiltonian, hence is uniquely determined by its 2-matrix. And a weaker version of this conjecture states that any nondegenerate excited state of a 2-local Hamiltonian is uniquely determined by its 2-matrix among all the pure nnn-particle states. We construct explicit counterexamples to show that both conjectures are false. We further show that any nondegenerate excited state of a kkk-local Hamiltonian is a unique ground state of another 2k2k2k-local Hamiltonian, hence is uniquely determined by its 2k2k2k-RDMs (or 2k2k2k-matrix). These results set up a solid framework for the study of excited-state properties of many-body systems.
Many-body entangled systems, in particular topologically ordered spin systems proposed as resources for quantum information processing tasks, often involve highly nonlocal interaction terms. While one may approximate such systems through two-body interactions perturbatively, these approaches have a number of drawbacks in practice. In this Letter, we propose a scheme to simulate many-body spin Hamiltonians with two-body Hamiltonians nonperturbatively. Unlike previous approaches, our Hamiltonians are not only exactly solvable with exact ground state degeneracy, but also support completely localized quasiparticle excitations, which are ideal for quantum information processing tasks. Our construction is limited to simulating the toric code and quantum double models, but generalizations to other nonlocal spin Hamiltonians may be possible.
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.
Determining properties of ground states of spin Hamiltonians remains a topic of central relevance connecting disciplines of mathematical, theoretical and applied physics. In the last few decades, ground state properties of physical systems have been increasingly considered as computational resources. This thesis develops parts of the mathematical apparatus to create (program) ground states relevant for quantum and classical computation. The core findings presented in this thesis (now over a decade old) including that (i) logic operations (gates) can be embedded into the low-energy sector of Ising spins whereas three (and higher) body Ising interaction terms can be mimicked through the minimisation of 2- and 1-body Ising terms yet require the introduction of slack spins; (ii) Perturbation theory gadgets enable the emulation of interactions not present in a given Hamiltonian, e.g.~YYYYYY interactions can be realized from ZZZZZZ, XXXXXX, the thesis contains a result from 2007 showing that physically relevant two-body model Hamiltonian's have a QMA-hard ground state energy decision problem. Merged with other results, this established that these models provide a universal resource for ground state quantum computation. More recent findings include the proof that an idealised version of the contemporary variational approach to quantum algorithms enables a universal model of quantum computation. Other related results are also presented as they relate to ground state quantum computation and the minimisation of Hamiltonians by quantum circuits. The topics covered include: Ising model reductions, stochastic versus quantum processes on graphs, quantum gates and circuits as tensor networks, variational quantum algorithms and Hamiltonian gadgets.