Аналоговый решатель превосходит цифровые компьютеры в NP-трудной оптимизации

• Исследователи построили новую систему, которая может решать квинтэссенциальную дискретную оптимизационную проблему, называемую MaxSAT.
• Этот аналоговый решатель выполняется лучше цифровых компьютеров и может быть расширен на другие оптимизационные проблемы.

Современные цифровые компьютеры хорошо выполняют большинство задач. Они идеальны для определенных вычислений, обработки текста, серфинга в интернете и графических искусств. Но поскольку они полагаются на бинарный код — 0 и 1 — они не идеальны для решения всех проблем.

Цифровые вычисления почти достигли своего максимального потенциала, и поэтому некоторые математики начали проявлять интерес к возрождению аналоговых вычислений. Это может помочь продвинуть вычисления за рамки цифрового фреймворка.

Недавно исследователи из Университета Нотр-Дам и Бабеш-Бояйского университета, Румыния, разработали новый аналоговый решатель, который может оценивать лучшие решения NP-трудных проблем.

NP-трудная проблема означает, что нет алгоритма, который может решить проблему за полиномиальное время. Время, необходимое для достижения решения, растет экспоненциально с размером проблемы. Обычно эти проблемы ассоциируются с медицинской визуализацией, биоинформатикой, сворачиванием белков и планированием.

Исследователи протестировали свой аналоговый решатель на широком спектре NP-трудных проблем и обнаружили, что этот новый метод имеет потенциал вести к лучшим решениям за меньшее время.

Почему аналоговые вычисления?

Аналоговые компьютеры были крайне популярны в середине 20-го века. Каждое большое администрирование и компания, заботящаяся о проблемах динамики, имела гигантский аналоговый вычислительный центр. Их использовали для запуска ракет в космос, управления оружием на линкорах и симуляции авиационной динамики.

В отличие от цифровых компьютеров, аналоговые компьютеры используют недискретные данные, такие как напряжение, вес, скорость, температура и давление. И поскольку они используют непрерывные значения, они иммунны к квантованию шуму.

Аналоговые компьютеры могут быть спроектированы для решения множества проблем. Они могут прямо выполнять математические операции. Например, чтобы вычесть 8 из 3, аналоговые компьютеры вычитают напряжения, соответствующие этим значениям, и сразу предоставляют правильный вывод.

Они могут использоваться для операций в реальном времени и одновременных вычислений. В случае аналоговых проблем они могут предоставлять инсайты проблем и ошибок. И поскольку они не требуют квантования, они идеальны для модуляции/демодуляции сигналов и высокоскоростного управления двигателями.

Источник: Nature Communications | doi:10.1038/s41467-018-07327-2 | Университет Нотр-Дам

Однако цифровые компьютеры захватили рынок в 1980-х. Они были достаточно гибкими, быстрыми и более точными в выполнении общих задач. По мере появления эффективных алгоритмов их производительность стала еще лучше.

Винтажный аналоговый компьютер AMF665D | Источник изображения: Francis Massen / YouTube

Но цифровые компьютеры, включая современные, не могут решать NP-трудные проблемы с большими переменными. Сложность большинства оптимизационных проблем в том, что вы не можете определить, является ли решение(я) оптимальным. Обеспечение того, что нет лучшего решения, так же трудно, как сама проблема.

Аналоговый решатель с высокой производительностью

Новая непрерывная-временная динамическая система может решать квинтэссенциальную дискретную оптимизационную проблему, называемую MaxSAT. Метод опирается на детерминированный набор обыкновенных дифференциальных уравнений и эвристическую технику для предсказания вероятности того, что оптимальное решение было оценено аналоговым временем t.

В аналоговых цепях устраняется узкое горлышко фон Неймана: сама цепь действует как процессор и память. Реализация подхода на цифровых компьютерах, с другой стороны, требует использования алгоритма интегратора обыкновенных дифференциальных уравнений, который дискретизирует непрерывные-временные уравнения и решает их пошагово, обрабатывая ошибки.

В цифровой форме решатель не выполняется эффективно, потому что динамика эволюционирует несколько тысяч связанных обыкновенных дифференциальных уравнений, что является затратным по времени процессом интеграции.

Читайте также: Самые интересные факты о квантовых компьютерах

И поскольку подход использует общие характеристики, он может быть расширен на другие оптимизационные проблемы также. Исследователи планируют спроектировать и построить устройства на базе этого нового подхода.