[quantum-info] Colloquium Institute for Quantum Computing Monday, 2 June 2014 at 2:30PM QNC 1506
Matthew Fries
mfries at uwaterloo.ca
Fri May 30 14:17:02 EDT 2014
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.
More information about the quantum-info
mailing list