Send living bacteria into a tiny maze and use the paths they take to solve a math problem. If the bacteria divide along the way, the number of individuals doing the computing grows, letting them explore more routes in parallel. An international team led by McGill University has developed a new biocomputer built on this property of living organisms.
The findings, from a team led by Professor Dan V. Nicolau of McGill University, were published on August 11, 2026, in the journal Microsystems & Nanoengineering. The researchers demonstrated a mechanism that exploits the way living bacteria swim through microchannels to solve the subset sum problem, which is classified as "NP-complete" in computational complexity theory. Its defining feature is that the bacteria multiply during the computation, allowing the system to increase the computing resources available for the search on its own.
In conventional parallel biocomputing, the number of molecules or microparticles loaded before the computation starts limits how many routes can be explored at once. This study showed that bacterial cell division could ease that constraint. However, the problem sizes confirmed in the experiments were limited, and the work has not shown performance that surpasses electronic computers.
How bacteria solve the subset sum problem by navigating a maze
The subset sum problem (SSP) that the team targeted asks whether some combination of numbers chosen from a given set of integers adds up to a specified target value. For example, if the set is {1, 3, 4} and the target is 5, the combination "1 + 4" is the answer.
If the number of elements is (N), there are (2^N) possible subsets in total. Because the number of combinations grows exponentially as elements are added, solving large problems by brute force requires an enormous amount of computation. The subset sum problem is known as one of the NP-complete problems, and no algorithm has been found that solves arbitrary inputs in polynomial time. That said, not every instance is hard, and some can be solved efficiently depending on the values and distribution of the integers.
The team translated this combinatorial search into a network of microchannels. The decision to include or exclude each integer is represented by a branch in the channels, and the computation is carried out by the routes the bacteria swim along. The bacteria themselves do not understand numbers or perform arithmetic. Moving through channels whose structure has been built in advance to encode the problem corresponds to the mathematical operations.
The network has multiple exits corresponding to the sums of the subsets. By observing which exit the bacteria reach, researchers can determine whether a combination yielding that sum exists. By tracing the paths the bacteria took, they can also find out which integers were selected to produce it.
Cell division expands computing resources
The team fabricated the channel chips using microfabrication techniques also used in semiconductor manufacturing. A silicon master was made with electron-beam lithography and reactive ion etching, and the channel pattern was then transferred to polydimethylsiloxane (PDMS). This was bonded to a transparent glass substrate or similar to form a sealed network inside which the bacteria can move. PDMS is permeable to oxygen, which also helps keep aerobic bacteria alive and motile.
The channels contain three main types of junctions.
- Split junction: Divides the channel in two directions, representing the choice of whether to include an integer in the subset.
- Pass junction: A structure that lets bacteria cross intersecting channels without changing direction.
- Join junction: A structure where bacteria arriving from different paths merge, used for example when multiple combinations reach the same sum.
At a Split junction, the search path branches depending on whether a bacterium turns left or right. However, bacterial movement varies, and a bacterium that should go straight through a Pass junction sometimes enters a different channel. If bacteria that did not follow the correct computational path reach an exit, they can produce incorrect results. The team calls this "ghost traffic" and added side channels and trap structures to remove bacteria that went down the wrong path.
The key feature of this approach is that bacteria can divide during the computation, increasing the number of individuals doing the search.
Previous biocomputing research has explored methods in which actin filaments, microtubules, and similar components are driven by molecular motors to explore channel networks. But these computing agents do not reproduce themselves, so the number needed for the search must be prepared in advance. The process of loading large numbers of agents one after another becomes a time constraint in large-scale computations.
Bacteria, by contrast, keep dividing as long as they have nutrients and a suitable environment. If the population doubles each generation, the number of search agents also grows exponentially. The team likens this property to a mechanism in which the number of CPUs increases during the computation.
The experiments used the relatively slow-dividing Escherichia coli strain HCB437 and the marine bacterium Vibrio natriegens, which grows extremely fast. The latter is said to be able to double in about 9 to 12 minutes even at room temperature, so its population can increase while it explores the microchannels. By comparing the movement characteristics and growth rates of the two, the team tested how cell division affects computation.
Growth effects and branching errors confirmed in experiments
The team measured how the bacteria move at junctions and evaluated the accuracy of the computation. All experiments were repeated at least three times.
E. coli HCB437 is a mutant strain with altered chemotaxis-related functions; it changes direction infrequently and swims relatively straight. V. natriegens, meanwhile, grows quickly but showed a bias in the direction it took at branch points.
The movement characteristics measured at each junction are as follows.
| Measurement | E. coli HCB437 | V. natriegens |
|---|---|---|
| Left-turn rate at Split junction | 50.1% | 61.1% |
| Right-turn rate at Split junction | 49.8% | 38.3% |
| Erroneous entry rate at Pass junction | 1.3% | 0.3% |
Source: Microsystems & Nanoengineering (2026). Values are measured results at microchannel junctions.
E. coli chose left and right branches almost equally, whereas V. natriegens chose the left direction more often. The paper links this bias to asymmetry in the cell structure, which has a single flagellum. On the other hand, V. natriegens had the lower erroneous entry rate at Pass junctions, at 0.3%. These results show that channel shapes need to be optimized to suit the species and motility characteristics of the bacteria.
For subset sum problems using prime numbers, the team solved problems with (N=7) elements and a total sum of up to 42 in experiments and confirmed that no notable operational problems arose. The number of subsets explored is (2^7=128), a very small problem for a modern electronic computer. The significance of this experiment lies not in computation speed but in confirming that a mathematical problem can be solved physically through the movement of bacteria.
In addition, when the network for a sum of 42 was observed for about 26 minutes, the fast-growing V. natriegens went through about two division cycles, and the number of search agents in the channels increased. The slower-growing E. coli, in contrast, showed no comparable amplification in the same observation time. This experimentally showed that bacterial self-replication can be used to expand computing resources.
Seven elements was not, however, the upper limit of all the experiments in the study. The team also tested a special subset sum problem in which every element is 1, confirming solution determination for up to 100 elements in a channel corresponding to Pascal's triangle. In operation tests of a large-scale channel, they confirmed bacterial movement across a range equivalent to 175 elements. In the 200-element network, some channels were not sufficiently wetted, a fabrication and experimental problem, so exit observation was limited to 175.
Still, problems in which all elements are 1 have a simple structure, and erroneous entry at Pass junctions is unlikely to be an issue. The operation checks in these large channels need to be distinguished from the ability to accurately solve complex subset sum problems that combine different integers.
Simulations predict potential for scaling up, but comparisons with electronic computers come with conditions
Using the bacterial movement speed, division time, directional bias, junction error rates, and other values obtained in the experiments, the team estimated performance at larger scales through Monte Carlo simulations.
An important constraint that emerged was erroneous entry at Pass junctions. As the problem size grows, the number of junctions in the channels increases, and so does the number of bacteria that follow wrong paths. As a result, the signal from bacteria that reached the correct exit could be buried in noise from erroneous entries.
In the simulations, with a Pass junction error rate of 1%, the problem size at which the correct solution could be statistically identified was estimated at about 10 to 15 elements. Stably solving problems of 30 or more elements would require reducing the error rate below 0.01%. That is far lower than current measured values and would be difficult to achieve without improving channel design and control of bacterial motion. The team proposes measures such as adopting three-dimensional crossing structures to prevent erroneous entry.
The team also evaluated computation-time scaling in simulations based on measured values. For subset sum problems using prime numbers, the relationship between problem size and computation time fit a power law well, with a coefficient of determination in the regression analysis of (R^2>0.99). This suggests that under certain conditions the increase in computation time may be approximated by a polynomial relationship. However, for hard subset sum problems in which the integer values grow exponentially, the channels themselves become exponentially longer, so the time the bacteria need to travel also increases exponentially.
The team also made theoretical comparisons with conventional electronic computers. Using the Intel Pentium Pro and the AMD Ryzen Threadripper 3990X as benchmarks, they estimate that under conditions of high bacterial speed and growth rate, computation times could be on par at roughly 28 and 38 elements, respectively. However, the bacterial volume required under these conditions reaches about 1 liter for the former and about 1 cubic meter for the latter.
Furthermore, these comparisons rely on idealized simulations that treat bacterial volume as zero and on brute-force computation on the electronic computer side. Real bacteria have size, and crowding will occur if they keep multiplying in the channels. Efficient algorithms specialized for the subset sum problem also exist for electronic computers, so it cannot be concluded from these results that the approach has an advantage in general computing performance.
The same applies to energy efficiency. The paper estimates the energy for a bacterium to move 10 µm and perform one logical operation at about (2\times10^{-18}) J. The energy per operation for the CPUs used as comparisons, meanwhile, is given as about (3.9\times10^{-12}) to (1.4\times10^{-11}) J.
However, the bacterial figure mainly covers the energy needed for movement and does not include the cell's overall metabolic activity. The paper itself explains that the energy E. coli uses for motility is only about 2% of its total energy consumption. A real device would also need energy for culturing the bacteria, temperature control, microscope observation, and image analysis, so it has not been demonstrated that the system as a whole uses less power than an electronic computer.
The results can be summarized by dividing them into experiments, simulations, and theoretical comparisons, as follows.
| Evaluation stage | Main results | Limitations / untested issues |
|---|---|---|
| Experimental subset sum computation | Verified up to 7 elements and a total sum of 42 in the prime-number series | Scaling up to complex problems |
| Measurement of bacterial movement and growth | Pass junction error rate of 0.3–1.3%; confirmed about two generations of growth opportunity for V. natriegens in about 26 minutes | Stability over long operation |
| Operation tests on a special subset sum problem | Determined solutions up to 100 elements for the all-ones problem; channel operation confirmed up to the equivalent of 175 | Application to general subset sum problems |
| Monte Carlo simulation | Estimated about 10–15 elements at a 1% error rate; error rate below 0.01% needed for 30 or more elements | Whether such low error rates can be achieved in real devices |
| Theoretical comparison with electronic computers | Suggested computation times could cross over under certain conditions | Required bacterial quantity, device volume, actual power consumption |
| Future applications | Potential applications in cryptanalysis, molecular biology, and more | Concrete demonstration and practical advantages |
Ever-multiplying bacteria and limited channel space: physical constraints on practical use
The bacteria's ability to multiply is the greatest advantage of this biocomputer, but it is also a constraint on scaling up.
The most important issue is congestion in the channels. If the bacteria keep dividing, their numbers rise over time, and density becomes especially high where multiple paths merge and near the exits. If collisions between bacteria or hydrodynamic interference impede movement, the advantage of parallel search could be lost. If the channels become clogged, the bacteria end up moving in single file, which increases computation time.
In long computations, nutrient depletion, buildup of metabolic waste, and bacterial adhesion to channel walls also become problems. The team cites remedies such as placing a porous membrane above the channels to supply nutrients. Earlier studies have also confirmed that making the PDMS surface hydrophilic can suppress bacterial adhesion. Whether such measures work well enough in large-scale computing networks will need to be verified in future work.
In this study's tests of the large channel based on Pascal's triangle, no serious congestion was observed up to the range equivalent to 175 elements. But this does not guarantee that growth-induced congestion will not occur. Theoretical analysis also suggests that, depending on the type of problem and the channel density, congestion could begin to affect computation time from around 15 to 30 elements.
The team proposes making parts of the channels deeper to secure space for the multiplied bacteria, and converting the planar channels into three-dimensional structures. They also have an idea for dynamically switching the structure of branch points so that the problem being computed can be changed. The possibility of genetically engineering the bacteria so that the cells themselves record which paths they passed through, improving the readout of results, is also being considered.
Could biocomputers replace electronic computers?
The team lists cryptanalysis, molecular biology, and artificial intelligence as possible future application areas. They also mention applications to problems involving protein three-dimensional structure, but the experiments did not solve such problems. What has been shown so far is the basic principle: a mathematical combinatorial search can be mapped onto microchannels and computed using the movement and growth of living bacteria.
Conventional electronic computers have overwhelming advantages in processing speed, accuracy, programming flexibility, and device miniaturization. This approach is not meant to directly replace them; it is better seen as research exploring the potential of a complementary computing technology that uses biological parallelism for specific combinatorial problems.
What matters most in this study is not just that bacteria perform computation, but that it was experimentally confirmed that they can multiply during the computation and expand their own search capacity. The idea of increasing computing resources through the organisms' own growth, rather than adding them from outside, is fundamentally different from conventional electronic computers.
Whether this mechanism becomes a practical computing technology, however, depends on how far erroneous entry at junctions can be suppressed, whether multiplied bacteria will clog the channels, and how far the scale and energy consumption of the whole device can be reduced. The focus of future research will be whether the advantage of bacterial self-replication can be translated into computing performance without being hindered by physical constraints.