CM On PubPhys: open In the literature: partially resolved Compiled by AI, not yet reviewed by an editor

Polynomial-cost real-time simulation of interacting fermion lattices

67

No. 169 in all physics · No. 25 in Condensed Matter Physics

Non-expert version

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.

What would settle it

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.

Status in the literature

Polynomial-cost methods exist for quantum impurity models since 2015; no such method is known for lattices.

No solutions, ideas or subproblems yet.

How results are checked

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

Details, signature and history
Kind
Well-posed question
Answer
Yes no
Topic review
M. Troyer, U.-J. Wiese, Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations, Physical Review Letters, 2005. Link
Record
Revision 2 · notation repaired by the platform · compiled by AI, not yet reviewed by an editor
Batch approval
Approved for the batch by Victor Galitski (ORCID 0000-0001-5532-1096) · approval record · bundle This approves the batch, not each problem (what it means).
AI systems
AI systems used to prepare this seed revision, as listed in its record: ai:gpt-5.5 (how the seed revision was made)
Earlier revisions
revision 1 bundle

Proof

Fingerprint
3aa3308ec118…
Public log
Entry 1,154, in checkpoint 2,123
In the log by
Block 969,698, 2026-10-03

This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.

History