On the Commuting Local Hamiltonian Problem, and Tight Conditions on Topological Order

The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003 [10], using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend this result beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is planar and also "nearly Euclidean" in some well-defined sense. The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: the ground spaces of 3-local "physical" systems based on qubits and qutrits are diagonalizable by a basis whose entanglement is highly local, while even slightly more involved interactions (the particle dimensionality or the locality of the interaction is larger) already exhibit an important long-range entanglement property called Topological Order. Our results thus imply that Kitaev's celebrated Toric code construction is, in a well defined sense, optimal as a construction of Topological Order based on commuting Hamiltonians.

arXiv:1102.0770Annual Symposium on Foundations of Computer ScienceOct 1, 201156 citations

On the Complexity of Two Dimensional Commuting Local Hamiltonians

Dorit Aharonov, Kenneth, Oded, Itamar Vigdorovich

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

arXiv:1803.02213Leibniz international proceedings in informaticsJan 1, 20185 citations

New construction for a QMA complete three-local Hamiltonian

Daniel Nagaj, Shay Mozes

We present a new way of encoding a quantum computation into a three-local Hamiltonian. Our construction is novel in that it does not include any terms that induce legal-illegal clock transitions. Therefore, the weights of the terms in the Hamiltonian do not scale with the size of the problem as in previous constructions. This improves the construction by Kempe and Regev [Quantum Inf. Comput. 3, 258–264 (2003); e-print quant-ph∕0302079] who were the first to prove that three-local Hamiltonian is complete for the complexity class QMA, the quantum analog of NP. Quantum k-SAT, a restricted version of the local Hamiltonian problem using only projector terms, was introduced by Bravyi (e-print quant-ph∕0602108) as an analog of the classical k-SAT problem. Bravyi proved that quantum 4-SAT is complete for the class QMA with one-sided error (QMA1) and that quantum 2-SAT is in P. We give an encoding of a quantum circuit into a quantum 4-SAT Hamiltonian using only three-local terms. As an intermediate step to this three-local construction, we show that quantum 3-SAT for particles with dimensions 3×2×2 (a qutrit and two qubits) is QMA1 complete. The complexity of quantum 3-SAT with qubits remains an open question.We present a new way of encoding a quantum computation into a three-local Hamiltonian. Our construction is novel in that it does not include any terms that induce legal-illegal clock transitions. Therefore, the weights of the terms in the Hamiltonian do not scale with the size of the problem as in previous constructions. This improves the construction by Kempe and Regev [Quantum Inf. Comput. 3, 258–264 (2003); e-print quant-ph∕0302079] who were the first to prove that three-local Hamiltonian is complete for the complexity class QMA, the quantum analog of NP. Quantum k-SAT, a restricted version of the local Hamiltonian problem using only projector terms, was introduced by Bravyi (e-print quant-ph∕0602108) as an analog of the classical k-SAT problem. Bravyi proved that quantum 4-SAT is complete for the class QMA with one-sided error (QMA1) and that quantum 2-SAT is in P. We give an encoding of a quantum circuit into a quantum 4-SAT Hamiltonian using only three-local terms. As an intermediate step to this three-local construction, we show that quantum 3-SAT for particles with dimensions 3×2×2 (a qutrit and two qubits) is QMA1 complete. The complexity of quantum 3-SAT with qubits remains an open question.

arXiv:quant-ph/0612113Journal of Mathematical PhysicsJul 1, 200762 citations

Commuting Local Hamiltonians Beyond 2D

John Bostanci, Yeongwoo Hwang

Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit completely classical verifiers. Despite intense work, the largest class of commuting local Hamiltonians we can place in NP are those on a square lattice, where each lattice site is a qutrit. Even worse, many of the techniques used to analyze these problems rely heavily on the geometry of the square lattice and the properties of the numbers 2 and 3 as local dimensions. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan's Lemma and the Structure Lemma. Our rounding technique is much more flexible than previous work, and allows us to show that a larger family of commuting local Hamiltonians is in NP, albiet with the restriction that all terms are rank-1. Specifically, we prove the following two results: 1. Commuting local Hamiltonians in 2D that are rank-1 are contained in NP, independent of the qudit dimension. Note that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality. 2. We prove that rank-1, 3D commuting Hamiltonians with qudits on edges are in NP. To our knowledge this is the first time a family of 3D commuting local Hamiltonians has been contained in NP.Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit completely classical verifiers. Despite intense work, the largest class of commuting local Hamiltonians we can place in NP are those on a square lattice, where each lattice site is a qutrit. Even worse, many of the techniques used to analyze these problems rely heavily on the geometry of the square lattice and the properties of the numbers 2 and 3 as local dimensions. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan's Lemma and the Structure Lemma. Our rounding technique is much more flexible than previous work, and allows us to show that a larger family of commuting local Hamiltonians is in NP, albiet with the restriction that all terms are rank-1. Specifically, we prove the following two results: 1. Commuting local Hamiltonians in 2D that are rank-1 are contained in NP, independent of the qudit dimension. Note that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality. 2. We prove that rank-1, 3D commuting Hamiltonians with qudits on edges are in NP. To our knowledge this is the first time a family of 3D commuting local Hamiltonians has been contained in NP.

