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

Complexity and simulation of many-body quantum systems

Stephen Piddock

Published Jan 1, 2019• 0 citations
OpenAlex

Abstract

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-

Related papers

Universal Qudit Hamiltonians

Stephen Piddock, Ashley Montanaro

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.

arXiv:1802.07130•Communications in Mathematical Physics•Feb 23, 2021•7 citations

Universal quantum Hamiltonians

Toby S. Cubitt, Ashley Montanaro, Stephen Piddock

Quantum many-body systems exhibit an extremely diverse range of phases and physical phenomena. However, we prove that the entire physics of any quantum many-body system can be replicated by certain simple, "universal" spin-lattice models. We first characterize precisely what it means for one quantum system to simulate the entire physics of another. We then fully classify the simulation power of all two-qubit interactions, thereby proving that certain simple models can simulate all others, and hence are universal. Our results put the practical field of analogue Hamiltonian simulation on a rigorous footing and take a step toward justifying why error correction may not be required for this application of quantum information technology.

arXiv:1701.05182•Proceedings of the National Academy of Sciences•Aug 30, 2018•98 citations

Complexity Classification of Local Hamiltonian Problems

Toby S. Cubitt, Ashley Montanaro

The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P, NP-complete, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms, for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.

Annual Symposium on Foundations of Computer Science•Oct 1, 2014•34 citations

Universal Translationally-Invariant Hamiltonians

Stephen Piddock, Johannes Bausch

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$.

arXiv:2001.08050•Jan 22, 2020•3 citations

Oracle Complexity Classes and Local Measurements on Physical Hamiltonians

Sevag Gharibian, Stephen Piddock, Justin Yirka

The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that APX-SIM is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^{QMA[log]}-complete, for P^{QMA[log]} the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^{QMA[log]}-complete even when restricted to physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model: - We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results. - Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^{||NP},P^{||StoqMA}, or P^{||QMA} depending on the Hamiltonians employed. - Leveraging the above, we show that APX-SIM is P^{QMA[log]}-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians. This implies APX-SIM is P^{QMA[log]}-complete even on physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^{QMA[log]}-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.

arXiv:1909.05981•Leibniz international proceedings in informatics•Sep 12, 2019•3 citations

Complexity Classification of Local Hamiltonian Problems

Toby S. Cubitt, Ashley Montanaro

The calculation of ground-state energies of physical systems can be formalized as the $k$-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set $\mathcal{S}$ and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset $\mathcal{S}$, the problem falls into one of the following categories: in $\mathsf{ P}$; $\mathsf{NP}$-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. The third of these classes has been shown to be $\mathsf{StoqMA}$-complete by Bravyi and Hastings. The characterization holds even if $\mathcal{S}$ does not contain any 1-local terms; for example, we prove for the first time $\mathsf{QMA}$-completeness of the Heisenberg and XY interactions in this setting. If $\mathcal{S}$ is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant $k$, all $k$-local qubit Hamiltonians whose terms are picked from a fixed set $\mathcal{S}$ correspond to problems either in $\mathsf{P}$; polynomial-time equivalent to the Ising model with transverse magnetic fields; or $\mathsf{QMA}$-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.

SIAM Journal on Computing•Jan 1, 2016•75 citations
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-
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.
Quantum many-body systems exhibit an extremely diverse range of phases and physical phenomena. However, we prove that the entire physics of any quantum many-body system can be replicated by certain simple, "universal" spin-lattice models. We first characterize precisely what it means for one quantum system to simulate the entire physics of another. We then fully classify the simulation power of all two-qubit interactions, thereby proving that certain simple models can simulate all others, and hence are universal. Our results put the practical field of analogue Hamiltonian simulation on a rigorous footing and take a step toward justifying why error correction may not be required for this application of quantum information technology.
The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterise the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P, NP-complete, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms, for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P, polynomial-time equivalent to the Ising model with transverse magnetic fields, or QMA-complete. These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.
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.
The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that APX-SIM is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^{QMA[log]}-complete, for P^{QMA[log]} the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^{QMA[log]}-complete even when restricted to physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model: - We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results. - Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^{||NP},P^{||StoqMA}, or P^{||QMA} depending on the Hamiltonians employed. - Leveraging the above, we show that APX-SIM is P^{QMA[log]}-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians. This implies APX-SIM is P^{QMA[log]}-complete even on physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^{QMA[log]}-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.
The calculation of ground-state energies of physical systems can be formalized as the kkk-local Hamiltonian problem, which is a natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S\mathcal{S}S and scaling them by arbitrary weights. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics. In this work we characterize the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S\mathcal{S}S, the problem falls into one of the following categories: in P\mathsf{ P}P; NP\mathsf{NP}NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA\mathsf{QMA}QMA-complete. The third of these classes has been shown to be StoqMA\mathsf{StoqMA}StoqMA-complete by Bravyi and Hastings. The characterization holds even if S\mathcal{S}S does not contain any 1-local terms; for example, we prove for the first time QMA\mathsf{QMA}QMA-completeness of the Heisenberg and XY interactions in this setting. If S\mathcal{S}S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterization that goes beyond 2-local interactions: for any constant kkk, all kkk-local qubit Hamiltonians whose terms are picked from a fixed set S\mathcal{S}S correspond to problems either in P\mathsf{P}P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA\mathsf{QMA}QMA-complete. These results are a quantum analogue of the maximization variant of Schaefer's dichotomy theorem for Boolean constraint satisfaction problems.