News for hackers. Stuff that matters.
Re:Quantum Advantage for NP Approximation by evanb on Thursday October 10, 2024 @12:41AM (#41795572)
Computational physicists have been thinking about algorithms for simulating quantum systems essentially since computers were invented. We have decent algorithms for approximating ground states, or for systems in equilibrium (contingent on it being spin-balanced, or at half-filling, or at 0 density, ... depending on the model), or in other limited circumstances.

But lift any of those special restrictions, and simulation methods hit a sign problem [sign]. In particular, real-time evolution of quantum systems, which is what a quantum computer does by its very nature, poses in some sense the most difficult sign problem for approaches leveraging classical computing.

That's not a proof that classical algorithms can't become more capable, but it's almost certainly a question that must be answered system-by-system. The generic sign problem is NP-hard, so special-case reasoning is required.

[sign]: https://en.wikipedia.org/wiki/Numerical_sign_problem

Re:Quantum Advantage for NP Approximation by whatshisface on Thursday October 10, 2024 @09:10AM (#41798440)
That's for the strong force. The challenge with quantum chemistry is the 2^N state space for N particles.
Re:Quantum Advantage for NP Approximation by evanb on Thursday October 10, 2024 @11:35AM (#41799957)
The reason those lattice field theory computations are done that way is that they provide stochastic but polynomial-time algorithms for exactly the same kind of exponentially-large state space that appears in quantum chemistry.