10
$\begingroup$

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?

Remarks:

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?

Improve this question
$\endgroup$
5
  • 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, 2014 at 9:29
  • $\begingroup$ Dear Norbert, Yes yes, it should be polynomial in the latic size not its logarithm... $\endgroup$
    – Gil Kalai
    Jan 20, 2014 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, 2014 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, 2014 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, 2014 at 17:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.