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:1802.07130 · Communications in Mathematical Physics

Universal Qudit Hamiltonians

Stephen Piddock, Ashley Montanaro

Published Feb 23, 2021• 22 citations
arXivHTMLPDF

Abstract

Abstract A family of quantum Hamiltonians is said to be universal if any other finite-dimensional Hamiltonian can be approximately encoded within the low-energy space of a Hamiltonian from that family. If the encoding is efficient, universal families of Hamiltonians can be used as universal analogue quantum simulators and universal quantum computers, and the problem of approximately determining the ground-state energy of a Hamiltonian from a universal family is QMA-complete. One natural way to categorise Hamiltonians into families is in terms of the interactions they are built from. Here we prove universality of some important classes of interactions on qudits (d-level systems): We completely characterise the k-qudit interactions which are universal, if augmented with arbitrary Hermitian 1-local terms. We find that, for all $$k \geqslant 2$$ k ⩾ 2 and all local dimensions $$d \geqslant 2$$ d ⩾ 2 , almost all such interactions are universal aside from a simple stoquastic class. We prove universality of generalisations of the Heisenberg model that are ubiquitous in condensed-matter physics, even if free 1-local terms are not provided. We show that the SU(d) and SU(2) Heisenberg interactions are universal for all local dimensions $$d \geqslant 2$$ d ⩾ 2 (spin $$\geqslant 1/2$$ ⩾ 1 / 2 ), implying that a quantum variant of the Max-d-Cut problem is QMA-complete. We also show that for $$d=3$$ d = 3 all bilinear-biquadratic Heisenberg interactions are universal. One example is the general AKLT model. We prove universality of any interaction proportional to the projector onto a pure entangled state.

DOI
10.1007/s00220-021-03940-3

Related papers

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

Simulating Hamiltonian dynamics using many-qudit Hamiltonians and local unitary control

Michael J. Bremner, Dave Bacon, Michael A. Nielsen

When can a quantum system of finite dimension be used to simulate another quantum system of finite dimension? What restricts the capacity of one system to simulate another? In this paper we complete the program of studying what simulations can be done with entangling many-qudit Hamiltonians and local unitary control. By entangling we mean that every qudit is coupled to every other qudit, at least indirectly. We demonstrate that the only class of finite-dimensional entangling Hamiltonians that are not universal for simulation is the class of entangling Hamiltonians on qubits whose Pauli operator expansion contains only terms coupling an odd number of systems, as identified by Bremner et al. [Phys. Rev. A 69, 012313 (2004)]. We show that in all other cases entangling many-qudit Hamiltonians are universal for simulation.

arXiv:quant-ph/0405115•Physical Review A•May 9, 2005•18 citations

Universality in quantum computation

Jennifer L. Dodd

A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers.        The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected.       This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate.       Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.

•Jan 1, 2004•7 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

Universal simulation of Hamiltonian dynamics for quantum systems with finite-dimensional state spaces

Michael A. Nielsen, Michael J. Bremner, Jennifer L. Dodd +2 more

What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? Dodd et al. [Phys. Rev. A 65, 040301(R) (2002)] provided a partial solution to this problem in the form of an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling N-qubit Hamiltonian, and local unitaries. We extend this result to the case where the component systems are qudits, that is, have D dimensions. As a consequence we explain how universal quantum computation can be performed with any fixed two-body entangling N-qudit Hamiltonian, and local unitaries.

arXiv:quant-ph/0109064•Physical Review A•Aug 30, 2002•134 citations

Universality of swap for qudits: a representation theory approach

James R. van Meter

