Cyan comments on Information theory and FOOM - Less Wrong

6 Post author: PhilGoetz 14 October 2009 04:52PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (93)

You are viewing a single comment's thread. Show more comments above.

Comment author: pengvado 15 October 2009 09:52:17AM *  3 points [-]

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.

Comment author: Cyan 15 October 2009 03:07:56PM 1 point [-]

This is a nice insight.