The Hubbard model (see also the wikipedea article on the Bose-Hubbard model) is a basic quantum model of solid-state physics.

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?

  • 1
    $\begingroup$ I assume you are talking about the translational invariant scenario? In that case, is question 2 whether the ground state can be found in time polynomial in the lattice size (Frank's argument seems to point in that direction), or whether it is in BQP, i.e., poly in the size of the input? In the latter case: What would the input be -- the lattice size? $\endgroup$ – Norbert Schuch Jan 20 '14 at 9:29
  • $\begingroup$ Dear Norbert, Yes yes, it should be polynomial in the latic size not its logarithm... $\endgroup$ – Gil Kalai Jan 20 '14 at 13:07
  • 3
    $\begingroup$ What do you mean by "approximating the ground state"? Do you mean "approximating the energy of the ground state"? Or "approximating the actual quantum ground state?" Or "finding an approximation to a quantum state which is close in energy to the ground state"? I believe nothing has been proved rigorously for any of these questions. $\endgroup$ – Peter Shor Jan 20 '14 at 16:58
  • $\begingroup$ Dear Peter, hmm good question. I think I meant the ground state, but the question about the energy also makes sense. I suppose that Frank's suggestion applies for both. (but somehow now there is a third option, which I am sure I did not consider..) $\endgroup$ – Gil Kalai Jan 20 '14 at 17:02
  • 3
    $\begingroup$ @Gil: the second and third options should be equivalent except near phase transitions, in which case the second option may be much too hard to lie in a reasonable complexity class, since you have to decide which side of the phase transition you're on; the third option is my suggestion for a way to get around this problem. $\endgroup$ – Peter Shor Jan 20 '14 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.