arXiv:2410.10495Oct 14, 20242 citations

Behavior of O(log n) Local Commuting Hamiltonians

Jenish C. Mehta

We study the variant of the k-local hamiltonian problem which is a natural generalization of k-CSPs, in which the hamiltonian terms all commute. More specifically, we consider a hamiltonian H over n qubits, where H is a sum of k-local terms acting non-trivially on O(log n) qubits, and all the k-local terms commute, and show the following - 1. We show that a specific case of O(log n) local commuting hamiltonians over the hypercube is in NP using the Bravyi-Vyalyi Structure theorem. 2. We give a simple proof of a generalized area law for commuting hamiltonians (which seems to be a folklore result) in all dimensions, and deduce the case for O(log n) local commuting hamiltonians. 3. We show that traversing the ground space of O(log n) local commuting hamiltonians is QCMA complete. The first two behaviours seem to indicate that deciding whether the ground space energy of O(log n)-local commuting hamiltonians is low or high might be in NP or possibly QCMA, though the last behaviour seems to indicate that it may indeed be the case that O(log n)-local commuting hamiltonians are QMA complete.We study the variant of the k-local hamiltonian problem which is a natural generalization of k-CSPs, in which the hamiltonian terms all commute. More specifically, we consider a hamiltonian H over n qubits, where H is a sum of k-local terms acting non-trivially on O(log n) qubits, and all the k-local terms commute, and show the following - 1. We show that a specific case of O(log n) local commuting hamiltonians over the hypercube is in NP using the Bravyi-Vyalyi Structure theorem. 2. We give a simple proof of a generalized area law for commuting hamiltonians (which seems to be a folklore result) in all dimensions, and deduce the case for O(log n) local commuting hamiltonians. 3. We show that traversing the ground space of O(log n) local commuting hamiltonians is QCMA complete. The first two behaviours seem to indicate that deciding whether the ground space energy of O(log n)-local commuting hamiltonians is low or high might be in NP or possibly QCMA, though the last behaviour seems to indicate that it may indeed be the case that O(log n)-local commuting hamiltonians are QMA complete.

Jun 1, 20161 citation

Complexity of Basis-Restricted Local Hamiltonians

Ma, Henry

A major goal of quantum complexity theory is to understand which computational problems can be solved with access to certain quantum resources. The subfield of Hamiltonian complexity specifically considers computational problems that ask about properties of local Hamiltonians, which are of critical importance in quantum complexity because they can be viewed as quantum generalizations of classical constraint satisfaction problems. In this work, we study the complexity of certain restricted variants of the Quantum-k-Sat problem, a quantum analog of the NP-complete k-Sat problem. We introduce new variants of Quantum-k-Sat which place a basis restriction on the input Hamiltonian H = Σᵢ hᵢ . Each variant is defined by a fixed collection of bases B₁, . . . , Bᵣ of n-qubit space. We require that each Hamiltonian term hi must be diagonal in one of these bases. Our results resolve the complexity of certaim basis-restricted variants of Quantum-k-Sat. First we show the Quantum-6-Sat problem with Hamiltonian terms restricted to be diagonal in an X/Z mixed basis is QMA₁-complete. Second, we combine basis restriction with the restriction of commutativity, and show the following easiness result, which applies generally to higher-level quantum systems (qudits) and bases Q and R (which are real-valued and satisfy an overlap condition): The commmuting Quantum-Sat problem on qudits, where Hamiltonian terms are either diagonal in the Q basis, the R basis, or a single mixed Q/R basis, is in NP.A major goal of quantum complexity theory is to understand which computational problems can be solved with access to certain quantum resources. The subfield of Hamiltonian complexity specifically considers computational problems that ask about properties of local Hamiltonians, which are of critical importance in quantum complexity because they can be viewed as quantum generalizations of classical constraint satisfaction problems. In this work, we study the complexity of certain restricted variants of the Quantum-k-Sat problem, a quantum analog of the NP-complete k-Sat problem. We introduce new variants of Quantum-k-Sat which place a basis restriction on the input Hamiltonian H = Σᵢ hᵢ . Each variant is defined by a fixed collection of bases B₁, . . . , Bᵣ of n-qubit space. We require that each Hamiltonian term hi must be diagonal in one of these bases. Our results resolve the complexity of certaim basis-restricted variants of Quantum-k-Sat. First we show the Quantum-6-Sat problem with Hamiltonian terms restricted to be diagonal in an X/Z mixed basis is QMA₁-complete. Second, we combine basis restriction with the restriction of commutativity, and show the following easiness result, which applies generally to higher-level quantum systems (qudits) and bases Q and R (which are real-valued and satisfy an overlap condition): The commmuting Quantum-Sat problem on qudits, where Hamiltonian terms are either diagonal in the Q basis, the R basis, or a single mixed Q/R basis, is in NP.

May 1, 20250 citations

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.