“Maybe you mean subexponential time? Which is not much of an improvement. This is a question which I would like someone like Scott Aaronson to answer. The sign problem is NP-hard[1]. So it's not currently believed that quantum computers can actually help with the sign problem [2]. On the other hand, we have papers that seem to say they could [3]. "today i…”
Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the "negative sign problem'' when applied to fermions - causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show, that such a solution is almost certainly unattainable by proving that the sign problem is NP-hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP (nondeterministic polynomial) in polynomial time.
候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“Thanks for mentioning the term that I was able to find: https://en.wikipedia.org/wiki/Numerical_sign_problem https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.94.170201 "Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations, Matthias Troyer and Uwe-Jens Wiese, Phys. Rev. Lett. 94, 170201, 4 May 2005" …”