Ученые решили задачу раскраски графов без двоичных представлений

Команда ученых Технологического института Джорджии и Университета Нотр-Дам (США) разработала новую компьютерную систему, способную за секунды решать самые сложные задачи, на которые обычно уходят недели.

Проблема раскраски графов — визуальное представление набора объектов, соединенных между собой определенным образом — требует присвоить вершинам цвета таким образом, чтобы любые два смежных цвета не совпадали. Желательно также использовать наименьшее количество цветов.

Новая технология использует сеть электронных осцилляторов для решения задач раскраски графов — проблемы, которая с трудом поддается современным компьютерам. "Мы хотели найти способ решать задачи без использования двоичных представлений, которые десятки лет были основой вычислительной техники, — говорит профессор Ариджит Райчоудхури. Работа ученых была опубликована в журнале Scientific Reports.

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

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

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

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

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

Комментарии: