Новые квантовые технологии: зачем в Сколтехе создали поляритонный вычислитель
Человечество живет в мире под контролем процессов, которые растут экспоненциально быстро с числом степеней свободы. Для создания автоматизированных систем нам приходится учитывать взаимодействие большого количества элементов. Для разработки новых материалов и лекарств, необходимо комбинировать большое число молекул и выбирать наиболее эффективные из всех возможных комбинаций. Мы моделируем поведение финансовых рынков, учитывая поведение множества игроков. Какие из этих задач человечество может решить эффективно даже для большого количества элементов, а какие быстро станут неподъемными даже для самых мощных суперкомпьютеров?
Экспоненциальная сложность
Что такое экспоненциальная сложность объясню на примере сказки. По легенде, древнеиндийский изобретатель шахмат так поразил Правителя страны своим изобретением, что мог сам назначить себе награду. Он попросил у Повелителя за первую клетку шахматной доски заплатить ему одно зерно пшеницы, за второе — два, за третье — четыре и т. д., удваивая количество зерен на каждой следующей клетке. Правитель легко согласился, удивившись на показавшийся ему этот очень скромный запрос. К его великому изумлению оказалось, что расплатиться невозможно, поскольку количество зерна на шахматной доске превышает весь урожай пшеницы, собранный за всю историю человечества. На всей доске будет 264-1 или 18 446 744 073 709 551 615 зерен, при весе каждого зерна 0,065 грамма их общая масса составит около 1,2 трлн тонн. Эта красивая легенда как нельзя лучше демонстрирует высокую скорость роста экспоненциальных функций.
В реальной жизни задачи другие, но не менее сложные. Теория вычислительной сложности (complexity theory) дает неутешительный ответ: подавляющее большинство задач, с которыми сталкивается человечество, быстро станет недоступным даже для самых мощных суперкомпьютеров. (Оговоримся, что строгое доказательство этого тезиса считается одной из шести великих задач математики, за которое Математический институт Клея наградит миллионом долларов).
Математики добавили к такому пессимистическому выводу элемент надежды. Они выделили подкласс задач под названием NP-полных задач. Если научиться эффективно решать одну из них, то можно так же быстро решить любую другую из очень широкого круга проблем класса NP.
Список NP-полных задач уже содержит более 3000 задач, и, если кто-то найдет алгоритм решения одной из этих задач с ростом операций медленнее экспоненциального (как степенная функция), это приведет к «последствиям невообразимой значимости», по словам австрийского логика Курта Гёделя из его знаменитого письма 1956 года Джону фон Нейману, создателю архитектуры большинства современных компьютеров. Если бы такой алгоритм или метод был найден, это бы позволило найти кратчайшую логическую цепочку в любых данных и любых процессах. По словам Скота Ааронсона, директора Квантового Информационного Института в Техасе, человек смог бы тогда предсказать поведение финансовых рынков, повернуть вспять эволюцию и написать 38-ю пьесу Шекспира, т. е. получить практически божественную власть.
И наоборот, предположение, что NP-полные задачи не могут избежать экспоненциально растущего количества операций, это предположение, что божественные силы никогда не будут в руках человека!
Зачем нужны квантовые компьютеры
Но как же квантовые компьютеры? Кажется, что использование квантовой запутанности позволяет преодолеть проклятие экспоненциального роста, исследуя большое количество возможных решений одновременно. К сожалению, в момент измерения состояния компьютера мы видим только одно возможное решение с некой вероятностью. И искусство написания квантового алгоритма состоит в том, чтобы организовать вычисления таким образом, чтобы вероятность именно нужного нам решения была велика. Что и удалось сделать для задачи факторизации чисел.
Для NP-полных задач квантовые компьютеры тоже предлагают сокращение количества операций, но чрезвычайно скромное: если для классического компьютера потребуется 2n операций для перебора различных вариантов, квантовому компьютеру будет достаточно 2n/2, рост по прежнему экспоненциальный. Например, задачу, которую классический компьютер будет решать миллион лет, квантовый решит за какие-то десятки тысяч лет.
Пока квантовые компьютеры еще находятся в стадии исследования. У них уже появились конкуренты — квантовые вычислители. Они не столь универсальны, каждый вычислитель решает только конкретную NP-полную задачу. Квантовые вычислители обычно используют физические принципы, отличные от параллелизма квантового компьютера. Например, первый и пока единственный коммерчески доступный квантовый вычислитель канадской компании D-wave использует принцип квантового отжига: для нахождения оптимального решения сложной проблемы сначала берется простая задача, для которой оптимальное решение известно. Система сверхпроводящих элементов (на основе которых работает D-wave) настраивается на это решение. После этого простая задача медленно приближается к заданной, а система сверхпроводящих элементов остается в состоянии, отвечающем оптимальному решению уже новой задачи благодаря чудесному свойству квантового туннелирования. Где же прячется проклятие экспоненциального роста в этом случае? Скорее всего, в слове «медленно»! С ростом системы (количества параметров и переменных) приближать простую задачу к заданной придется экспоненциально медленно.
Практический подход
В наших исследованиях в Сколтехе (проведены совместно с лабораторией профессора Павлоса Лагудакиса) мы предложили новую концепцию квантового вычислителя, основанную на новой системе и новом механизме для решения сложных оптимизационных задач, в том числе NP-полных задач. Теоретическое обоснование и экспериментальная демонстрация такого симулятора была опубликована в журнале Nature Materials 25 сентября 2017 года. Основой — битом — такого симулятора служит поляритон, гибридная частица, состоящая из света и вещества. Такие частицы не являются «фундаментальными» или «естественными», такими как атомы или электроны, но создаются внутри полупроводников, встроенных в наноструктуры изысканной точности. Используя тонкие слои атомов галлия, мышьяка, индия и алюминия, мы можем контролировать движение электронов и их взаимодействие со светом.
В наших устройствах электроны, расположенные на таких тонких атомных слоях, поглощают и излучают свет определенного цвета. Вокруг этих «квантовых ям» мы выращиваем чрезвычайно блестящие зеркала, которые эффективно захватывают свет между ними, но только определенного цвета, с длиной волны, установленной зазором микронного размера между зеркалами. Это позволяет свету отражаться и возвращаться в квантовую яму с той же фазой и возбуждать электроны при каждом возврате в одно и то же состояние. Таким образом, энергия непрерывно колеблется между светом и веществом. Эта когерентная смесь электронов и фотонов и образует поляритон, частицу с совершенно новыми свойствами, которые мы можем контролировать, варьируя дизайн эксперимента.
Фотонная составляющая поляритонов делает их в тысячи раз легче электронов и в миллиарды раз легче обычных атомов и позволяет достигать достаточных плотностей, чтобы образовать поляритонный конденсат Бозе-Эйнштейна. В таком состоянии квантовая фаза поляритонов синхронизируется, создавая единый макроскопический квантовый объект, который излучает яркий когерентный свет.
Во время конденсации поляритоны сами принимают наиболее выгодную конфигурацию, тем самым находя оптимальное решение известной задачи статистической физики — XY-модели, которая принадлежит к классу NP-полных задач, а значит, потенциально решая любую задачу класса NP! При этом время конденсации практически не зависит от количества элементов — поляритонов — в системе. Это дает надежду, что, начиная с определенного размера задачи, наш поляритонный симулятор опередит классические вычисления! Учитывая особенности работы со светом и потенциальные возможности системы, в пресс-релизе Кембриджского университета о нашей системе использовали забавную метафору этого процесса — «свечение волшебной пыли».
Но как же проклятие экспоненциального роста NP-полных задач и предположение о невозможности его преодоления? Пока мы не знаем ответа на этот вопрос... Сейчас наша система работает на сотне элементов. Нужно изучить поведение системы при увеличении числа элементов. Даже если не удастся полностью преодолеть экспоненциальный рост, то вполне реально во много раз уменьшить время нахождения оптимального решения по сравнению с классическим компьютером. Поляритонные симуляторы дают нам именно такую надежду!