Advanced

Parallel computation with molecular-motor-propelled agents in nanofabricated networks.

Nicolau, Dan V; Lard, Mercy LU ; Korten, Till; van Delft, Falco C M J M; Persson, Malin; Bengtsson, Elina; Månsson, Alf; Diez, Stefan; Linke, Heiner LU and Nicolau, Dan V (2016) In Proceedings of the National Academy of Sciences 113(10). p.2591-2596
Abstract
The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is... (More)
The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Proceedings of the National Academy of Sciences
volume
113
issue
10
pages
2591 - 2596
publisher
National Acad Sciences
external identifiers
  • pmid:26903637
  • scopus:84960532489
  • wos:000372013300025
ISSN
1091-6490
DOI
10.1073/pnas.1510825113
language
English
LU publication?
yes
id
8db589fe-4bdc-4a32-905c-91b93a7423f9 (old id 8821971)
date added to LUP
2016-03-04 09:39:50
date last changed
2017-10-01 03:09:12
@article{8db589fe-4bdc-4a32-905c-91b93a7423f9,
  abstract     = {The combinatorial nature of many important mathematical problems, including nondeterministic-polynomial-time (NP)-complete problems, places a severe limitation on the problem size that can be solved with conventional, sequentially operating electronic computers. There have been significant efforts in conceiving parallel-computation approaches in the past, for example: DNA computation, quantum computation, and microfluidics-based computation. However, these approaches have not proven, so far, to be scalable and practical from a fabrication and operational perspective. Here, we report the foundations of an alternative parallel-computation system in which a given combinatorial problem is encoded into a graphical, modular network that is embedded in a nanofabricated planar device. Exploring the network in a parallel fashion using a large number of independent, molecular-motor-propelled agents then solves the mathematical problem. This approach uses orders of magnitude less energy than conventional computers, thus addressing issues related to power consumption and heat dissipation. We provide a proof-of-concept demonstration of such a device by solving, in a parallel fashion, the small instance {2, 5, 9} of the subset sum problem, which is a benchmark NP-complete problem. Finally, we discuss the technical advances necessary to make our system scalable with presently available technology.},
  author       = {Nicolau, Dan V and Lard, Mercy and Korten, Till and van Delft, Falco C M J M and Persson, Malin and Bengtsson, Elina and Månsson, Alf and Diez, Stefan and Linke, Heiner and Nicolau, Dan V},
  issn         = {1091-6490},
  language     = {eng},
  month        = {02},
  number       = {10},
  pages        = {2591--2596},
  publisher    = {National Acad Sciences},
  series       = {Proceedings of the National Academy of Sciences},
  title        = {Parallel computation with molecular-motor-propelled agents in nanofabricated networks.},
  url          = {http://dx.doi.org/10.1073/pnas.1510825113},
  volume       = {113},
  year         = {2016},
}