[ndl]

Having worked worked in both quantum information and biology, I have a few things to say about this article...

1) The 1st paragraph really annoys me. Quantum computers don't solve NP Complete problems by trying every solution. This is a common misconception. In fact, it's widely believed that quantum computers wouldn't solve NP-Complete problems in polynomial time, though they may get a moderate speedup over classical computers related to their superior searching capability.

2) The biological computer in the article also doesn't solve NP problems in polynomial time. Rather, it proposes a highly parallel machine that divides runtime by a very large constant. The real claim is to make a low-energy parallel processor that makes it easier to throw lots of processors at the problem. It does not alter the complexity classes. The linked PNAS article states, "it is inherent to combinatorial and NP-complete problems (assuming P != NP) that the exploration of the entire solution space requires the use of exponentially increasing amounts of some resource, such as time, space, or material. In the present case this fundamental requirement manifests itself in the number of agents needed, which grows exponentially with 2^N. Effectively we are trading the need of time for the need of molecular mass." Unfortunately, the experiment hasn't quite got this far, since "the error rates of this first device are too large for scaling up to problems containing more than ∼ 10 variables." It may constitute a step in the right direction, though.

3) The popular science article (as opposed to the original research it links to) is probably too focused on trying to make this about P vs. NP and misses the actual accomplishment: that the researchers can control a microbiological system outside of their own brains well enough to compute with it. This is pretty cool and may be valuable progress in nano/biotech even if it doesn't end up being a viable computer.

[p4wnc6]

In grad school I always heard Scott Aaronson harp on these issues too. He was fond of saying that quantum algorithms organize things so that amplitude here and amplitude there is arranged just so, to ensure that wrong answers experience cancelling amplitudes, rendering them highly unlikely to be the observed outcomes.

It's not about "trying everything in parallel" but rather shoving amplitude around to ensure that correct answers are overwhelmingly more likely to be observed.

[rayuela]

This is spot on and what they actually managed to build is actually super interesting.