В прошлом году сбой в системе распределения работы между сотрудниками American Airlines мог привести к нарушению графика тысяч полётов в праздничный сезон. Ошибка позволяла пилотам отказываться от полётов без того, чтобы его заменял другой пилот, и под угрозой оказалось порядка 15 000 полётов.

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

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

Триумф алгоритмической науки и закона Мура состоит в том, что мы теперь можем подступиться ко множеству сложных задачи по оптимизации, включая такие области, как перевозки, логистика и составление расписаний. Большая часть современного мира не сможет нормально функционировать без этих алгоритмов: ежегодно 50 000 грузовых судов перевозят товары, вырабатывается 25 000 ТВт*ч электричества, а роутеры проводят через себя 1 Зеттабайт трафика. Всё это работало бы куда как менее эффективно. Однако организации часто работают с неоптимальными решениями из-за поджимающих сроков сдачи и недостатка доступных компьютерных ресурсов. Более того, ещё полно возможностей для улучшения используемых нами методов, помогающих решать большую часть задач оптимизации.

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

Один многообещающий подход – разработка оптических машин, предназначенных для оптимизации. Группа учёных из Стэнфордского университета (куда входит и автор статьи) под руководством Йошихика Ямамото начала эти исследования семь лет назад. Теперь эту тему изучают несколько групп учёных, а также исследователи из лабораторий HP и NTT. Спустя годы работы появляется всё больше уверенности в том, что по меньшей мере одна из этих групп когда-нибудь сможет создать машину, которая могла бы помочь нам подступиться к некоторым из наиболее сложных задач оптимизации, решение которых требует современная промышленность.

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

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

Для пяти городов задача решается просто. Её можно просчитать, просто рассмотрев все 12 путей. Однако если трудяга-продавец намеревается посетить 50 городов, тогда метод перебора, рассматривающий все возможные пути, окажется непосильным – этих путей будет больше, чем новемдесиллион, или 10⁶⁰ — единичка и 60 нулей.

Возможные решения такой задачи могут дать нам алгоритмы, использующие различные пути обхода и разумные приближения. Но даже наилучшие из них могут заставить задуматься самый мощный компьютер. В недавнем примере Университет Ватерлоо из Канады пытался найти кратчайший путь между почти 50 000 городами США, попавшими в национальный реестр исторических мест, и доказать правильность своего решения. Для этого он использовал 310 мощных процессоров, работавших без остановки 9 месяцев.

Но к оптимизации относится гораздо больше задач, чем только задача коммивояжёра. Ещё одна сложная задача состоит в составлении расписания. К примеру, Национальная футбольная лига в США должна ежегодно составлять расписание нескольких сотен игр, пытаясь при этом соответствовать тысячам правил, которые, например, запрещают командам играть больше трёх игр не на своём поле подряд. Для решения этой задачи в 2017 году NFL воспользовалась кластером из 400 компьютеров.

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

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

Исследователи много лет пытаются создать специальные машины для решения задач оптимизации. В середине 1980-х Дэвид Тэнк, работавший тогда в лабораториях AT&T Bell, и Джон Хопфилд, работавший как в AT&T Bell, так и в Калтехе, предложили использовать аналоговые электронные схемы, представляющие нейросети, для решения таких задач оптимизации, как задача коммивояжёра. Их работа породила десятилетия исследований этого направления. Затем в 1994 году Леонард Эдлман из Южнокалифорнийского университета, обнаружил, что в теории ДНК можно использовать для решения проблем подобного типа. Его идея породила сходный шквал исследований. Однако эти попытки разработать радикально новые и эффективные подходы к решению задач оптимизации привели к практическим альтернативам обычных компьютеров и технологий, остающихся сегодня основными инструментами для решения таких задач.

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

