О чем сегодня ученые заставляют думать квантовые процессоры

[admin_]

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

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

Чтобы сделать универсальный квантовый вычислитель, нужно решить две проблемы: инструментальную и логическую. Первая — это вопрос о кубитах, о том, из каких квантовых объектов лучше всего делать процессоры для таких вычислителей. С выбором между электронами, фотонами, ионами, сверхпроводниками и прочими кандидатами на квантовые транзисторы ученые не могут определиться до сих пор, поэтому занимаются сразу всеми. В лидеры этой гонки кубитов выбивается то одна платформа, то другая.

Второй вопрос — какие вообще задачи можно решать на этих машинах.

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

нашем материале
про квантовые вычисления). Но сделать алгоритмы, которые уже можно было бы запустить на квантовых компьютерах, — сложнее.

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

Если с помощью этой схемы квантовый компьютер сможет раскладывать на множители хотя бы стозначные числа, это позволит взломать популярную сейчас систему RSA-шифрования. Шор наглядно показал, как с помощью квантового компьютера можно взломать любую защищенную линию связи. На то, чтобы подобрать ключ к RSA-шифру, у классического компьютера уйдет триллион лет. Квантовый сможет взломать такой же шифр за восемь часов.

Правда, для этого ему потребуется миллион кубитов.

В 2001 году первый шаг был к победе над RSA как будто бы был сделан: квантовый вычислитель IBM разложил на простые множители двузначное число 15. Сегодня квантовые вычислители могут воспроизвести алгоритм для трехзначного числа 143, но за эти 20 лет дальше дело так и не пошло. Более того, непонятно даже, как вообще двигаться. Для чисел подлиннее современным квантовым компьютерам просто не хватает кубитов. Нужно либо сильно увеличивать их число, либо придумывать, как эту задачу решать на кудитах — квантовых элементах с большим числом квантовых состояний.

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

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

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

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

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

