Tuesday, November 19, 2013
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.