Блеск и нищета квантовых вычислений

⇡#Ваше слово, товарищ Шор

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

Перспективные квантовые компьютеры, даром что имеют дело с единичными атомами, напоминают по обводам и массе фантастические боевые машины (источник: Quantinuum)

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

Факторизация — это разложение целых положительных (натуральных) чисел на простые множители. Для небольших чисел её тривиально произвести вручную: 6 раскладывается на 2 и 3, 15 — на 3 и 5 и т. д. Но если число достаточно велико, записывается десятками и сотнями значащих цифр, его факторизация превращается в натуральный вычислительный кошмар. Математиками предложен целый ряд алгоритмов, призванных ускорить факторизацию больших чисел на классических компьютерах, но прорывного выигрыша по времени (по сравнению с незатейливым последовательным перебором простых чисел из таблицы — и лобовой проверкой, делится ли изучаемое большое число на них нацело) они всё-таки не дают.

Пошаговая факторизация числа 525: на каждом шаге получается очередной простой множитель (источник: Wikimedia Commons)

Это, кстати говоря, вовсе не плохо — с точки зрения цифровой криптографии. Наоборот: если бы вдруг завтра кто-то обнаружил аналитический способ факторизации больших чисел, под угрозой оказался бы алгоритм шифрования RSA, который применяется сегодня буквально везде — от кодирования данных внутри закрытых от постороннего глаза папок на локальном жёстком диске до передачи чувствительных данных (номеров банковских карт при оплате товаров онлайн, например) через Интернет.

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

8-кубитовый квантовый процессор калифорнийского стартапа Rigetti (2018 г.) для алгоритма RSA угрозы не представляет (источник: Skoltech)

В основе алгоритма Шора лежит сведение разложения на множители к другой задаче, куда лучше оптимизированной для решения на квантовом компьютере, — к поиску периода некой функции. Всё верно: опять налицо тяга различных явлений, описываемых схожими математическими моделями, к взаимному соответствию (аналогии). С привлечением теоремы Эйлера выясняется, что на основе разлагаемого на множители числа нетрудно составить числовой ряд, который — начиная с некоторого момента — гарантированно начнёт повторяться.

Не будем углубляться в математическое изложение этой процедуры — приведём для наглядности лишь один пример из блестящего описания алгоритма Шора, сделанного Скоттом Ааронсоном (Scott Aaronson), профессором Техасского университета в г. Остин. Всем известна последовательность целочисленных степеней двойки:

2, 4, 8, 16, 32, 64, 128, 256…

Каждый из членов этой последовательности может быть взят по модулю любого числа, например 15. Напомним, что «взять x по модулю y» (x mod y) означает «получить остаток от деления x на y нацело». Если делимое меньше делителя, то частное обращается в ноль, а остаток с очевидностью равен самому делимому. Построим новый ряд на основе прежнего:

2 mod 15 = 2,

4 mod 15 = 4,

8 mod 15 = 8,

16 mod 15 = 1,

32 mod 15 = 2,

64 mod 15 = 4,

128 mod 15 = 8,

256 mod 15 = 1

…

Видите закономерность? Вместо ряда бесконечно увеличивающихся чисел (степеней двойки) получился весьма компактный бесконечно повторяющийся ряд с некоторым периодом, в данном случае равным 4 (один за другим повторяются именно четыре числа: 2, 4, 8, 1). Так вот, если в качестве того самого модуля, по которому производится разложение, взять произведение двух простых чисел p и q (а в примере Скотта Ааронсона 15 — это как раз 3 * 5), то период полученной последовательности, как показал Шор, будет нацело делить произведение (p – 1)*(q – 1).

⇡#К вопросу о множественности миров

Наконец-то подходит время собрать воедино всё то, что до сих пор было сказано о квантовых вычислениях, кубитах и принципе суперпозиции, чтобы понять, в чём же всё-таки сила — и одновременно слабость — квантовых вычислений в сравнении с классическими.

Одна из основных слабостей современных реализаций квантовых компьютеров — их невероятная физическая громоздкость (источник: Quantinuum)

Суть метода Шора — в том, что, хотя напрямую из произведения (p – 1)*(q – 1) простые множители p и q получить нельзя, никто не запрещает вычислить периоды множества последовательностей вида

x mod pq,

x² mod pq,

x³ mod pq,

x⁴ mod pq...

для множества же случайным образом подобранных x.

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

Многомировая интерпретация квантовой механики постулирует одновременное существование «параллельных вселенных» с идентичными законами природы и мировыми константами, но находящихся в различных квантовых состояниях (источник: Wikimedia Commons)

Результатами проведённых вычислений будут волны — повторяющиеся последовательности с определёнными периодами. Используя квантовое преобразование Фурье, своего рода проявление интерференции между квантовыми состояниями, не составит труда выделить истинный период — тот самый, что будет нацело делить упомянутое выше произведение (p – 1)*(q – 1).

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

