Polynomial-cost real-time simulation of interacting fermion lattices · revision history

Revision 2

Accepted · core change · record

Changes against revision 1:

Title
Polynomial-cost real-time simulation of interacting fermion lattices
Plain
Simulating how electrons evolve in time requires summing complex phases that cancel more and more as time grows, so the cost rises exponentially with simulated time. For a single magnetic impurity, new methods reduced this to polynomial cost; whether this is possible for whole lattices is open.
Precise · changed · core
Revision 1: Real-time diagrammatic and path-integral Monte Carlo for nonequilibrium Green's functions have variance growing as $\operatorname{exp}(c t)$. Inchworm Monte Carlo (Cohen et al. 2015) and related methods reach polynomial scaling in t for Anderson impurity models. Determine whether a classical algorithm computes local real-time correlators of the infinite 2D Hubbard model at $U/t \sim 4$, starting from a thermal state at $T \sim t$, up to time $t_{\mathrm{max}}$ with error eps at cost polynomial in t_max and 1/eps, or prove that this is hard (e.g. by a complexity reduction). An answer is an algorithm with proven scaling or a hardness proof.
Revision 2: Real-time diagrammatic and path-integral Monte Carlo for nonequilibrium Green's functions have variance growing as $\exp(c t)$. Inchworm Monte Carlo (Cohen et al. 2015) and related methods reach polynomial scaling in t for Anderson impurity models. Determine whether a classical algorithm computes local real-time correlators of the infinite 2D Hubbard model at $U/t \sim 4$, starting from a thermal state at $T \sim t$, up to time $t_{\max}$ with error $\epsilon$ at cost polynomial in $t_{\mathrm{max}}$ and $1/\epsilon$, or prove that this is hard (e.g. by a complexity reduction). An answer is an algorithm with proven scaling or a hardness proof.
Settled by
An algorithm with a proven polynomial cost bound verified against exact results, or a complexity-theoretic reduction showing such an algorithm would imply an unlikely collapse.
Kind
well-posed
Answer type
yes-no
References
(empty)
Literature status
partially-resolved
Status note
Polynomial-cost methods exist for quantum impurity models since 2015; no such method is known for lattices.
Posed since
(empty)

Decisions