title: Parallel computation with molecular-motor-propelled agents in nanofabricated networks.
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.
authors.affiliation: Department of Integrative Biology, University of California, Berkeley, CA 94720-3140; Molecular Sense, Ltd., Wallasey CH44 1AJ, United Kingdom;
authors.forename: Dan V
authors.initials: DV
authors.lastname: Nicolau
authors.affiliation: NanoLund and Solid State Physics, Lund University, S-22100 Lund, Sweden;
authors.forename: Mercy
authors.initials: M
authors.lastname: Lard
authors.affiliation: Center for Molecular Bioengineering (B CUBE) and Center for Advancing Electronics Dresden (cfaed), Technische Universität Dresden, 01069 Dresden, Germany; Max Planck Institute of Molecular Cell Biology and Genetics, 01307 Dresden, Germany;
authors.forename: Till
authors.initials: T
authors.lastname: Korten
authors.affiliation: Philips Research (MiPlaza) and Philips Innovation Services, 5656 AE, Eindhoven, The Netherlands;
authors.forename: Falco C M J M
authors.initials: FC
authors.lastname: van Delft
authors.affiliation: Department of Chemistry and Biomedical Sciences, Linnaeus University, SE-39182 Kalmar, Sweden;
authors.forename: Malin
authors.initials: M
authors.lastname: Persson
authors.affiliation: Department of Chemistry and Biomedical Sciences, Linnaeus University, SE-39182 Kalmar, Sweden;
authors.forename: Elina
authors.initials: E
authors.lastname: Bengtsson
authors.affiliation: Department of Chemistry and Biomedical Sciences, Linnaeus University, SE-39182 Kalmar, Sweden;
authors.forename: Alf
authors.initials: A
authors.lastname: Månsson
authors.affiliation: Center for Molecular Bioengineering (B CUBE) and Center for Advancing Electronics Dresden (cfaed), Technische Universität Dresden, 01069 Dresden, Germany; Max Planck Institute of Molecular Cell Biology and Genetics, 01307 Dresden, Germany;
authors.forename: Stefan
authors.initials: S
authors.lastname: Diez
authors.affiliation: NanoLund and Solid State Physics, Lund University, S-22100 Lund, Sweden; heiner.linke@ftf.lth.se dan.nicolau@mcgill.ca.
authors.forename: Heiner
authors.initials: H
authors.lastname: Linke
authors.affiliation: Department of Electrical Engineering & Electronics, University of Liverpool, Liverpool L69 3GJ, United Kingdom; Department of Bioengineering, McGill University, Montreal, QC, Canada H3A 0C3 heiner.linke@ftf.lth.se dan.nicolau@mcgill.ca.
authors.forename: Dan V
authors.initials: DV
authors.lastname: Nicolau
keywords: NP complete; biocomputation; molecular motors; nanotechnology; parallel computing