Чтобы понять, как модель Изинга связана с оптимизацией, нужно начать с её использования в физике для понимания магнетизма. Рассмотрим обычный магнитный брусок. Используя модель Изинга можно представить себе магнитный брусок, как трёхмерную решётку атомов, в которой каждый из атомов сам представляет собой магнитный брусок. У электронов в атомах есть свойство под названием спин. Спины валентных электронов – находящихся на внешних оболочках атома – направлены либо вверх, либо вниз. Направление спинов определяет намагниченность материала. Если все спины направлены вверх, материал намагничен. Если вниз, материал тоже намагничен – только с противоположной полярностью. Если спины смешаны, материал не намагничен.

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

Оптическая машина Изинга: оптический параметрический осциллятор (ОПО) с обратной связью измерений может решать задачи оптимизации, выраженные в форме модели Изинга – набора спинов электронов и их влияние друг на друга. Фазы оптических импульсов в ОПО представляют спины, а влияние вносится в программируемую пользователем вентильную матрицу (ППВМ). Нужно совершить порядка ста проходов по системе до того, как импульсы в ОПО станут достаточно мощными, чтобы выдать решение задачи.

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

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

Так как же преобразовать путь коммивояжёра в спины? Основная задача – это постановка соответствия: нам надо представить нашу задачу оптимизации в такой форме, в которой ей сможет решить машина, предназначенная для решения задач оптимизации Изинга. Для начала нужно сопоставить исходную задачу оптимизации – к примеру, поиск пути для продавца пылесосов – с набором спинов, и определить, как спины влияют друг на друга. Благодаря исследованиям, проведённым за последние десятилетия как в области информатики, так и в исследовании операций, сопоставление различных задач оптимизации с формами Изинга в целом известно.

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

Ключом к возможности нашего прототипа сопоставлять спины импульсам света является ОПО, устройство, напоминающее лазер. Но ОПО, в отличие от обычного лазера, выдаёт свет, находящийся точно в фазе, или точно в противофазе к некоему базовому свету. Именно это необходимо для представления бинарных состояний спина, вверх и вниз. Мы можем представить спин, направленный вверх, как состояние, в котором свет ОПО находится в фазе с базовым, и наоборот, спин, направленный вниз, соответствует свету в противофазе.

Создать машину Изинга при помощи ОПО можно несколькими способами. Группы из NTT, Калтеха, Корнелла и Колумбии, среди прочих, испытывают различные подходы. Прототип машины Изинга, впервые показанный в Стэнфорде в эксперименте под руководством Алирезы Маранди (который теперь работает в Калтехе) использовал технологию, с которой мы продолжаем работать и далее: мультиплексный ОПО с разделением по времени и оптическим соединением.

Давайте разберём этот сложный термин. Мы начинаем с импульсного лазерного источника. Источник отправляет одновременный импульсы света длительностью в несколько пикосекунд в двух направлениях. Первый импульс становится базовым; он расщепляется, и идёт по двум разным путям.

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

Вверху: Автор статьи и его бывший партнёр по лаборатории Алиреза Маранди смотрят на прототип оптического компьютера Изинга. Внизу: большая часть событий происходит внутри катушки оптического кабеля

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

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

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

Критически важно выбрать правильный момент – нам нужно, чтобы изменённый базовый импульс скомбинировался с правильным импульсом ОПО. Если всё сделать правильно, два импульса смешатся. В зависимости от того, находятся ли они в фазе, или нет, введённый в систему импульс склоняет импульс ОПО к представлению спина, направленного либо вверх, либо вниз.

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

В наших экспериментах мы сначала сделали систему с четырьмя спинами, а затем – с 16 спинами. Параметры задачи были аппаратно заложены в установках в виде разветвляющихся отрезков оптического кабеля определённой длины. В этих экспериментах мы успешно обнаружили состояния минимальной энергии, и это дало нам мотивацию к развитию этого подхода. В 2016 году мы создали машину с обратной связью на основе ППВМ, способную решать задачи Изинга со 100 спинами. Сравнение скорости работы нашей установки со специализированными системами, включая аппарат «квантового отжига» из НАСА, дало нам уверенность в том, что ОПО-машины Изинга могут быть эффективными оптимизаторами.

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

Автор: Вячеслав Голованов