Наталия Берлова: путь к оптимальному решению NP-задач можно проложить, комбинируя свет и вещество в «волшебную пыль»

24 октября 2017 г.

«Мы сможем пересылать свои эмоции и чувства через сети». Это одна из самых запомнившихся фраз прошедшего на днях в Сколково форума «Открытые инновации» принадлежит физику-теоретику и футурологу Митио Каку. Согласно другому его прогнозу, достижения квантовых технологий позволят сохранять память людям с болезнью Альцгеймера. Новый интернет, утверждает японский ученый, станет сетью, которая свяжет один человеческий мозг с другим без посредников.

Субъективное наблюдение за дискуссиями на «Открытых инновациях» позволило выявить два ключевых понятия, которые чаще других упоминались в течение трех дней работы форума, посвященного цифровой экономике. Это, разумеется, модный блокчейн и – квантовые технологии. Одна из панелей первого дня так и называлась: «Прикладные квантовые технологии. Как меняется мир?»

Наталия Берлова в лаборатории гибридной фотоники Сколтеха. Фото: Sk.ru

Зачастую рассуждения сводились к обсуждению возможностей квантового компьютера и основывались на том неочевидном предположении, что квантовый компьютер будет создан в самое ближайшее время. Между тем в канун открытия форума журнал Nature Materials опубликовал статью профессора Сколтеха и Кембриджского факультета прикладной математики и теоретической физики Наталии Берловой (Natalia Berloff), в которой она рассказала о результатах прорывного исследования: команда ученых из России и Британии продемонстрировала, что квантовые частицы поляритоны, комбинирующие в себе свет и материю, могут быть использованы для решения сложных проблем, и квантовый вычислитель, созданный с их участием, имеет потенциал превзойти возможности самых мощных суперкомпьютеров.

Что такое сложная проблема

Поскольку мало кто, кроме посвященных, способен понять, чем в точности занимаются Наталия Берлова и ее коллеги из Сколтеха, Кембриджа, и университетов Саутгемптона и Кардиффа, в интервью, которое профессор дала Sk.ru, достаточно много метафор и аналогий. Потому что прежде, чем замахнуться на «волшебную пыль» (остроумная метафора, использованная в пресс-релизе Кембриджа), с помощью которой Наталия Берлова с товарищами намерена создавать новый тип суперкомпьютера, следует осознать, зачем это нужно. Что с неизбежностью приводит к разговору о том, что такое просто и что такое сложно.

Например, создать новую 38-ю пьесу Шекспира, проанализировав предыдущие 37, – задача высшей сложности, говорит профессор Берлова, равно как возможность полностью предсказывать поведение финансовых рынков или повернуть вспять эволюцию: «Это равносильно тому, чтобы найти кратчайшую логическую цепочку в любом массиве данных, - рассуждает она. - Иными словами, человек начинает обладать божественной властью».

«Вопрос стоит так: давайте построим не универсальный квантовый компьютер, а сделаем нечто иное: решим конкретную задачу, на  которую любая другая задача класса NP-полных задач может быть отображена»

Когда Льва Толстого однажды спросили, о чем роман «Анна Каренина», он ответил, что ему проще написать новый роман, чем описать уже созданный. Если провести рискованную аналогию между великим романом и квантовой системой, можно перебросить временной мостик из века 19-го на сотню лет позже, в 1982 год, когда один из создателей квантовой электродинамики американский физик Ричард Фейнман, исходя из предположения, что квантовую систему невозможно просчитать на компьютере, предложил создать новую квантовую систему, которую можно будет использовать, чтобы понять, что происходит в той системе, которую мы просчитать не можем. Отсюда возник термин квантовый симулятор, или квантовый вычислитель: одна квантовая система, которая ведет себя, как другая, но – в отличие от первой – полностью контролируема.

Эта экскурсия во времени необходима, по мысли Наталии Берловой, чтобы понять степень сложности проблем, которые можно решать с помощью квантового симулятора.

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

Наталия Берлова приводит пример. «Число 15 мы можем разложить в уме (5х3). Если в числе 100 знаков, его разложить поможет суперкомпьютер. А вот в основе системы RSA [криптографический алгоритм, основывающийся на вычислительной сложности задачи факторизации больших целых чисел – Sk.ru] уже лежат числа, в которых может быть тысячa символов (цифр). И это уже невозможно разложить на множители, хоть миллиард лет считай на классическом компьютере. Шор показал, что квантовый компьютер решит такую задачу гораздо быстрее. Под квантовым компьютером он подразумевал, что его основой вместо бита становится кубит, т.е. вместо нолика и единички – вектор, который живет на сфере и описывается двумя комплексными числами – «амплитудами»; притом у нас может быть суперпозиция или запутанность квантовых состояний; если у нас есть n кубитов, то система способна одновременно рассматривать 2n  комбинаций элементов. В популярной литературе появились предположения, что уж теперь-то мы сможем считать экспоненциально растущие задачи, потому что экспонента заложена в саму идею квантового компьютера. Но есть одна проблема: в момент измерения мы видим только одно состояние системы, с вероятностью зависящей от амплитуды. Идея Шора заключалась в том, чтобы организовать вычисления таким образом, чтобы решение с большой вероятностью появляется во время измерения. И вот это тот конкретный алгоритм, который квантовый компьютер, если он когда-нибудь будет создан, сможет эффективно решать. Отсюда берет начало бум, связанный с квантовым компьютером, – универсальной машиной, использующей запутанность квантовых элементов.

