The power of quantum systems on a line

Thursday, October 18, 2007 - 4:30pm
Skiles 269
Sandy Irani
Computer Science Department, UC Irvine

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