Why do you think nature can't solve NP-hard problems? When you dip a twisted wire with 3D structure into a dish of liquid soap and water, and pull it out and get a soap film, didn't it just solve an NP problem?

All of the bonds and atoms in a protein are "computing" simultaneously, so the fact that the problem is NP in terms of number of molecules isn't a problem. I don't understand BQP & so can't comment on that.

Incidentally, your observation about consistent folding is often right, but some proteins have functions that depending on them folding to different shapes under different conditions. Usually these shapes are similar. I don't know if any proteins routinely fold into 2 very-different shapes.