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:1111.5247 · IEEE Conference on Computational Complexity (CCC)

The Complexity of the Separable Hamiltonian Problem

André Chailloux, Or Sattath

Published Jun 1, 2012• 10 citations
arXivHTMLPDF

Abstract

In this paper, we study variants of the canonical Local Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local Hamiltonian problem. The input for the Separable Local Hamiltonian problem is the same as the Local Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable Sparse Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable Sparse Hamiltonian problem is QMA(2)-Complete, while Separable Local Hamiltonian is in QMA. This should be compared to the Local Hamiltonian problem, and the Sparse Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable Sparse Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.

DOI
10.1109/ccc.2012.42

Related papers

The complexity of the separable hamiltonian problem

André Chailloux, Or Sattath

In this paper, we study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.

•Jan 1, 2012•14 citations

On the complexity of estimating ground state entanglement and free energy

Sevag Gharibian, Jonas Kamminga

Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).

arXiv:2510.06796•Oct 8, 2025•0 citations

The local Hamiltonian problem on a line with eight states is QMA-complete

HallgrenSean, NagajDaniel, NarayanaswamiSandeep

The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which w...

Quantum Information and Computation•Sep 1, 2013•0 citations

The Complexity of the Consistency and N-representability Problems for Quantum States

Liu, Yi-Kai

QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices'': given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian'' and ``N-representability,'' are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960's, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic'' systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.

arXiv:0712.3041•Dec 18, 2007•19 citations

The Complexity of Stoquastic Sparse Hamiltonians

Alex B. Grilo, Marios Rozos

Despite having an unnatural definition, $\mathsf{StoqMA}$ plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of $\mathsf{NP}$, $\mathsf{MA}$ and $\mathsf{AM}$. Therefore, understanding the exact power of $\mathsf{StoqMA}$ (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem ($\mathsf{StoqSH}$) is in $\mathsf{StoqMA}$. Since Stoquastic Local Hamiltonians are $\mathsf{StoqMA}$-hard, this implies that $\mathsf{StoqSH}$ is $\mathsf{StoqMA}$-complete. We complement this result by showing that the separable version of $\mathsf{StoqSH}$ is $\mathsf{StoqMA}(2)$-complete, where $\mathsf{StoqMA}(2)$ is the version of $\mathsf{StoqMA}$ that receives two unentangled proofs.

cs.CCCross-listedarXiv:2605.02845•May 5, 2026•0 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 has been shown to be StoqMA-complete by Bravyi and Hastings. 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.

arXiv:1311.3161•Nov 13, 2013•9 citations
In this paper, we study variants of the canonical Local Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local Hamiltonian problem. The input for the Separable Local Hamiltonian problem is the same as the Local Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable Sparse Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable Sparse Hamiltonian problem is QMA(2)-Complete, while Separable Local Hamiltonian is in QMA. This should be compared to the Local Hamiltonian problem, and the Sparse Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable Sparse Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.
In this paper, we study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).
QMA (Quantum Merlin-Arthur) is the quantum analogue of the class NP. There are a few QMA-complete problems, most notably the ``Local Hamiltonian'' problem introduced by Kitaev. In this dissertation we show some new QMA-complete problems. The first one is ``Consistency of Local Density Matrices'': given several density matrices describing different (constant-size) subsets of an n-qubit system, decide whether these are consistent with a single global state. This problem was first suggested by Aharonov. We show that it is QMA-complete, via an oracle reduction from Local Hamiltonian. This uses algorithms for convex optimization with a membership oracle, due to Yudin and Nemirovskii. Next we show that two problems from quantum chemistry, ``Fermionic Local Hamiltonian'' and ``N-representability,'' are QMA-complete. These problems arise in calculating the ground state energies of molecular systems. N-representability is a key component in recently developed numerical methods using the contracted Schrodinger equation. Although these problems have been studied since the 1960's, it is only recently that the theory of quantum computation has allowed us to properly characterize their complexity. Finally, we study some special cases of the Consistency problem, pertaining to 1-dimensional and ``stoquastic'' systems. We also give an alternative proof of a result due to Jaynes: whenever local density matrices are consistent, they are consistent with a Gibbs state.
Despite having an unnatural definition, StoqMA\mathsf{StoqMA}StoqMA plays a central role in Hamiltonian complexity, e.g., in the classification theorem of the complexity of Hamiltonians by Cubitt and Montanaro (SICOMP 2016). Moreover, it lies between the two randomized extensions of NP\mathsf{NP}NP, MA\mathsf{MA}MA and AM\mathsf{AM}AM. Therefore, understanding the exact power of StoqMA\mathsf{StoqMA}StoqMA (and hopefully collapsing it with more natural complexity classes) is of great interest for different reasons. In this work, we take a step further in understanding this complexity class by showing that the Stoquastic Sparse Hamiltonians problem (StoqSH\mathsf{StoqSH}StoqSH) is in StoqMA\mathsf{StoqMA}StoqMA. Since Stoquastic Local Hamiltonians are StoqMA\mathsf{StoqMA}StoqMA-hard, this implies that StoqSH\mathsf{StoqSH}StoqSH is StoqMA\mathsf{StoqMA}StoqMA-complete. We complement this result by showing that the separable version of StoqSH\mathsf{StoqSH}StoqSH is StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2)-complete, where StoqMA(2)\mathsf{StoqMA}(2)StoqMA(2) is the version of StoqMA\mathsf{StoqMA}StoqMA that receives two unentangled proofs.
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 has been shown to be StoqMA-complete by Bravyi and Hastings. 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.