An open problem of quantum information theory has been to determine under what conditions universal exchange-only computation is possible for qudits encoded on $d$-state systems for $d>2$. This problem can be posed in terms of representation theory by recognizing that each quantum mechanical swap, generated by exchange-interaction, can be identified with a transposition in a symmetric group, each $d$-state system can be identified with the fundamental representation of $SU(d)$, and each encoded qudit can be identified with an irreducible representation of a Lie algebra generated by transpositions. Towards this end we first give a mathematical definition of exchange-only universality in terms of a map from the special unitary algebra on the product of qudits into a representation of a Lie algebra generated by transpositions. We show that this definition is consistent with quantum computing requirements. We then proceed with the task of characterizing universal families of qudits, that is families of encoded qudits admitting exchange-only universality. This endeavor is aided by the fact that the irreducible representations corresponding to qudits are canonically labeled by partitions. In particular we derive necessary and sufficient conditions for universality on one or two such qudits, in terms of simple arithmetic conditions on the associated partitions. We also derive necessary and sufficient conditions for universality on arbitrarily many such qudits, in terms of Littlewood--Richardson coefficients. Among other results, we prove that universal families of multiple qudits are upward closed, that universality is guaranteed for sufficiently many qudits, and that any family that is not universal can be made so by simply adding at most five ancillae. We also obtain results for 2-state systems as a special case.