Обычную (не квантовую) интерференцию волн от множественных источников можно наблюдать в дождь в самой обычной луже (источник: Pixabay)

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

Теперь уже, будем надеяться, понятнее, почему в сообщении Google об успехах 52-кубитного квантового вычислителя Sycamore упоминалась 0,2%-ная погрешность полученного результата. Получить нулевую погрешность в ходе деструктивной интерференции можно лишь при бесконечном числе взаимно складывающихся волн, а поскольку кубитов в том эксперименте было задействовано немногим более полусотни, вместо точного ответа исследователи получили некое среднее число плюс определённый интервал допустимых отклонений.

⇡#Темна вода во кубитех

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

Усовершенствованный (с улучшенной коррекцией ошибок) Sycamore планируют применять для моделирования химических реакций — существенно квантовых по своей природе процессов (источник: Phys.org)

Разумеется, нет, — и проблема коррекции ошибок стоит для них даже острее, чем для классических ЭВМ. Хотя реализовать кубиты можно довольно обширным рядом способов, наиболее распространённый сегодня, реализуемый в том числе инженерами Google и IBM, предусматривает интеграцию резонаторов на основе крохотных сверхпроводящих контуров, интегрированных в полупроводниковые микрочипы, — таким образом получаются сравнительно бюджетные и хорошо управляемые квантовые вычислители. Резонаторы могут находиться в одном из двух граничных энергетических состояний (кодирующих |0⟩ и |1⟩).

Под воздействием микроволнового излучения резонатор можно переводить как в одно из этих состояний, так и в любую их комбинацию (допустим, 42% от |0⟩ и 58% от |1⟩). Но вот незадача: только граничные состояния резонатора устойчивы, и потому из любого промежуточного этот квантовый элемент чрезвычайно быстро, за доли секунды, непременно переходит в ближайшее граничное. Это объективный физический процесс, называемый декогеренцией, разрушает суперпозицию волновых функций. Таким образом, само основание алгоритма Шора — деструктивная интерференция — оказывается невозможным вследствие заведомой потери взаимной согласованности колебаний кубитов даже с истинным периодом. Поэтому все вычисления и фиксацию их результатов на реальном квантовом компьютере необходимо проводить за крайне ограниченное время.

Один из ранних прототипов Sycamore (2014 г.) содержал всего 9 кубитов, выстроенных в ряд протяжённостью немногим более 3 мм (источник: Google)

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

Ошибки типа «сбой бита» (bit-flip) приводят к инверсии долей компонентов в составе текущего вектора состояния — вместо 42% от |0⟩ и 58% от |1⟩ получается 58% от |0⟩ и 42% от |1⟩. Ошибки типа «сбой фазы» (phase-flip) едва ли не более опасны с точки зрения алгоритма Шора, поскольку сдвигают фазу вектора состояния сразу на π радиан — и тем самым чрезвычайно сильно вредят процедуре деструктивной интерференции.

Оба типа ошибок в физических реализациях кубитов снижают точность квантовых вычислений (источник: Science)

По свидетельству Грега Куперберга (Greg Kuperberg), математика из Университета Калифорнии в г. Дэвис, когда команда Google в первый раз запустила на Sycamore свою пресловутую задачу — да-да, ту самую, что на квантовом компьютере исполняется «в 158 миллионов раз быстрее», чем на фон неймановском, — она едва смогла получить корректный ответ как раз из-за шумов, нарушавших деструктивно-интерференционную картину. Фактически примерно 1% информативного сигнала тонул в 99% шума — и только строгая равномерность распределения этого самого шума по измеренным результатам позволила выявить на его фоне даже столь слабые проявления истинного ответа.

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

Простой и действенный для фон неймановских машин механизм коррекции ошибок для квантовых вычислений с такой же лёгкостью, увы, реализовать нельзя (источник: Science)

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

⇡#Произошла чудовищная ошибка

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

Одиночный сверхпроводящий контур, используемый для создания кубита, при большом увеличении (источник: Phys.org)

При этом ничто не мешает двум произвольным квантовым системам находиться в запутанном (взаимозависимом) состоянии, когда, скажем, измерение вектора состояния одного из запутанных кубитов не только выдаёт результат для первого, но и одномоментно переводит второй в точно такое же состояние. Запутывание для квантовых резонаторов на микросхемах реализуется через операцию «контролируемое НЕ» — controlled not (CNOT), аналог «исключающего ИЛИ» (XOR) для бинарной логики. Исходно ведомый кубит переводится в состояние |0⟩, и если ведущий сколлапсировал при измерении в состояние |1⟩, то CNOT меняет состояние ведомого, а в противном случае то остаётся прежним.

