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.
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