Dr. Oded Regev, Dept. of Computer Science, Tel Aviv University

Date: Nov. 12, 2006

Title: Hamiltonian Problems and Quantum Computation

Abstract:

I will describe the recent progress in understanding the computational
difficulty of Hamiltonian problems.  One such typical problem is:
"Given a local Hamiltonian, compute its lowest eigenvalue" where a
local Hamiltonian is a Hamiltonian that can be written as the sum of
Hamiltonians acting on, say, two qubits each.

As we will see, such Hamiltonian problems are the quantum analogues of
NP-complete problems. I will also describe the closely related model
of adiabatic quantum computation.