Many of the early computer science approaches to protein folding were laughably naive, and the assumption about folding described in the Fraenkel paper: "It is believed that the native folded three-dimensional conformation of a protein is its lowest free energy state, or one of its lowest. "

is not factually correct. In reality, proteins never reach their lowest energy state unless they are very simple proteins, instead, they rapidly reach a state of kinetic interconversion between several accessible states. We can simulate proteins and measure those state transitions.

Really, solving protein folding is about classical approximations and clever sampling.

> The paper says a protein with 100 amino acids may assume 8^100 conformations and nature solves for that in 1 second

There are some problems with this - firstly that paper is quite old. Not sure what the current state of the art is but this might be helpful : http://folding.stanford.edu/dig-deeper

Secondly, the idea that the protein might adopt any of 8^100 (or some large number) of combinations is not quite right. Consider a very simple model of just a chain of nodes connected together on a 2D grid. There are certainly a large number of possible ways to arrange this chain on the grid, but if you start off in one particular arrangement (call it 'unfolded') and then move towards a more compact one ('folded') then you will follow some particular path of arrangements.

However, there are ideas around 'quantum biology' from Johnjoe Mcfadden (http://www.johnjoemcfadden.com/) that might be interesting.

My job is pretty awesome. But I had to get a PhD first, something that in my experience is risky for students' mental health. I don't recommend it to people unless they show a high tolerance for repeated failure (aka "research").

As for your question: NP-hardness refers to the worst-case performance, not the average case. Many individual instances of NP-hard problems are solvable. Stochastic algorithms do quite well, and protein folding in nature is a kind of stochastic algorithm (classically we would call it simulated annealing, although really it is quantum annealing). So as far as we know, there's nothing nature is doing to solve NP-hard problems faster than known algorithms. But it does do quantum annealing very fast, something we would really like to exploit using quantum computers.

For more like this - the intersection between computability and nature - I HIGHLY recommend Scott Aaronson's "Quantum Computing Since Democritus".

> Can we chain these natural occurances in order to calculate a function with inputs in record time?

That's essentially what a quantum computer does.

But, a quantum computer would not in general solve NP-hard problems in polynomial time (as far as we know). The known exponential speedups are for "easier" problems like factoring and finding quantum ground states, which are not NP-hard.