4
$\begingroup$

Naturally, in general, ground state preparation is QMA-complete. There exists a paper by Andrew Childs, David Gosset & Zak Webb, which shows that ground state preparation for the Bose-Hubbard model is QMA-complete.

However, is it known what the complexity of ground state preparation for the Fermi-Hubbard model is? I could not find this in the literature directly, does this follow trivially from a general result which I am missing?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

In this paper, Schuch and Verstraete determined the computational complexity of finding the ground state of the Fermi-Hubbard model, showing that it is among the hardest problems in the complexity class QMA, Quantum Merlin Arthur.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is very helpful, thank you! (will upvote as soon as I have the reputation) But if I understand correctly, strictly speaking, this completeness proof works only for the Fermi-Hubbard Hamiltonian with local magnetic fields $H_{\mathrm{Hubb}}=-t \sum_{\langle i, j\rangle, s} a_{i, s}^{\dagger} a_{j, s}+U \sum_i n_{i, \uparrow} n_{i, \downarrow}-\sum_i \boldsymbol{\sigma}_i \cdot \mathbf{B}_i$ - so this doesn't quite proof that an efficient ground state preparation for the Fermi-Hubbard model without magnetic fields is impossible, if I am not mistaken. $\endgroup$
    – lm1909
    Feb 3 at 16:27
  • 1
    $\begingroup$ Yes, indeed the proof by Schuch and Verstraete does include the coupling of local magnetic fields to the spin degrees of freedom. Moreover, the proof involves going from the spin-1/2 Heisenberg model to the Fermi-Hubbard model, which is only strictly valid at half-filling in the limit $U/t \to \infty$, since charge fluctuations are frozen. I have looked for other papers discussing the complexity class of the Fermi-Hubbard model, but could not find any that were more relevant than this one. $\endgroup$
    – bm442
    Feb 4 at 10:48
  • 1
    $\begingroup$ Let me also note that, even if the Fermi-Hubbard model is in the QMA class, it does not mean it is impossible to achieve quantum advantage in the determination of its ground state properties relative to state-of-the-art numerical methods (e.g., PEPS-based Corner Transfer Matrix, Quantum Monte Carlo) implemented on conventional hardware for system sizes of the order of $30-50$ sites in two-dimensional lattices. It simply means that the resources required to scale up the simulations grow exponentially with the number of electrons. $\endgroup$
    – bm442
    Feb 4 at 10:55
  • 1
    $\begingroup$ Worth pointing out that the magnetic field loophole appears to be closed, see this (open-access) journals.aps.org/prxquantum/abstract/10.1103/… $\endgroup$
    – Dr. T. Q. Bit
    Jul 8 at 20:03
  • $\begingroup$ @Dr.T.Q.Bit thank you, this is indeed exactly what I was looking for! In case you prefer to turn this into an answer, I am very happy to mark it as accepted. $\endgroup$
    – lm1909
    Sep 26 at 15:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.