Question: What is the computational complexity of approximating the ground state of a 2-D Hubbard model?
1) This question is inspired by lecture-series by Frank Verstraete in Jerusalem. (See here for the videotaped lectures.)
2) The question is a "tiny input" question, (see this question:Counting Isomorphism Types of Graphs ) so hardness result for questions of this kind is largely an uncharted territory.
We can ask:
1) is there a polynomial time algorithm?
2) Is there a polynomial time quantum algorithm?
Frank suggested that algorithms based on adiabatic evolution (starting from a product state) would work, since gaps at phase transitions typically only scale as 1/poly in the system size, (which keeps it in BQP). My question is if this is known/proven.
3) Is the problem in NP?