We consider the computational complexity of Hamiltonians which are sums of commuting terms acting on plaquettes in a square lattice of qubits, and we show that deciding whether the ground state minimizes the energy of each local term individually is in the complexity class NP. That is, if the ground states has this property, this can be proven using a classical certificate which can be efficiently verified on a classical computer. Different to previous results on commuting Hamiltonians, our certificate proves the existence of such a state without giving instructions on how to prepare it.We consider the computational complexity of Hamiltonians which are sums of commuting terms acting on plaquettes in a square lattice of qubits, and we show that deciding whether the ground state minimizes the energy of each local term individually is in the complexity class NP. That is, if the ground states has this property, this can be proven using a classical certificate which can be efficiently verified on a classical computer. Different to previous results on commuting Hamiltonians, our certificate proves the existence of such a state without giving instructions on how to prepare it.

Quantum Information and ComputationNov 1, 201136 citations

Complexity of commuting Hamiltonians on a square lattice of qubits

SchuchNorbert

Quantum Information and ComputationNov 1, 20112 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

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

QCMA hardness of ground space connectivity for commuting Hamiltonians

David Gosset, Jenish C. Mehta, Thomas Vidick

In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H . It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.In this work we consider the ground space connectivity problem for commuting local Hamiltonians. The ground space connectivity problem asks whether it is possible to go from one (efficiently preparable) state to another by applying a polynomial length sequence of 2-qubit unitaries while remaining at all times in a state with low energy for a given Hamiltonian H . It was shown in [Gharibian and Sikora, ICALP15] that this problem is QCMA-complete for general local Hamiltonians, where QCMA is defined as QMA with a classical witness and BQP verifier. Here we show that the commuting version of the problem is also QCMA-complete. This provides one of the first examples where commuting local Hamiltonians exhibit complexity theoretic hardness equivalent to general local Hamiltonians.

arXiv:1610.03582QuantumJul 14, 201710 citations

The k-local Pauli Commuting Hamiltonians Problem is in P

Jijiang Yan, Dave Bacon

Given a Hamiltonian that is a sum of commuting few-body terms, the commuting Hamiltonian problem is to determine if there exists a quantum state that is the simultaneous eigenstate of all of these terms that minimizes each term individually. This problem is known to be in the complexity class quantum Merlin-Arthur, but is widely thought to not be complete for this class. Here we show that a limited form of this problem when the individual terms are all made up of tensor products of Pauli matrices is efficiently solvable on a classical computer and thus in the complexity class P. The problem can be thought of as the classical XOR-SAT problem over a symplectic vector space. This class of problems includes instance Hamiltonians whose ground states possess topological entanglement, thus showing that such entanglement is not always a barrier for the more general problem.Given a Hamiltonian that is a sum of commuting few-body terms, the commuting Hamiltonian problem is to determine if there exists a quantum state that is the simultaneous eigenstate of all of these terms that minimizes each term individually. This problem is known to be in the complexity class quantum Merlin-Arthur, but is widely thought to not be complete for this class. Here we show that a limited form of this problem when the individual terms are all made up of tensor products of Pauli matrices is efficiently solvable on a classical computer and thus in the complexity class P. The problem can be thought of as the classical XOR-SAT problem over a symplectic vector space. This class of problems includes instance Hamiltonians whose ground states possess topological entanglement, thus showing that such entanglement is not always a barrier for the more general problem.

arXiv:1203.3906Mar 17, 20127 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.