Алгоритм Гровера для поиска элемента в наборе. Слева в скобках |⟩ — начальное состояние двух кубитов: один в состоянии 0, другой в состоянии 1. Однокубитные вентили: <i>H</i> (<a href=https://en.wikipedia.org/wiki/Quantum_l ... amard_gate target=_blank>оператор Адамара</a>, который создает состояние суперпозиции), <i>I</i> (единичное преобразование), |0⟩⟨0| (проектор на состояние 0) — на схеме расположены в одной строке. Двухкубитный универсальный вентиль <i>U</i>𝜔 — захватывает сразу две строки. В конце схематичной стрелкой со шкалой изображен измеритель состояния первого кубита

Алгоритм Гровера для поиска элемента в наборе. Слева в скобках |⟩ — начальное состояние двух кубитов: один в состоянии 0, другой в состоянии 1. Однокубитные вентили: H (оператор Адамара, который создает состояние суперпозиции), I (единичное преобразование), |0⟩⟨0| (проектор на состояние 0) — на схеме расположены в одной строке. Двухкубитный универсальный вентиль U𝜔 — захватывает сразу две строки. В конце схематичной стрелкой со шкалой изображен измеритель состояния первого кубита

Wikipedia

Квантовые вычисления имеют вероятностный характер: любой из вентилей возвращает значение 0 или 1 с определенной вероятностью. Из мира вероятностей и распределений кубиты возвращаются в границы жесткого детерминизма после измерения: им заканчивается любая квантово-логическая цепочка.

Такая гейтовая модель (от gate — вентиль) вычислителей, нужна для алгоритмов Шора и Гровера. В них на старте есть какое-то входное состояние, которое проходит определенное число вентилей и заканчивается измерением. Проблема в том, что создавать вентили, которые будут без сбоев выполнять предписанное им преобразование, непросто. Если вентиль не идеальный, то на выходе получается много ошибок, и часто нужную задачу вовсе не удается решить.

С ошибками можно бороться с помощью кодов коррекции, как и в классическом компьютере, но для этого нужны дополнительные кубиты. А это роскошь для нынешних квантовых технологий. Увеличение квантового вычислителя даже на один кубит — сложная техническая задача. Из рекордсменов по числу кубитов — 53-кубитный вычислитель Sycamore, на котором Google продемонстрировал квантовое превосходство. В современных устройствах, претендующих на звание квантового компьютера, число кубитов не превышает сотни.

Часть кубитов в любом случае уходит на коррекцию ошибок — и чаще всего вспомогательных кубитов даже больше, чем непосредственно «считающих» кубитов, иногда значительно. Например, в прошлом году на один устойчивый логический кубит в ионном вычислителе ученым

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

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

Лучшие квантовые вычислители для алгоритмов Шора и Гровера были сделаны уже больше 20 лет назад на

ЯМР-платформе
, с которой давно не работают как раз из-за невозможности ее масштабировать. Самая цитируемая работа по реализации алгоритма Шора была

опубликована
в 2001 году. Для разложения больших чисел 15 кубитов все еще не хватает, даже несмотря на то, что физики ищут и

находят
пути масштабирования алгоритма. С алгоритмом Гровера дело обстоит

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

масштабируемостью
, для нынешнего поколения вычислителей кое-какие задачи нашлись. Но немного иные.


Классика в помощь
Работа нашлась для шумных квантовых компьютеров промежуточного масштаба (noisy intermediate-scale quantum, NISQ) — это вычислители с небольшим временем декогеренции, управление и подготовка квантовых состояний в которых часто проходит с ошибками. Алгоритмы для таких устройств не похожи на те, что придумали Шор и Гровер. Зато им достаточно неидеальных кубитов и не нужна коррекция ошибок.

Логические схемы этих вычислителей заточены под конкретное устройство, то есть они a priori не универсальные. А квантовые эффекты в них используются для решения отдельных задач под управлением классического компьютера. Задачи такие есть, и Google, IBM и другие технологические гиганты экспериментируют сейчас с их реализациях на своих машинах.

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

Решение оптимизационной задачи — это, по сути, минимизация (или максимизация) целевой функции. В случае с квантовым вычислителем целевая функция — это гамильтониан, оператор полной энергии исследуемой квантовой системы. В отличие от классической функции, которая может быть математической абстракцией, у него всегда есть конкретный физический смысл. Для квантового вычислителя это, собственно, энергия системы кубитов, а ее минимум — основное состояние системы, которое нужно найти. А если изначальную функцию нужно было не минимизировать, а максимизировать, то гамильтониан составляют такой, чтобы его минимум, наоборот, соответствовал максимуму целевой функции.

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

Квантовое машинное обучение
Первый способ облегчить поиск основного состояния — перекинуть на обычный компьютер часть задачи. Такие объединенные вычислители выполняют гибридные квантово-классические алгоритмы. Вся логическая нагрузка здесь ложится на классический вычислитель. Квантовая часть просто готовит нужное квантовое состояние, чтобы можно было провести его измерение — никакой логики для этого нужно. А все задачи решают обычные транзисторы. Вычисления по такой схеме называют квантовым машинным обучением, а к названию алгоритмов добавляют уточнение «вариационные».

Стеклянный чип для вариацианного алгоритма. Напыляя на его поверхность металл, можно управлять фотонами, которые двигаются по волноводу (на фото светится красным)

Стеклянный чип для вариацианного алгоритма. Напыляя на его поверхность металл, можно управлять фотонами, которые двигаются по волноводу (на фото светится красным)

Центр Квантовых Технологий МГУ; НОЦ ФМН, Московский государственный технический университет имени Н.Э. Баумана

Со стороны это выглядит как классический компьютер плюс квантовый черный ящик. Компьютер перебирает стартовые состояния квантовой системы и затем считывает результат, который та выдает. Классическую половину вполне устраивает такой режим работы: неважно, как именно квантовая половина получает те или иные данные, достаточно просто понимать, что именно она приносит.

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

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

Работа оптимизационного алгоритма: квантовая система ищет минимум ландшафта

Работа оптимизационного алгоритма: квантовая система ищет минимум ландшафта

Оксана Борзенкова

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

Сейчас используют два вида вариационных алгоритмов — алгоритм нахождения собственных значений операторов (variational quantum eigensolver, VQE) и алгоритм приближенной оптимизации (quantum approximate optimization algorithm, QAOA).

Схема работы алгоритма VQE

Схема работы алгоритма VQE

Оксана Борзенкова

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

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

Второй тип вариационных алгоритмов (QAOA) отличается от первого только структурой слоев. Если для VQE можно использовать любые преобразования состояния, то QAOA использует знание о заданной гамильтониане и помимо преобразований в стиле VQE воздействует на свое состояние гейтами, связанными с гамильтонианом. Это усложняет схему и вводит дополнительные варьируемые параметры в схему, но сужает область поиска нужных параметров для приготовления основного состояния.

Кремниевый чип для вариационного алгоритма

Кремниевый чип для вариационного алгоритма

Центр Квантовых Технологий МГУ; НОЦ ФМН, Московский государственный технический университет имени Н.Э. Баумана

В отличие от чисто квантовой логики, вариационные алгоритмы применяют уже сейчас. Например, в IBM изучают их применимость в задачах из квантовой химии. В частности, с помощью них проводят квантово-химические расчеты для разработки литий-серных аккумуляторов, которые должны прийти на смену литий-ионным. Ими, в частности, интересуется автомобильная компания Daimler, которая сотрудничает с IBM. А подразделение Google Quantum AI планирует использовать гибридные вычисления для молекулярного моделирования: они будут работать с фармацевтической компанией «Берингер Ингельхайм» над созданием лекарств.

В 2021 году Volkswagen использовал квантовые алгоритмы для оптимизации трафика в Лиссабоне, а Boeing планирует распределять багаж на основе квантовых вычислений. Испанский банк BBVA в 2020 году провел эксперименты на адиабатическом квантовом вычислителе по статической оптимизации инвестиционного портфеля более чем из 100 акций.

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

Такой метод называют адиабатической эволюцией, пионерами в его реализации стала канадская компания D-Wave. Несмотря на то, что их подход ставят под сомнение многие ученые — стоит ли считать его по-настоящему квантовым? — машины D-Wave используют, бизнес канадцев процветает.

Одно из квантовых устройств D-wave

Одно из квантовых устройств D-wave

D-wave

Google, который тоже скептически относился к компьютерам D-Wave, купил их вычислитель, чтобы разобраться, как он работает. Приглашенные корпорацией ученые после ряда экспериментов подтвердили, что машина D-Wave способна показать ускорение в решении тех все тех же оптимизационных задач (подробнее об этих задачах можно прочитать в материале «Взять и потрясти», а о том, как устроены машины D-Wave, N + 1 рассказывал главный конструктор архитектуры их процессоров).

Адиабатическая эволюция. Последовательное изменение рельефа, в яме которого лежит квантовое состояние

Адиабатическая эволюция. Последовательное изменение рельефа, в яме которого лежит квантовое состояние

Оксана Борзенкова

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

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

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

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

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

Поэтому квантовые вычислители пока что занимаются шумными вычислениями.

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

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

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