But nature can't solve NP-hard problems in general either, so predicting what actually happens when a protein folds is merely in BQP.

That explains why I've seen descriptions of folding prediction algorithms that run in polynomial time, on the order of n^5 or less with n = number of amino acids in primary chain.

I wanted to add that many proteins found in nature require chaperones to fold correctly. These can be any other molecules - usually proteins, RNA-zymes, or lipids - that influence the folding process to either assist or prevent certain configurations. They can even form temporary covalent bonds with the protein being folded. (Or permanent ones; some working proteins have attached sugars, metals, other proteins, etc.) And the protein making machinery in the ribosomes has a lot of complexity as well - amino acid chains don't just suddenly appear and start folding.

All this makes it much harder to predict the folding and action of a protein in a real cell environment. In vivo experiments can't be replaced by calculations without simulating a big chunk of the whole cell on a molecular level.