Computer Science/Discrete Mathematics Seminar I

The central problem of physics and quantum chemistry is to find the ground state energy of some physical system governed by quantum mechanics.  In mathematical terms, this means finding the lowest eigenvalue of some linear operator on a vector space with a tensor product structure.  Since the dimension of the vector space grows exponentially with the size of the physical system, the problem quickly becomes computationally intractable.  Semidefinite programming methods are one interesting way of approximating the solution.  Even these methods can become computationally difficult as the order of the semidefinite program increases, but low order methods can provide useful information.  I will review some of these methods, and give some positive and negative results showing their power and limitations on various physical systems.  Finally, I will explain an interesting new graph invariant suggested by these methods and give some preliminary results on that invariant.