4 ms·
Computational chemistry involves solving multiple NP-hard problems. There is an increasing reliance on computational models and simulation, but chemists realize
by quanticle 7y ago
Computational chemistry involves solving multiple NP-hard problems. There is an increasing reliance on computational models and simulation, but chemists realize that the models are approximations (since it's computationally infeasible to have perfect fidelity simulations). The only surefire way to observe a compound's properties is to synthesize it and measure.
- OscarCunningham 7y agoSurely there can't be any problems in computational chemistry that have actually been proven to be NP-hard? Simulating an experiment atom-for-atom is in BQP, which is not known to contain NP (and is suspected not to contain NP). EDIT: To put it another way, we can't solve NP problems by doing chemistry experiments.
- 0xffff2 7y agoSurely you would need to be modelling at a subatomic level to accurately simulate chemical interactions?
- OscarCunningham 7y agoSure. It's not an essential distinction though, because subatomic physics is also simulable in BQP.
- selimthegrim 7y agoN-representability?
- the8472 7y agoLayman understanding ahead, see scott aaronson's NP-complete Problems and Physical Reality[0] if you want more rigorous arguments. BQP gets you collapsing measurements. The Schrödinger equation (NP-hard) gives you all probabilities at once, solving it is equivalent to performing non-collapsing measurements. [0] https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf
- jhrmnn 7y agoHere’s one example. Though it’s probably different from what you had in mind https://arxiv.org/abs/cond-mat/0408370 https://arxiv.org/abs/cond-mat/0408370