A universal Hamiltonian simulator: the full characterization

We show that if the ground state energy problem of a
classical spin model is NP-hard, then there exists a choice parameters of the
model such that its low energy spectrum coincides with the spectrum of
\emph{any} other model, and, furthermore, the corresponding eigenstates match
on a subset of its spins. This implies that all spin physics, for example all
possible universality classes, arise in a single model. The latter property was
recently introduced and called ``Hamiltonian completeness'', and it was shown
that several different models had this property. We thus show that Hamiltonian
completeness is essentially equivalent to the more familiar
complexity-theoretic notion of NP-completeness. Additionally, we also show that
Hamiltonian completeness implies that the partition functions are the same.
These results allow us to prove that the 2D Ising model with fields is
Hamiltonian complete, which is substantially simpler than the previous examples
of complete Hamiltonians. Joint work with Toby Cubitt.

Event Type: 
Scientific Area(s): 
Event Date: 
Monday, November 11, 2013 - 16:00 to 17:30
Time Room
Room #: