Theory of Computing
-------------------
Title : The Bose-Hubbard Model is QMA-complete
Authors : Andrew M. Childs, David Gosset, and Zak Webb
Volume : 11
Number : 20
Pages : 491-603
URL : https://theoryofcomputing.org/articles/v011a020
Abstract
--------
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. The
Hamiltonian is determined by a choice of graph that specifies the
geometry in which the particles move and interact. We prove that
approximating the ground energy of the Bose-Hubbard model on a graph
at fixed particle number is QMA-complete. In our QMA-hardness proof,
we encode the history of an n-qubit computation in the subspace with
at most one particle per site (i.e., hard-core bosons). This feature,
along with the well-known mapping between hard-core bosons and spin
systems, lets us prove a related result for a class of 2-local
Hamiltonians defined by graphs that generalizes the XY model. By
avoiding the use of perturbation theory in our analysis, we circumvent
the need to multiply terms in the Hamiltonian by large coefficients.