3 ms·
Surely 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, wh
by OscarCunningham 7y ago
Surely 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