arXiv:2103.12303•Mar 23, 2021•5 citations
Abstract A family of quantum Hamiltonians is said to be universal if any other finite-dimensional Hamiltonian can be approximately encoded within the low-energy space of a Hamiltonian from that family. If the encoding is efficient, universal families of Hamiltonians can be used as universal analogue quantum simulators and universal quantum computers, and the problem of approximately determining the ground-state energy of a Hamiltonian from a universal family is QMA-complete. One natural way to categorise Hamiltonians into families is in terms of the interactions they are built from. Here we prove universality of some important classes of interactions on qudits (d-level systems): We completely characterise the k-qudit interactions which are universal, if augmented with arbitrary Hermitian 1-local terms. We find that, for all k⩾2k \geqslant 2k⩾2 k ⩾ 2 and all local dimensions d⩾2d \geqslant 2d⩾2 d ⩾ 2 , almost all such interactions are universal aside from a simple stoquastic class. We prove universality of generalisations of the Heisenberg model that are ubiquitous in condensed-matter physics, even if free 1-local terms are not provided. We show that the SU(d) and SU(2) Heisenberg interactions are universal for all local dimensions d⩾2d \geqslant 2d⩾2 d ⩾ 2 (spin ⩾1/2\geqslant 1/2⩾1/2 ⩾ 1 / 2 ), implying that a quantum variant of the Max-d-Cut problem is QMA-complete. We also show that for d=3d=3d=3 d = 3 all bilinear-biquadratic Heisenberg interactions are universal. One example is the general AKLT model. We prove universality of any interaction proportional to the projector onto a pure entangled state.
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-
When can a quantum system of finite dimension be used to simulate another quantum system of finite dimension? What restricts the capacity of one system to simulate another? In this paper we complete the program of studying what simulations can be done with entangling many-qudit Hamiltonians and local unitary control. By entangling we mean that every qudit is coupled to every other qudit, at least indirectly. We demonstrate that the only class of finite-dimensional entangling Hamiltonians that are not universal for simulation is the class of entangling Hamiltonians on qubits whose Pauli operator expansion contains only terms coupling an odd number of systems, as identified by Bremner et al. [Phys. Rev. A 69, 012313 (2004)]. We show that in all other cases entangling many-qudit Hamiltonians are universal for simulation.
A quantum computer is similar to an ordinary computer, except that instead of bits it uses two-level quantum systems (qubits), and the usual logical operations on bits are replaced with noiseless quantum dynamics in the form of unitary gates or Hamiltonian interactions. Many sets of resources that are universal for quantum computation (that is, capable of implementing any quantum computation) have been found, but general conditions for universality are still only partially understood. Improving our understanding of these conditions contributes to two broad goals. On the one hand, understanding what class of physical systems is suitable for quantum computation allows us choose the systems that are most easily controlled or built in the laboratory. On the other hand, identifying the unifying characteristics of such a class provides insight into the fundamental physics responsible for the much greater computational power of quantum computers.        The original results presented in this thesis are a contribution to our understanding of the physical requirements for universal quantum computation. These results lead to the identification of a new, large class of universal dynamics. More specifically, the main problem that is addressed is the following: consider a physical system that is made up of a finite number of qubits that are subject to a natural, fixed interaction described by a two-body Hamiltonian. Suppose we have the ability to control the system only by applying fast one-qubit operations. Under what conditions is this system capable of universal quantum computation? The first original result of the thesis is to prove that universal quantum computation is possible under these conditions given the single extra constraint that the Hamiltonian must entangle, or connect, all of the qubits. In other words, since a two-body Hamiltonian is expressible as a sum of coupling terms each of which acts nontrivially on a pair of qubits, consider the graph whose vertices correspond to qubits and whose edges connect qubits that are coupled by a term in the Hamiltonian. Then this Hamiltonian, together with fast one-qubit unitaries, is universal for quantum computation precisely when the corresponding graph is connected.       This result suggests many potential generalizations, three of which are explored in this thesis. The first generalization is to show that the same result holds for a two-body Hamiltonian that acts on D-dimensional quantum systems (qudits), given fast one-qudit unitaries. A second extension is to the case of a many-body Hamiltonian, that is, a Hamiltonian that has coupling terms that act on more than two qubits. Again, we find that under mild restrictions, such Hamiltonians are universal provided they are connected and that arbitrary one-qubit unitaries are available. We also discover and explore some surprising structure in many-body Hamiltonians that is associated with the parity of the couplings. A third related problem that is addressed is the question of what two-qubit unitaries are universal for quantum computation. This problem was originally solved by J.-L. and R. Brylinski [BB02], who gave a technical proof of the universality of any two-qudit gate that is not the swap gate or a product of one-qudit unitaries, given one-qudit unitaries as a free resource. We develop an elementary and constructive proof for the case of qubits, and prove that our construction is very close to optimal in the number of uses of the two-qubit gate.       Given a qualitative understanding of what dynamical resources are universal for quantum computation, it is natural to consider developing a quantitative measure of the usefulness of quantum dynamics for quantum information processing. This is done in the final chapter of the thesis, in which the beginnings of a quantitative theory of quantum dynamics are developed.
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.
What interactions are sufficient to simulate arbitrary quantum dynamics in a composite quantum system? Dodd et al. [Phys. Rev. A 65, 040301(R) (2002)] provided a partial solution to this problem in the form of an efficient algorithm to simulate any desired two-body Hamiltonian evolution using any fixed two-body entangling N-qubit Hamiltonian, and local unitaries. We extend this result to the case where the component systems are qudits, that is, have D dimensions. As a consequence we explain how universal quantum computation can be performed with any fixed two-body entangling N-qudit Hamiltonian, and local unitaries.
An open problem of quantum information theory has been to determine under what conditions universal exchange-only computation is possible for qudits encoded on ddd-state systems for d>2d>2d>2. This problem can be posed in terms of representation theory by recognizing that each quantum mechanical swap, generated by exchange-interaction, can be identified with a transposition in a symmetric group, each ddd-state system can be identified with the fundamental representation of SU(d)SU(d)SU(d), and each encoded qudit can be identified with an irreducible representation of a Lie algebra generated by transpositions. Towards this end we first give a mathematical definition of exchange-only universality in terms of a map from the special unitary algebra on the product of qudits into a representation of a Lie algebra generated by transpositions. We show that this definition is consistent with quantum computing requirements. We then proceed with the task of characterizing universal families of qudits, that is families of encoded qudits admitting exchange-only universality. This endeavor is aided by the fact that the irreducible representations corresponding to qudits are canonically labeled by partitions. In particular we derive necessary and sufficient conditions for universality on one or two such qudits, in terms of simple arithmetic conditions on the associated partitions. We also derive necessary and sufficient conditions for universality on arbitrarily many such qudits, in terms of Littlewood--Richardson coefficients. Among other results, we prove that universal families of multiple qudits are upward closed, that universality is guaranteed for sufficiently many qudits, and that any family that is not universal can be made so by simply adding at most five ancillae. We also obtain results for 2-state systems as a special case.