The complexity of the commuting local Hamiltonians (CLH) problem still remains a mystery after two decades of research of quantum Hamiltonian complexity; it is only known to be contained in NP for few low parameters. Of particular interest is the tightly related question of understanding whether groundstates of CLHs can be generated by efficient quantum circuits. The two problems touch upon conceptual, physical and computational questions, including the centrality of non-commutation in quantum mechanics, quantum PCP and the area law. It is natural to try to address first the more physical case of CLHs embedded on a 2D lattice but this problem too remained open, apart from some very specific cases. Here we consider a wide class of two dimensional CLH instances; these are
k-local CLHs, for any constant
k; they are defined on qubits set on the edges of any surface complex, where we require that this surface complex is not too far from being "Euclidean". Each vertex and each face can be associated with an arbitrary term (as long as the terms commute). We show that this class is in NP, and moreover that the groundstates have an efficient quantum circuit that prepares them. This result subsumes that of Schuch [2011] which regarded the special case of
4-local Hamiltonians on a grid with qubits, and by that it removes the mysterious feature of Schuch's proof which showed containment in NP without providing a quantum circuit for the groundstate and considerably generalizes it. We believe this work and the tools we develop make a significant step towards showing that 2D CLHs are in NP.
Quantum Hamiltonian complexity studies computational complexity aspects of local Hamiltonians and ground states; these questions can be viewed as generalizations of classical computational complexity problems related to local constraint satisfaction (such as SAT), with the additional ingredient of multi-particle entanglement. This additional ingredient of course makes generalizations of celebrated theorems such as the PCP theorem from classical to the quantum domain highly non-trivial; it also raises entirely new questions such as bounds on entanglement and correlations in ground states, and in particular area laws. We propose a simple combinatorial tool that helps to handle such questions: it is a simplified, yet more general version of the detectability lemma introduced by us in the more restricted context on quantum gap amplification a year ago. Here, we argue that this lemma is applicable in much more general contexts. We use it to provide a simplified and more combinatorial proof of Hastings' 1D area law, together with a less than 1 page proof of the decay of correlations in gapped local Hamiltonian systems in any constant dimension. We explain how the detectability lemma can replace the Lieb-Robinson bound in various other contexts, and argue that it constitutes a basic tool for the study of local Hamiltonians and their ground states in relation to various questions in quantum Hamiltonian complexity.
Classical spin Hamiltonians are a powerful tool to model complex systems, characterized by a local structure given by the local Hamiltonians. One of the best understood local structures is the grammar of formal languages, which are central in computer science and linguistics, and have a natural complexity measure given by the Chomsky hierarchy. If we see classical spin Hamiltonians as languages, what grammar do the local Hamiltonians correspond to? Here, we cast classical spin Hamiltonians as formal languages, and classify them in the Chomsky hierarchy. We prove that the language of (effectively) zero-dimensional spin Hamiltonians is regular, one-dimensional spin Hamiltonians is deterministic context-free, and higher-dimensional and all-to-all spin Hamiltonians is context-sensitive. This provides a new complexity measure for classical spin Hamiltonians, which captures the hardness of recognizing spin configurations and their energies. We compare it with the computational complexity of the ground state energy problem, and find a different easy-to-hard threshold for the Ising model. We also investigate the dependence on the language of the spin Hamiltonian. Finally, we define the language of the time evolution of a spin Hamiltonian and classify it in the Chomsky hierarchy. Our work suggests that universal spin models are weaker than universal Turing machines.