Произведя квантовое запутывание трёх кубитов — точнее, двух ведущих с одним и тем же ведомым, — получаем, что если у ведущего вектор состояния образован 42% от |0⟩ и 58% от |1⟩, то и у все трёх вместе вектор состояния будет точно таким же — 42% от |0⟩ и 58% от |1⟩. Подчеркнём, что здесь имеет место не точное копирование первого кубита, физически недопустимое вследствие теоремы о запрете клонирования, а именно создание зависимой (запутанной) структуры из трёх кубитов через логический вентиль. Если после измерения состояния ведущего кубита тот коллапсирует в |1⟩, то и остальные два делают то же самое; если в |0⟩ — значит, все три продемонстрируют состояние |0⟩.

После запутывания состояния ведущего и двух ведомых кубитов оказываются взаимно согласованными (источник: Science)

Далее к этой схеме подключаются ещё два вспомогательных кубита: один — к ведущему и первому ведомому из только что рассмотренной тройки, второй — к первому и второму ведомым. Вспомогательные кубиты позволяют выявлять случаи самопроизвольного изменения конечных состояний каждого из трёх основных кубитов вследствие спонтанно возникающих из-за шума ошибок, не нарушая притом запутанности ведущего с обоими ведомыми. Если первый вспомогательный кубит демонстрирует после измерения значение |0⟩, значит, оба контролируемых им основных кубита находятся в одном и том же состоянии.

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

Два вспомогательных (ancillary) кубита, запутанные перекрёстно с тремя основными, позволяют уверенно исправлять одиночные ошибки типа bit-flip (источник: Science)

Увы, этим дело не ограничивается. Описанный механизм коррекции приложим лишь к ошибкам типа «сбой бита»: чтобы выявлять и исправлять ещё и «сбой фазы», требуется схема уже из девяти кубитов, расположенных квадратной матрицей 3 × 3. На этом фоне сообщения о постройке той или иной группой машины с одной или двумя сотнями физических кубитов звучат куда менее бравурно — ведь фактически доступное для вычислений на них число логических (за вычетом вспомогательных) элементов оказывается примерно на 0,5—1 десятичный порядок меньше.

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

Предложенная IBM в 2015 г. схема из четырёх кубитов (два основных в запутанном состоянии, два контрольных, занимаемая контуром площадь — 1,6 кв. см) позволяет эффективно выявлять ошибки bit-flip и phase-flip, но не исправлять их (источник: IBM)

При этом — памятуя о существенно ограничивающей время работы системы декогеренции, избежать которой невозможно, — необходимо на крайне ограниченном временнóм отрезке обеспечить точность вычислений на уровне не хуже одной ошибки на миллиард операций. Для чего, по оценке работающей над квантовыми вычислениями в Google физика Мариссы Жюстины (Marissa Giustina), на каждый логический кубит может потребоваться — на нынешнем уровне развития прикладных квантовых технологий — до одной тысячи вспомогательных, реализующих выявление и своевременное (не забываем о растущей со временем угрозе декогеренции!) исправление ошибок. «Говорят, коррекция ошибок — это следующий шаг в квантовых вычислениях. Я бы сказала, что это следующие 25 шагов», — с горькой иронией признаётся исследователь.

⇡#Так есть ли он, реальный прогресс в квантовых вычислениях?

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

127-кубитный квантовый процессор IBM Eagle (2021 г.) полагается для выявления и своевременной коррекции ошибок на новую топологию heavy hex, подразумевающую расположение попарно запутанных основных кубитов в узлах гексагональной решётки, а контрольных — на её гранях (источник: IBM)

Ну и на сладкое: все неурядицы, перечисленные до сих пор, имели отношение к отдельным кубитам, тогда как квантовый компьютер включает, помимо них, и логические элементы — вентили (такие, как упомянутый ранее CNOT). Которые — сюрприз, сюрприз! — тоже подвержены ошибкам. В конце 2021 г. Джон Мартинис (John Martinis), ныне профессор Университета Калифорнии в г. Санта-Барбара, а ранее главный архитектор той самой Sycamore, прямо заявил: «Я думаю, исправление ошибок на квантовых вентилях сегодня куда более важная задача, чем наращивание числа кубитов. В долгосрочной перспективе, если говорить о действительно сложных квантовых вычислениях, следует добиваться снижения уровня ошибок на вентилях до уровня не выше 1%».

Самые передовые квантовые компьютеры наших дней демонстрируют общий уровень логических ошибок (с учётом всех вносящих свой вклад в них узлов и корректирующих схем) порядка 10^–3 — грубо говоря, одна-две ошибки на тысячу операций. Чтобы выйти на тот уровень точности, который демонстрируют полупроводниковые вычислители, построенные на архитектуре фон Неймана, требуется точность не менее 10^–10, а лучше 10^–20. И путь к этому пределу, очевидно, будет долог и труден.

Хотя квантовые вычисления производятся на микроуровне, для обеспечения работы того же 127-кубитного Eagle необходима установка довольно внушительных размеров (источник: IBM)

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