A Caltech Library Service

Behavior of O(log n) Local Commuting Hamiltonians


Mehta, Jenish C. (2016) Behavior of O(log n) Local Commuting Hamiltonians. Master's thesis, California Institute of Technology. doi:10.7907/Z9V98611.


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.

Item Type:Thesis (Master's thesis)
Subject Keywords:Local, Hamiltonian, problem, commuting, ground, space, connectivity, area, law, structure, theorem
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Vidick, Thomas G. (advisor)
  • Schulman, Leonard J. (advisor)
Thesis Committee:
  • Unknown, Unknown
Defense Date:31 May 2016
Non-Caltech Author Email:jenishc (AT)
Record Number:CaltechTHESIS:05272016-141059835
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9792
Deposited By: Jenish Mehta
Deposited On:01 Jun 2016 20:46
Last Modified:04 Oct 2019 00:13

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page