CaltechTHESIS
  A Caltech Library Service

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. http://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.

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:
  • None, None
Defense Date:31 May 2016
Non-Caltech Author Email:jenishc (AT) gmail.com
Record Number:CaltechTHESIS:05272016-141059835
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:05272016-141059835
DOI:10.7907/Z9V98611
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9792
Collection:CaltechTHESIS
Deposited By: Jenish Mehta
Deposited On:01 Jun 2016 20:46
Last Modified:01 Jun 2016 20:46

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

273Kb

Repository Staff Only: item control page