[quantum-info] Colloquium Institute for Quantum Computing Monday, 2 June 2014 at 2:30PM QNC 1506

[Matthew Fries]

Colloquium

Institute for Quantum Computing

Monday, 2 June 2014 at 2:30PM

QNC 1506 PLEASE NOTE ROOM CHANGE

Ground state connectivity of local Hamiltonians

Sevag Gharibian

University of California, Berkeley

The study of ground spaces of local Hamiltonians is a fundamental task in condensed matter physics. In terms of computational complexity theory, a common focus in this area has been to estimate a given Hamiltonian’s ground state energy. However, from a physics perspective, it is often more relevant to understand the structure of the ground space itself. In this paper, we pursue the latter direction by introducing the notion of “ground state connectivity” of local Hamiltonians. In particular, we show that determining how “connected” the ground space of a local Hamiltonian is can range from QCMA-complete to PSPACE-complete. (Here, QCMA is the well-known variant of Quantum Merlin Arthur (QMA) in which the proof is classical.) As a result, we obtain a natural QCMA-complete problem, a task which has generally proven difficult since the conception of QCMA over a decade ago.

This talk is based on joint work with Jamie Sikora.