In this talk, we discuss the computational strength of finite dimensional quantum particles arranged on a line. We prove that adiabatic computation is equivalent to standard quantum computation even when the adiabatic quantum system is restricted to 2-local interactions of nearest neighbors on a line. The particles in this construction require 9 states per particle. We then adapt this construction to show that the 2-local Hamiltonian for 12 state particles on a line is QMA-complete. QMA is the quantum analog of NP. This result contrasts with the classical analog in which one-dimensional Max-2-SAT with nearest neighbor constraints is in known to be in P. Similar results were obtained independently by Aharonov, Gottesman and Kempe. The work appears jointly in FOCS 2007.
Refreshments at 4:00PM in Skiles 236
