<p>The <a href="http://en.wikipedia.org/wiki/Hubbard_model" rel="nofollow noreferrer">Hubbard model</a> (see also the wikipedea article on the <a href="http://en.wikipedia.org/wiki/Bose%E2%80%93Hubbard_model" rel="nofollow noreferrer">Bose-Hubbard model</a>) is a basic quantum model of solid-state physics. </p>

<p>Question: What is the computational complexity of approximating the ground state of a 2-D Hubbard model? </p>

<p>Remarks:  </p>

<p>1) This question is inspired by lecture-series by <strong>Frank Verstraete</strong> in Jerusalem. (<a href="http://www.youtube.com/playlist?list=PLTn74Qx5mPsRlH0Ex_eqD6HVEunhzIQXC" rel="nofollow noreferrer">See here for the videotaped lectures</a>.) </p>

<p>2) The question is a "tiny input" question, (see this question:<a href="https://cstheory.stackexchange.com/questions/19189/counting-isomorphism-types-of-graphs">Counting Isomorphism Types of Graphs</a>  ) so hardness result for questions of this kind is largely an uncharted territory.</p>

<p>We can ask: </p>

<p>1) is there a polynomial time algorithm? </p>

<p>2) Is there a polynomial time quantum algorithm? </p>

<p>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.</p>

<p>3) Is the problem in NP?</p>

CC BY-SA 3.0
2014-01-20T09:29:44.660Z
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?
Norbert Schuch
CC BY-SA 3.0
2014-01-20T13:07:08.807Z
Dear Norbert, Yes yes, it should be polynomial in the latic size not its logarithm...
Gil Kalai
CC BY-SA 3.0
2014-01-20T16:58:15.307Z
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.
Peter Shor 
CC BY-SA 3.0
2014-01-20T17:02:26.363Z
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..)
Gil Kalai
CC BY-SA 3.0
2014-01-20T17:17:59.310Z
@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.
Peter Shor 
<quantum-computing>
How hard it is to approximate the ground state of the (2-D) Hubbard model
Gil Kalai
# How hard it is to approximate the ground state of the (2-D) Hubbard model

(Asked by: username_0 on 2014-01-19)

The [Hubbard model](http://en.wikipedia.org/wiki/Hubbard_model) (see also the wikipedea article on the [Bose-Hubbard model](http://en.wikipedia.org/wiki/Bose%E2%80%93Hubbard_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](http://www.youtube.com/playlist?list=PLTn74Qx5mPsRlH0Ex_eqD6HVEunhzIQXC).)

2) The question is a "tiny input" question, (see this question:[Counting Isomorphism Types of Graphs](https://cstheory.stackexchange.com/questions/19189/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?

**Tags:** quantum-computing

> **Comments:**
> **username_1**: 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?  
> **username_0**: Dear Norbert, Yes yes, it should be polynomial in the latic size not its logarithm...  
> **username_2**: 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.  
> **username_0**: 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..)  
> **username_2**: @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.  

---

## 0 answers

