New parallel computer proves capable of solving combinatorial problems

A global collective of researchers has published a paper detailing a new parallel-computing approach that is able to solve combinatorial problems. 

The report indicates the solution is scalable, error-tolerant, energy-efficient, and can work with current technologies.

Despite advancements made to electronic computers over the decades they’ve been in existence, the technology is limited due to its sequential nature; that is, electronic computers are only able to process one computational task at a time. This restriction, if you will, prevents the computer from solving combinatorial-esque problems — things like protein design and folding, optimal network routing, and more. In these instances, there are a higher number of calculations because they grow exponentially with the size of the problem. 

In theory, parallel computing is able to address these problems, but anything that’s been developed thus far has suffered from drawbacks that adversely affected the computer’s ability to address up-scaling and practical implementation. 

The solution, which it’s worth noting was put together by researchers from the Technische Universität Dresden and the Max Planck Institute of Molecular Cell Biology and Genetics, Dresden in collaboration with international partners from Canada, England, Sweden, the US, and the Netherlands, combines well-established nanofabrication technology with molecular motors that are not only efficient, but work in parallel. 

Diving into the specifics, the team used a benchmark combinatorial problem that is known to be too difficult to solve for a sequential computer. The problem to be solved was “encoded” into a network of nanoscale channels. On the one hand, was completed mathematically by designing a geometrical network capable of representing the problem; on the other hand, it was done by fabricating the physical network based on the aforementioned design via lithography (the standard chip-manufacturing technique).

The networks were then explored in parallel by a group of protein filaments (specifically, actin filaments) that were self-propelled by a molecular layer of motor proteins (myosin or kinesin) covering the bottom of the channels. By using different types of junctions in the design of the network, the filaments were automatically guided to the correct solutions to the problem; that is, the filaments were forced to behave in only one of two ways by these different junction types. Worth mentioning: the filaments are pretty rigid in structure, so turning left or right was only possible for certain angles of the crossing channel. By clearly defining the options (split junctions and pass junctions), the team was able to create an “intelligent” network that gave the filaments the opportunity to either cross straight or decide between two channels with a 50/50 probability. 

Tests indicate the time to solve combinatorial problems of this size using the parallel computing method described here is improved upon in vast order. More importantly, the approach is scalable with existing technologies and uses orders of magnitude less energy than conventional computers; this, in turn, circumvents heating issues that are also limiting many of today’s computers.

Learn more by downloading the team’s paper, Parallel computation with molecular-motor-propelled agents in nanofabricated networks, which was published in Proceedings of the National Academy of Sciences . 

Via Dresden University of Technology