Трудности перевода

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

Наталия Берлова. Фото: Sk.ru

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

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

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

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

Зачастую реальная сложность задачи скрыта за ее кажущейся простотой. Такова известная «задача коммивояжера». Дан набор городов, требуется найти оптимальный путь между этими городами. «В действительности эта задача относится к числу самых сложных; эффективного (растущего как степенная функция) способа ее решения не существует, - говорит профессор Сколтеха. - Если я буду искать оптимальное решение перебором, то для всего лишь 70-ти городов потребуется потратить миллиард лет на работу суперкомпьютера. При увеличении количества городов сложность возрастает экспоненциально. Есть более быстрые алгоритмы решения, которые используют внутреннюю структуру задачи, но и они не могут преодолеть экспоненциальный рост количества операций с ростом числа городов. И это грустно, так как такая задача в различных модификациях ложится в основу огромного количества других задач, например в секвенировании ДНК, при которой «города» становятся фрагментами ДНК, а «оптимальный путь» определяется похожестью фрагментов».

Более того, «задача коммивояжера» принадлежит к особому классу NP-полных (самых сложных) задач. Таких задач сейчас известно 3 тысячи. «Если вы эффективно решите одну из них, найдете полиномиальное решение, – решите все задачи».

Это и есть та самая кратчайшая логическая цепочка в любом массиве данных, нахождение которой, как выражается Наталия Берлова, дает человеку «божественную власть». «Другое дело, что, как можно предположить, божественная власть нам все-таки не под силу, - улыбается она. - Что бы вы ни делали, экспоненциальный рост, наверное, где-то себя проявит. Но тут мы говорим: мы не пытаемся найти полиномиальный алгоритм, мы просто хотим быть быстрее, чем классический компьютер, это уже дает нам огромное преимущество в создании искусственного интеллекта, расшифровки любых кодов и т.д.

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

Для перебора всех вариантов экспоненциально растущей задачи универсальный квантовый компьютер (если такой будет построен, что вообще-то не факт) дает совсем небольшое улучшение в сравнении с классическим компьютером. То есть на решение задачи вместо миллиoна лет потребуется несколько тысяч лет.

«Поэтому вопрос стоит так: давайте построим не универсальный квантовый компьютер, а сделаем нечто иное: решим конкретную задачу, на  которую любая другая задача класса NP-полных задач может быть отображена. В нашем случае, это нахождение абсолютного минимума модели XY. Речь идет о функции в пространстве большой размерности, и вам надо найти самую низкую точку этой функции», - формулирует Наталия Берлова.

И вот тут мы непосредственно подходим к тому, что же собственно сделала группа российских и британских исследователей.

Кратчайший путь к оптимальному решению

Но прежде, чем мы обратимся к работе научного коллектива, несколько слов о человеческой стороне этой работы. Три года назад коллеги из Сколтеха пригласили Берлову принять участие в так называемом «Форсайт-флоте». РВК, организующая это действо, так определяет его: ««Форсайт-флот» — уникальный, не имеющий аналогов в России и мире, формат групповой коммуникации, в ходе которой участники совместно разрабатывают дорожные карты отраслевого и территориального развития и проекты по наиболее значимым и перспективным направлениям». Сказать проще, специалисты в самых разных инновационных областях на несколько дней оставляют свои непосредственные занятия и отправляются в плавание по реке ради вот этой самой «групповой коммуникации», из которой впоследствии иногда рождаются новые инициативы.

Наталия Берлова поначалу принимала участие в дискуссиях, а затем не устояла перед соблазном запереться в своей каюте и начать делать расчеты. «Так родилась теоретическая часть этой работы, - рассказывает она. – Я потом сказала [вице-президенту Сколтеха - Sk.ru] Алексею Ситникову, что очень благодарна ему за приглашение. Так спокойно мне давно не работалось».

Поляритонный графический симулятор. Изображение предоставлено Наталией Берловой.

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

Группа Наталии Берловой предложила новую концепцию квантового симулятора. В ее основе – поляритон, гибридная частица, состоящая из света и вещества. В отличие от атомов, эти частицы не являются «естественными», но создаются внутри встроенных в наноструктуры полупроводников. С помощью лазера на тончайших слоях напылений атомов галлия, мышьяка, индия и алюминия создается та самая «волшебная пыль»: расположенные на тонких атомных слоях, электроны поглощают и излучают свет определенного цвета. Этот свет отражается от зеркал и возвращается в т.н. «квантовые ямы», возбуждая электроны при каждом таком возврате. Что создает непрерывное колебание энергии между светом и веществом. Вот так, собственно, и образуются поляритоны, которые, благодаря фотонной составляющей, в тысячи раз легче электронов и в миллиарды раз – обычных атомов.

Роль поляритонов сродни роли маяка: «волшебная пыль» начинает светиться (превращаться в новое состояние вещества – конденсат Бозе-Энштейна) только в абсолютном минимуме функции большой размерности. Что потенциально позволяет находить оптимальное решение любой из задач класса NP. Это не наделяет человека возможностями бога, но создает колоссальные новые возможности, превосходящие производительность любых из существующих классических суперкомпьютеров.

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