4 ms·

Dude, your job looks awesome. I have been thinking a lot about the ramifications of chemestry computation since last year. This comment https://news.ycombinato

Dude, your job looks awesome. I have been thinking a lot about the ramifications of chemestry computation since last year. This comment https://news.ycombinator.com/item?id=16027737 https://news.ycombinator.com/item?id=16027737 about how to get around NP-hardness made me go "Oh, can you even ask such a question? Can you expect to solve getting around this kind of problem?" and so I went researching. I found the paper Complexity of Protein Folding https://www.gwern.net/docs/biology/1993-fraenkel.pdf https://www.gwern.net/docs/biology/1993-fraenkel.pdf and chapter 4 exposes two possible realities: either nature solves NP-hard problems in polynomial time or it functions in a classic Turing machine model. I was like "Welp I guess when you put it like this, talking about nature working within a machine model I suppose it sounds rather silly, yes. It may be that nature just does her thing in her own way somehow." The paper says a protein with 100 amino acids may assume 8^100 conformations and nature solves for that in 1 second. Also the spin glass https://en.wikipedia.org/wiki/Spin_glass https://en.wikipedia.org/wiki/Spin_glass model is apparently some other thing that nature solver eerly fast. Can we chain these natural occurances in order to calculate a function with inputs in record time?

gilleain 9y ago
> 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 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/ http://www.johnjoemcfadden.com/) that might be interesting.
dekhn 9y ago
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.
Robotbeat 9y ago
> 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.
- comicjk 9y ago
  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.
comicjk 9y ago
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".

gilleain 9y ago

> 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 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/ http://www.johnjoemcfadden.com/) that might be interesting.

dekhn 9y ago

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.

Robotbeat 9y ago

> 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.

comicjk 9y ago
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.

comicjk 9y ago

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".