Tuesday, November 19, 2013
3:00 pm
Annenberg 105

Institute for Quantum Information Seminar

The Bose-Hubbard model on a graph is QMA-complete
David Gosset, University of Waterloo

The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. We prove that approximating the ground energy of the Bose-Hubbard model on a graph (at fixed particle number) is QMA-complete. Our QMA-hardness proof encodes an n-qubit computation in the subspace of n hard-core bosons with at most one particle per site, so it holds for any fixed repulsive interaction strength. This feature, along with the well-known mapping between hard-core bosons and spin systems, also allows us to prove a related result for a class of 2-local Hamiltonians defined by graphs (a generalization of the XY model).

This is joint work with Andrew Childs.

Contact Ann Harvey aharvey@caltech.edu at 626-395-4964
Add this event to my calendar