Generally speaking, "playing god" is talked about as messing with nature and the things around us to better suit our needs. Genetic engineering, climate engineering, etc. "God" refers to the natural order of things and trying to change it.
(Form time to time there are articles that try to explain why analog computers are better than binary computers. Usually they assume infinite precision, that is impossible in a real system.)
The article claims that the time is linear, but it use quadratic space. So if you campare thy to simulate the algorithm with a big system in a sequential computer you will get probably cubic run time.
A better way to understand this is that the amoeba uses a good heuristic to solve the TSP in a small case. There are many heuristics out there, so it would be nice to implement this heuristic and compare with all the other one is some kind of standardized example set. It's more easy to find a good solution in a small system.
(Under the hood, the amoeba is a quantum system. But if you consider this a quantum computer then your phone is also a quantum computer.)
The internal communication inside the cell is classical, not quantic (classic, like your phone). I guess it use some kind of internal hormone, but it may be some signal that propagates in the cell membrane. IANAB.
You can't have a good quantum correlation in something that is as big as a cell (unless you freeze it at ridiculous low temperature that are not posible for now and would kill the cell anyway, or you have a more ordered system like a extremely pure crystal, or you only want some correlation for ridiculous small amount of time).
You can have big entangled systems, but they look more like pair of very clear optic fiber, not like a cell with a lot of water and crap moving randomly inside.
There are also some interesting "big" quantum effects in molecules like chlorophyll. (I'm not sure if they are 100% confirmad yet.) But a molecule of chlorophyll is much much much smaller than the cell and the effect is very short lived.
There are good heuristic, specially if the distances are not chosen at random but are the distance between points in the plane. So it's posible in some cases to find quite good solutions.
The problem is NP-complete only is you ask for the best solution.