Re:Gamers solve molecular puzzle
by jbri on Sunday September 18, 2011 @11:02PM
(#3012034)
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.
Re:Gamers solve molecular puzzle
by sid0 on Monday September 19, 2011 @12:11AM
(#3012202)
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.
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.