Чтобы решить эту загадку, ученые активно исследуют возможности использования интегральных схем. В этом методе каждое состояние в задаче коммивояжера (например, каждый возможный маршрут в грузовике для доставки) представлено «спин-ячейками», каждая из которых имеет одно из двух состояний. Используя схему, которая может хранить силу одного состояния спиновой ячейки по сравнению с другим, можно получить взаимосвязь между этими состояниями (или, используя нашу аналогию, расстояние между двумя городами для грузовика доставки).
Используя большую систему, содержащую такое же количество спиновых ячеек и цепей, что и компоненты (или города и маршруты для грузовика доставки) в задаче, мы можем определить состояние, требующее наименьшего количества энергии, или маршрут, покрывающий наименьшее расстояние, таким образом решение задачи коммивояжера или любого другого типа задач комбинаторной оптимизации.
Однако основным недостатком обычного способа использования интегральных схем является то, что он требует предварительной обработки, а количество компонентов и время, необходимое для ввода данных, увеличиваются по мере увеличения масштаба проблемы. По этой причине эта технология смогла решить проблему коммивояжера только в 16 штатах или городах.
Группа исследователей под руководством профессора Такаюки Кавахара с кафедры электротехники Токийского университета науки стремилась решить эту проблему. Они заметили, что взаимодействия между каждой спиновой ячейкой линейны, что гарантирует, что спиновые ячейки могут взаимодействовать только с ячейками рядом с ними, увеличивая время обработки. «Мы решили расположить ячейки немного по-другому, чтобы все спиновые ячейки могли быть связаны», – объясняет профессор Кавахара.
Для этого они сначала расположили схемы в двумерном массиве, а спиновые ячейки по отдельности в одномерном расположении. Затем схемы считывали данные, и совокупность этих данных использовалась для переключения состояний спиновых ячеек.
Это означало бы, что количество необходимых спиновых ячеек и время, необходимое для обработки, были резко сокращены.
Авторы представили свои выводы на 18-м Всемирном симпозиуме IEEE по прикладному машинному интеллекту и информатике (SAMI 2020). «Таким образом, наша новая технология представляет собой полностью связанный метод, – отмечает профессор Кавахара, – и может решить задачу коммивояжера, охватывающую до 22 городов.«Авторы надеются, что эта технология найдет применение в будущем в качестве высокопроизводительной системы с низким энергопотреблением для офисного оборудования и планшетных терминалов, что позволит легко находить оптимальные решения из большого количества комбинаций.