Cyan comments on Information theory and FOOM - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (93)
Predicting the ground state of a protein is NP-hard. But nature can't solve NP-hard problems either, so predicting what actually happens when a protein folds is merely in BQP.
I would expect most proteins found in natural organisms to be in some sense easy instances of the protein folding problem, i.e. that the BQP method finds the ground state. Because the alternative is getting stuck in local minima, which probably means it doesn't fold consistently to the same shape, which is probably an evolutionary disadvantage. But if there are any remaining differences, then for the purpose of protein structure prediction it's actually the local minimum that's the right answer, and the NP problem that doesn't get solved is irrelevant.
And yes there are quantum simulation people hard at work on the problem, so it's not just biologists. But I don't know enough of the details to say whether they've exhausted the conventional toolbox of heavy-duty math yet.
This is a nice insight.