Behavior of O(log n) Local Commuting Hamiltonians

Citation

Mehta, Jenish C. (2016) Behavior of O(log n) Local Commuting Hamiltonians. Master's thesis, California Institute of Technology. doi:10.7907/Z9V98611. https://resolver.caltech.edu/CaltechTHESIS:05272016-141059835

Abstract

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.

Thesis Files