[shiven]

Quite right! However, all we have are (imperfect?) versions of a Turing machine to solve the folding problem!

Maybe a Lisp machine would do better ;-)

At the end of the day, a linear sequence of amino acids has to end up in a three-dimensional conformation with short-range contacts being formed between atoms far away in the primary (linear) sequence. Add to this the complexity from long-range effects critical for the final structural stability and biological/biochemical function.

And don't even get me started on Intrinsically Disordered Proteins -- where, frankly, the future of the entire field lies !!!

[jbri]

Assuming this is an NP problem, then a nondeterministic turing machine is capable of solving it in polynomial time (by definition).

So it stands to reason that a properly-constructed quantum computer (being an approximation of a nondeterministic turing machine) would probably be able to solve the protein folding problem in polynomial time.

It's also not out of the bounds of possibility for similar quantum effects to explain how proteins fold the same way every time - an individual protein in fact being a superposition of all possible foldings, and the lowest-energy folding being the one that is actually observed whenever it interacts with anything.

[sid0]

There is no known way of getting a quantum computer to solve an NP-complete problem in polynomial time. Integer factoring is in NP but not complete for it.