Российские ученые подсказали эффективные алгоритмы для квантового компьютера

Физики, среди которых – сотрудники Института теоретической физики имени Ландау изучили, как в больших квантовых системах нарушается принцип эргодичности. Помимо того, что исследование позволяет лучше понять поведение таких систем, его результаты полезны для разработки поисковых алгоритмов для квантовых компьютеров. Поиск информации в больших базах данных – задача, с которой квантовый компьютер справляется намного эффективнее классического, поэтому создание работающих алгоритмов является крайне актуальным. Работа опубликована онлайн в журнале Annals of Physics. Принцип эргодичности – свойство динамических систем проходить по всем доступным для них состояниям. При этом неважно, из какого начального состояния стартовал процесс, необходимо лишь, чтобы время ожидания было достаточно большим. Если в качестве динамической системы рассмотреть один атом в комнате, то, подождав достаточно долго, мы обнаружим, что он побывал во всех углах этой комнаты. Но если представить, что у нас есть не один, а целое множество атомов, которые образуют кристалл, то окажется, что принцип эргодичности нарушен, так как каждый из атомов всегда находится в окрестностях одной точки. Такая же ситуация наблюдается, если у нас имеется не кристалл, а стекло. Возникает вопрос: если имеется большая, но конечного размера квантово-механическая система, в каких условиях она удовлетворяет принципу эргодичности, а в каких нет, и как происходит превращение одного состояния в другое. Этот вопрос интересен не только с чисто научной точки зрения. Постепенно люди научаются создавать очень большие, хорошо изолированные от внешнего мира квантовые системы – квантовые компьютеры. Самый большой из существующих принадлежит компании Google и состоит примерно из 70 кубитов. Через несколько лет, вероятно, появятся квантовые компьютеры из сотен и тысяч кубитов. К таким большим системам уже приложимы понятия квантовой статистической физики, и в частности – теории квантовых стекол, то есть квантовых систем, нарушающих принцип эргодичности. Из теории таких систем мы уже знаем некоторые их свойства, и они накладывают серьезные ограничения на возможности работы квантовых компьютеров —однако еще далеко не все в этой области физики понято, и не все существенные ограничения выявлены. Авторы работали с относительно простой моделью, включающей большое количество переменных. Они выясняли, в какой области параметров системы она находится в эргодической фазе, в какой – нет, и как эта эргодическая фаза устроена. Модель представляла собой куб в пространстве большого числа измерений: n-мерный куб, где n очень велико. Соответственно, количество вершин такого куба – 2n – было огромным. Каждой вершине куба приписывалось некое случайное значение энергии, причем все значения выбирались из одного и того же гауссова распределения с постоянной шириной. Дальше ученые предполагали, что есть частица, способная прыгать с вершины на вершину – амплитуда такого квантового прыжка была небольшой и задавалась изначально. Физики хотели выяснить, будет ли такая частица уходить сколь угодно далеко или вскоре остановится. Оказалось, что у этой задачи есть три возможных решения, зависящих от энергии частицы. Есть область энергий частицы, в которой она перемещается по всему кубу. Есть область, когда она прыгает только на несколько ближайших вершин. И есть промежуточная область, в которой частица, начав движение с какой-то случайной точки, через большое время оказывается распределена по части куба (то есть ее можно обнаружить в любой точке этой области куба). Число точек, до которых частица может добраться в этом случае – 2αn, где α – число от 0 до 1. С одной стороны – это большое число, но с другой – это всего лишь малая доля от всех возможных вершин. Например, если α равно 0,5, 2αn представляет собой корень из общего числа вершин. «Мы выяснили, что есть широкая область параметров задачи, в которой реализуется именно такое промежуточное состояние, – рассказывает один из авторов работы, заведующий сектором квантовой мезоскопии ИТФ имени Ландау Михаил Фейгельман. – Более того, характерное время τ, за которое частица «расползается» по этой области пространства, оказывается очень большим — оно растет как экспонента от числа узлов n, то есть τ ~ 2nβ, где β – другое число, находящееся между 0 и 1. В этом смысле такое поведение очень похоже на состояние стекла – можно сказать, это его простейшая модель. Стекло характерно тем, что в нем имеется много очень медленных движений. Если посмотреть на стекла возрастом несколько сотен лет, становится очевидно, что это вязкая жидкость: они явно утолщаются книзу и истончаются вверху. Время, за которое что-то в стеклах меняется, конечно, но очень велико. Причем у стекла нет какого-то одного определенного времени изменений, есть много разных – какие-то части быстрее двигаются, какие-то медленнее. Наша модель — первая, в которой удалось получить теоретические результаты для таких «стеклоподобных» квантовых систем, находящихся в строгой изоляции от внешнего мира, и проверить эти предсказания при помощи прямого численного эксперимента». Кроме того, изученная физиками модель будет полезной для исследования квантовых алгоритмов. Около 20 лет назад было строго доказано, что в решении задачи по поиску в больших базах данных квантовый компьютер может быть эффективнее классического. Для этого был придуман так называемый алгоритм Гровера. Число операций, необходимых для классического поиска в бесструктурной базе данных размера N, также имеет порядок N. «Для связи с исследованной моделью будем считать, что позиции в базе данных соответствуют узлам гиперкуба, то есть N= 2n. Квантовый алгоритм Гровера позволяет осуществить поиск за √(2n) ходов, – объясняет Фейгельман. – Но этот алгоритм очень чувствителен ко всевозможным ошибкам. Чтобы искать что-то в базе с его помощью, нужно иметь настоящий, не существующий пока нигде квантовый компьютер, который умеет исправлять свои ошибки и работает бесконечно долго. В ближайшее время подобные машины созданы не будут. Поэтому многих интересует вопрос: нельзя ли придумать пусть не такой быстрый, но зато более устойчивый алгоритм, при помощи которого можно было бы находить хорошие решения за несколько бОльшее число ходов, чем теоретический предел Гровера, но зато без обязательного требования коррекции всех ошибок». К ответу на этот вопрос недавно попытались подойти теоретики из Google. Математически алгоритмы поиска чего-либо в базе (и родственные им задачи оптимизации) напоминают модели стекол. Физики из Google изучали довольно простую модель на гиперкубе. Логика их работы была следующей: пусть у нас есть относительно небольшой набор «хороших» вершин на кубе (формально, это вершины с одной и той же низкой (отрицательной) энергией, в то время как все остальные вершины имеют нулевую энергию). Их число M велико, но гораздо меньше полного числа вершин 2n. Мы знаем одну из «хороших» вершин и хотим найти другие подобные. Авторы работы выясняли, можно ли их найти, предоставив систему своей квантовой эволюции, и сколько времени займет этот процесс? «В работе физиков из Google были сделаны умеренно оптимистичные выводы, однако сама по себе модель была слишком упрощенной, – поясняет Фейгельман. – Наша работа предлагает развитие этой идеи в более сложных системах. Найти самое лучшее решение за разумное время в подобных задачах по поиску может быть и невозможно – но можно найти достаточно хорошее решение. И таких достаточно хороших решений много, но во много раз меньше, чем всех возможных состояний. В этом смысле устраивающий нас результат очень похож на промежуточную неэргодическую фазу в описанной нами модели квантового стекла». Развитием этой чисто теоретической работы, как предполагают ее авторы, может оказаться предложение некоторой физической системы – специального вида цепочки из сверхпроводящих джозефсоновских контактов ( такой контакт образуют два сверхпроводника, соединенные тонкой прослойкой диэлектрика, через которую также протекает сверхпроводящий ток). Предварительные результаты показывают, что такая цепочка может иметь свойства, похожие на те, что были обнаружены в описанной учеными теоретической модели — но, что важно, ее можно сконструировать экспериментально и исследовать реальное поведение. Понравился материал? Добавьте Indicator.Ru в «Мои источники» Яндекс.Новостей и читайте нас чаще. Пресс-релизы о научных исследованиях, информацию о последних вышедших научных статьях и анонсы конференций, а также данные о выигранных грантах и премиях присылайте на адрес science@indicator.ru.