Международная группа исследователей создала бактериальный компьютер, который решает математические задачи с помощью живых микроорганизмов. Бактерии перемещаются по микроскопическим каналам, проверяют разные варианты ответа и размножаются прямо во время вычислений, увеличивая число работающих «процессоров».
Разработку возглавили специалисты канадского Университета Макгилла при участии коллег из Европы, Великобритании и Австралии. Главная особенность экспериментальной системы заключается в способности самостоятельно наращивать вычислительные ресурсы. Обычному компьютеру для увеличения числа параллельных вычислений требуется дополнительное оборудование, а бактериальной системе достаточно подходящих условий для деления клеток.
Для проверки идеи учёные выбрали задачу о сумме подмножества, известную как Subset Sum Problem. Нужно определить, можно ли выбрать из заданного набора чисел несколько значений так, чтобы получить определённую сумму. Например, из чисел 1, 3 и 4 получить четвёрку можно двумя способами. Взять число 4 либо сложить 1 и 3. Для небольшого набора ответ очевиден, но с добавлением новых чисел количество возможных комбинаций растёт экспоненциально.
При десяти числах существует 1024 возможных подмножества, при двадцати уже 1 048 576, а при тридцати больше миллиарда. Задача относится к классу NP-полных, объединяющему вычислительные проблемы, для которых не известны алгоритмы, способные эффективно решать все возможные случаи. Подобные математические конструкции встречаются в задачах оптимизации, планирования, проектирования электронных схем и криптографии.
Вместо перебора комбинаций программным алгоритмом исследователи превратили математическую задачу в физический лабиринт. Разветвления микроканалов соответствуют решениям включить очередное число в сумму или пропустить его. На одних перекрёстках бактерии выбирают направление, на других проходят без поворота, а отдельные участки объединяют несколько маршрутов. Каждый выход из сети обозначает определённый результат сложения.
Бактериям не требуется знать математику или выполнять арифметические операции внутри клетки. Вычисление заложено в геометрии каналов. Проходя развилки, микроорганизмы физически воспроизводят последовательность математических решений. Когда множество бактерий достигает разных выходов, исследователи определяют, какие суммы вообще можно получить. По траекториям движения также удаётся восстановить комбинации чисел, приведшие к ответу.
Для экспериментов использовали два вида микроорганизмов. Первым стала кишечная палочка Escherichia coli HCB437 с изменённым механизмом реакции на химические сигналы, благодаря которому бактерии движутся более прямолинейно. Вторым оказался Vibrio natriegens, известный необычайно быстрым размножением. При комнатной температуре популяция V. natriegens в подходящих условиях способна удваиваться каждые 9–12 минут.
Быстрое деление оказалось ключевым преимуществом. Пока микроорганизмы исследуют сеть, часть клеток размножается и создаёт новых участников вычислительного процесса. В одном из экспериментов наблюдение продолжалось около 26 минут, что давало V. natriegens время примерно для двух циклов удвоения. Исследователи непосредственно зафиксировали деление внутри каналов и подтвердили, что на выходах может оказаться больше бактерий, чем первоначально вошло в систему.
Сам вычислитель изготовили из прозрачного полимерного материала, закреплённого на стеклянной подложке. Ширина и глубина каналов превышали один микрометр, чтобы бактерии могли двигаться, не теряя заданного направления. Полимер пропускает кислород и помогает поддерживать жизнеспособность микроорганизмов. Геометрию перекрёстков формировали с высокой точностью, поскольку неправильный поворот бактерии означает ошибку вычисления.
В лаборатории проверили сети разной сложности. Например, конструкция для задачи с пятью числами содержала 903 узла. Учёные также продемонстрировали решение задач с семью числами и максимальной суммой 42. Результаты получали двумя способами. Подсчитывали бактерии на выходах либо строили карты движения по видеозаписям с микроскопа. Каждый вариант задачи проверяли как минимум в трёх повторных экспериментах.
Более крупные конструкции испытывали на специальном варианте задачи, связанном с треугольником Паскаля. В одной из сетей использовали 100 одинаковых чисел, что формально соответствует 2 в сотой степени возможных подмножеств. Однако такое испытание нельзя приравнивать к решению произвольной задачи со столь огромным числом комбинаций. При сложении ста единиц существует всего 101 различная сумма, поэтому эксперимент прежде всего проверял способность бактерий проходить большую сеть.
Исследователи изготовили и конструкцию для 200 элементов, но надёжно проследить движение удалось лишь до выхода с номером 175. Причиной стал производственный дефект, из-за которого жидкость не заполнила часть каналов. Результат показывает, что масштабирование зависит не только от поведения микроорганизмов, но и от качества изготовления микроскопической вычислительной схемы.
Ошибки движения также остаются серьёзной проблемой. Бактерии иногда выбирают неправильный маршрут, разворачиваются или задерживаются у стенок. Авторы предусмотрели специальные отводящие каналы и ловушки для части ошибочных траекторий. По экспериментальным данным, частота ошибок на перекрёстках с прямым проходом составляла около 1%. Для значительно более сложных задач потребуются существенно более точные конструкции.
Наиболее впечатляющие прогнозы исследователи получили при математическом моделировании. Используя измеренные скорости движения, частоту деления и вероятность ошибок, группа рассчитала, при каких масштабах бактериальная система теоретически сможет конкурировать с электронными процессорами. Для одного из сценариев модель предсказывает сопоставимое время решения задачи с AMD Ryzen Threadripper 3990X при наборе примерно из 38 чисел.
Однако такой результат пока существует только в расчётах. Более того, предполагаемому биокомпьютеру для достижения сопоставимой производительности потребовался бы примерно кубометр бактериальной массы. Сравнение проводили с электронными вычислениями методом полного перебора, а не со всеми существующими оптимизированными алгоритмами. Поэтому говорить о доказанном превосходстве живого компьютера над современными процессорами преждевременно.
Авторы также признают фундаментальное ограничение собственной архитектуры. Чем больше бактерий размножается внутри каналов, тем выше вероятность заторов. Клеткам нужны питательные вещества, пространство и подходящая температура, а результаты необходимо постоянно считывать оптическими датчиками. Для некоторых особенно сложных наборов чисел размеры самой сети растут настолько быстро, что увеличение бактериальной популяции уже не обеспечивает вычислительного преимущества.
Потенциальную пользу исследователи связывают со специальными задачами оптимизации, криптографии и молекулярной биологии. Руководитель работы Дэн Николау рассматривает бактериальные системы как дополнение к обычным и квантовым компьютерам, а не как их универсальную замену. При этом применение в криптографии пока остаётся перспективой. Эксперимент не показывает практической возможности взламывать современные алгоритмы шифрования.
Разработка продолжает исследования биологических вычислений, но использует принципиально другой подход, чем генетические логические элементы. Ранее учёные уже создавали живые транзисторы и собирали вычислительные схемы из бактериальных колоний, обменивающихся химическими сигналами. В новой системе логические операции задаёт геометрия лабиринта, а бактерии выступают подвижными вычислительными агентами.
Работа стала результатом примерно двадцатилетнего сотрудничества исследовательских групп и впервые вышла 11 августа в рецензируемом журнале Microsystems & Nanoengineering. В ноябре Университет Макгилла представил эксперимент широкой аудитории. Пока учёные доказали работоспособность нового вычислительного принципа, но не создали устройство, способное заменить обычный компьютер. Дальнейший успех зависит от того, удастся ли управлять миллионами размножающихся клеток без потери точности и превращения микроканалов в пробки.