Глубокое погружение в реализацию алгоритма Шора и анализ квантовых вычислений на квантовом оборудовании IBM
Делиться
Алгоритм Шора был предложен Питером Шором в основополагающей статье [1] в 1995 году как алгоритм факторизации больших чисел с использованием квантовых вычислений. В 2025 году, то есть 30 лет спустя, первые квантовые процессоры будут произведены и станут доступны широкой публике, что позволит протестировать алгоритм в реальных условиях. Сможем ли мы успешно запустить алгоритм Шора на больших числах? Ответ, как известно, отрицательный, поскольку для этого потребуются квантовые процессоры с тысячами кубитов и очень низким квантовым шумом, а мы пока не достигли этой цели. Но как насчёт малых чисел? И, кстати, как конкретно реализовать алгоритм Шора?
В этой публикации мы даём руководство по реализации алгоритма Шора, уделяя особое внимание реализации квантовой схемы поиска порядка и модульным арифметическим вычислениям, лежащим в основе алгоритма. Мы прилагаем ссылку на Git-репозиторий с полной реализацией в Qiskit. В заключение мы проводим симуляции и приводим результаты реальных вычислений на квантовом оборудовании IBM по состоянию на 2025 год.
Чтобы понять эту статью, вам будет полезно знать основы квантовых вычислений, а именно манипуляции с кубитами и стандартные операции с унитарными вентилями, а также немного линейной алгебры.
Отказ от ответственности 1: Хотя я стремлюсь к научному уровню строгости, это не академическая работа, и я не претендую на звание эксперта в этой области.
Отказ от ответственности 2: при создании этого поста не использовался искусственный интеллект.
Прорывной алгоритм факторизации чисел
Алгоритм Шора — это алгоритм, целью которого является нахождение нетривиального множителя целого числа N. Хотя для достаточно малого N найти множитель легко, перебирая, например, возможные значения вплоть до N1/2, задача становится невыполнимой при действительно больших N, например, N ~ 21 000, просто потому, что пространство поиска становится слишком большим. Чтобы найти множитель такого большого целого числа с помощью классического компьютера, не хватит всей человеческой жизни.
Если обозначить через n = ⌈log2(N)⌉ количество цифр для записи числа N в двоичной системе счисления, то самый известный классический алгоритм имеет временную сложность exp(c n1/3 (log n)2/3) для некоторой константы c, то есть экспоненциальную временную сложность. Под «классическим» алгоритмом понимается алгоритм, который может быть запущен на традиционном компьютере, а именно алгоритм, состоящий из арифметических операций над числами. К ним относятся практически все алгоритмы, за исключением квантовых.
Алгоритм Шора — квантовый алгоритм, то есть он использует операции над квантовой системой, в данном случае над кубитами. Более того, это вероятностный алгоритм, то есть он гарантированно работает с высокой вероятностью, но иногда может давать сбои.
Алгоритм Шора способен найти множитель N с временной сложностью O(n² log n) с высокой вероятностью в своей наиболее эффективной реализации, то есть с полиномиальной временной сложностью. Это, пожалуй, самый впечатляющий на сегодняшний день пример квантового алгоритма, превосходящего классические алгоритмы.
Более того, задача факторизации больших целых чисел лежит в основе криптографии с открытым ключом и алгоритма RSA, который сегодня широко используется для защиты интернет-коммуникаций. Алгоритм Шора, при успешном запуске на квантовом компьютере с несколькими тысячами кубитов, может взломать эту схему шифрования. Это делает его одним из самых популярных приложений в квантовых вычислениях.
Хотя мы всё ещё далеки от создания квантового компьютера, способного запустить алгоритм Шора на больших числах, текущий прогресс позволяет опробовать его на малых числах. Поэтому пришло время более подробно изучить алгоритм Шора, понять, как он работает, как мы можем реализовать его и запустить на квантовом оборудовании.
Воспользовавшись преимуществами квантовой платформы IBM, которая предоставляет ограниченный бесплатный доступ к реальным квантовым процессорам (QPU), я реализовал полный алгоритм с помощью Qiskit SDK и опробовал его на небольших числах. Полная реализация доступна в этом репозитории qiskit-shor.
Давайте теперь углубимся в алгоритм.
Алгоритм
В интернете можно найти множество описаний алгоритма Шора (например, в Википедии). Мы лишь опишем сам алгоритм и объясним его идеи, но не будем объяснять, как он работает, и не будем приводить доказательство каждого утверждения .
Рассмотрим составное целое число N, то есть целое число, допускающее нетривиальные простые множители. Также потребуем, чтобы N было нечётным и не являлось степенью простого числа (в этих случаях мы легко найдём нетривиальный множитель).
Тогда шаги алгоритма таковы:
- Выбираем случайное целое число 1 < A < N и вычисляем НОД(A, N). Если НОД(A, N) > 1, то НОД(A, N) — нетривиальный делитель числа N, и всё (счастливый случай). В противном случае числа A и N взаимно просты (типичный случай).
- Найдите порядок A в ZN, т.е. наименьшее целое число 1 < r < N такое, что Ar = 1 mod N, используя квантовый алгоритм оценки фазы (см. ниже).
- Если r нечётно, вернуться к шагу 1 и выбрать другое число A. В противном случае вычислить d = НОД(Ar/2 − 1, N). Если d > 1, то d — нетривиальный множитель числа N. В противном случае начать заново с шага 1.
Питер Шор предложил этот алгоритм в основополагающей статье [1] и доказал, что он находит множитель N за полиномиальное время с высокой вероятностью.
Из перечисленных выше шагов только нахождение порядка требует квантовой операции. Остальные шаги — классические операции, которые легко выполняются на классическом компьютере.
Квантовый алгоритм заключается в применении унитарных операций к набору кубитов, представляющих числа в двоичной системе счисления. Целое число
[ x = sum_{i=0}^{m-1} x_i 2^i, quad x_i in {0,1} ,,]
представлено состоянием m-кубита
[ |xrangle = |x_0rangle |x_1rangle …|x_{m-1}rangle ]
Например, число 13 = 20 + 22 + 23 представлено «квантовым целым числом» (4-кубитным состоянием) |13⟩ = |1⟩|0⟩|1⟩|1⟩.
Чтобы найти порядок r целого числа A в ZN, идея алгоритма Шора заключается в использовании того факта, что унитарный оператор
[ U_A : x rightarrow Ax ,, text{mod} ,, N ]
допускает собственные значения вида exp(2πi j/r), где 0 ≤ j < r, и что вектор |1⟩ («квантовое целое число 1») может быть выражен как линейная комбинация соответствующих собственных векторов. Алгоритм пытается оценить хотя бы одну из дробей j/r. Это называется оценкой фазы, поскольку мы оцениваем фазу Φ = 2π j/r собственного значения exp(iΦ) оператора UA.
Мы предоставим фактическую квантовую схему, которую необходимо запустить, в следующем разделе. Квантовый алгоритм заключается в запуске этой схемы и измерении ее m выходных битов, формируя число k в двоичной системе счисления. Это число k таково, что k/2m должно быть близко к j/r для некоторого 0 ≤ j < r с высокой вероятностью. Если только мы не попадем в какой-то неудачный случай (например, j = 0), мы можем извлечь значение r, найдя дробь формы a/b, где b < N, ближайшую к k/2m, и определив r=b (существуют библиотеки, которые делают это эффективно). Обычно схему поиска порядка запускают и измеряют ее результаты много раз, чтобы найти r с очень большой вероятностью. Ожидается, что распределение выходов k/2m должно иметь пики (одинаковой величины) при всех значениях j/r для 0 ≤ j < r.
Все классические операции легко реализовать, и их можно выполнить за время, равное логарифму N, поэтому нам остаётся только позаботиться о реализации и запуске квантовой схемы поиска порядка. Давайте посмотрим, как это выглядит.
Квантовая схема поиска порядка
Схема поиска порядка изображена на следующем рисунке. Для повышения эффективности в схему можно внести несколько изменений, но оставим это на потом.
Существует две группы кубитов: одна группа из n кубитов, инициализированных квантовым целочисленным состоянием |1⟩, то есть |x⟩, где x=1, называемые целевыми кубитами (нижние кубиты на рисунке), и другая группа из 2n кубитов, называемые управляющими кубитами (верхние кубиты на рисунке). Управляющие кубиты инициализируются суперпозицией всех целочисленных состояний с помощью вентилей Адамара,
[ (H|0rangle)^{otimes 2n} = left( frac{|0rangle + |1rangle}{sqrt 2}right)^{otimes 2n} = frac{1}{2^n} sum_{x =0}^{2^{2n}-1} |xrangle ]
и затем используются как управляющие кубиты для унитарных операций UD, действующих на целевые кубиты последовательно,
[
CU_{D}|brangle|xrangle = left{
begin{align}
& |0rangle , |xrangle & text{if $b = 0$} \
& |1rangle , |Dx, text{mod}, Nrangle & text{if $b = 1$}
end{align}
верно.
,,
]
с D, принимающим значения
[ D = A^{2^i} , text{mod} , N ,, quad i = 0, …, 2n-1, ]
Наконец, управляющие кубиты преобразуются с помощью обратного QFT-вентиля и все измеряются (обозначены кружками с буквой «m» на рисунке).
Можно заменить число управляющих кубитов 2n на другое число управляющих кубитов m. Чем больше управляющих кубитов, тем точнее будет оценка фазы k/2m оператора UA. Выбор m=2n является компромиссом между точностью и размером схемы.
Почему эта схема выполняет оценку фазы, обсуждается во многих введениях в алгоритм Шора. Лекция в IBM — отличное место для изучения этой темы.
В приведённой выше схеме все компоненты легко реализуются в Qiskit SDK, за исключением унитарного оператора UA (и его управляемой версии CUA). Именно здесь и кроется вся сложность. Большая часть академических исследований алгоритма Шора сосредоточена на оптимизации реализации UA. Представленное выше изображение схемы поиска порядка предполагает, что 3n кубитов достаточно для реализации квантового алгоритма, но сам вентиль UA фактически требует n + c дополнительных кубитов, называемых вспомогательными или служебными кубитами (точная константа c зависит от выбранной реализации).
Прежде чем обсуждать схемную реализацию UA, отметим, что существует важное упрощение вышеприведённой схемы. 2n управляющих кубитов можно заменить одним кубитом (!), который проходит серию унитарных вентильных операций, измерений и сброса, что приводит к значительному сокращению количества кубитов, необходимых для работы алгоритма Шора, но ценой введения операций потока управления, а именно, действий вентилей, зависящих от промежуточных измерений. Хотя в теории это может показаться недорогой ценой, на практике вентили потока управления сложнее в эксплуатации, чем стандартные унитарные операции. Схема «один управляющий кубит» представлена на следующем рисунке.
где mi ∈ {0, 1} — последовательные значения измерений уникального управляющего кубита, а Xm — вентиль X (= вентиль НЕ), если m = 1, или вентиль тождественности, если m = 0. Применение Xm сбрасывает управляющий кубит в состояние |0⟩. Ri — фазовые вентили (= вентили вращения RZ), фазовые параметры которых зависят от всех предыдущих значений измерений. Подробности и пояснения к этому упрощению можно найти, например, в [3].
UA-вентиль и квантовая модульная арифметика
Примечание: Этот раздел более технический. Некоторые читатели могут пропустить его при первом прочтении и сразу перейти к следующему.
Давайте теперь сосредоточимся на схеме, реализующей унитарное действие.
[ U_A : x rightarrow Ax ,, text{mod} ,, N ]
Внимательный читатель может спросить, действительно ли это унитарная операция, поскольку она не выглядит биективной из-за операции по модулю N. Это весьма важный момент, поскольку, используя только унитарные гейты, мы можем реализовать только унитарные операции. Дело в том, что UA, действующая на пространстве целых чисел в [0, N), является биективной функцией тогда и только тогда, когда A и N — взаимно простые целые числа, что верно для значений, рассматриваемых в алгоритме Шора. Обратная операция — это UB, где B — инверсия A в ZN, то есть B — целое число, такое что BA = 1 mod N. Тот факт, что A и N взаимно просты, гарантирует существование B.
Таким образом, теоретически возможно построить унитарный оператор UA, действующий в пространстве S, натянутом на векторы |x⟩, где 0 ≤ x < N. В схеме поиска порядка последовательность (контролируемых) операций UD с различными значениями D применяется к начальному состоянию |1⟩, которое принадлежит S. Действие UA на состояния |x⟩, где x ≥ N, не имеет значения, поскольку этот случай не реализуется. Мы можем игнорировать то, как наша схема вентиля UA действует на эти большие целочисленные состояния.
Чтобы сделать презентацию достаточно краткой, мы рассмотрим только наиболее важные особенности внедрения UA, оставив заинтересованному читателю несколько ссылок на соответствующие статьи.
Важным строительным блоком, который необходимо реализовать, является модульное дополнение:
[ text{add}(Y,N): quad |xrangle rightarrow |(x+Y) , text{mod} , N rangle ]
где 0 ≤ Y < N — «классическое» целое число, т.е. заданный параметр, а 0 ≤ x < N — «квантовое» целое число, т.е. целое число, представленное квантовым состоянием |x⟩, как описано в предыдущих разделах. Для реализации этой операции нам потребуется как минимум n = ⌈log2(N)⌉ кубитов для представления квантовых целых чисел по модулю N, поэтому мы будем считать, что n — это размер квантового регистра, с которым мы работаем, т.е. количество кубитов, хранящих x. Это означает, что мы можем представлять квантовые целые числа в диапазоне от 0 до 2n-1.
Существуют две «школы мысли» для реализации этой операции. Подход «Клиффорд+T» использует только вентили НЕ, H, S, S-1, CNOT и Тоффоли, тогда как подход «Квантовое преобразование Фурье» (QFT) выполняет сложение через параметризованные фазовые вентили P(λ) над представлением входного целого числа в пространстве Фурье (подробнее об этом ниже).
Подход Клиффорда+T, по сути, использует довольно простую «школьную» процедуру сложения битов двух квантовых чисел, записанных в двоичной системе счисления, и отслеживания единиц переноса во вспомогательных кубитах. В реализации [6] вся процедура требует около 10n вентилей и одного вспомогательного кубита, а её глубина составляет примерно 2n (эти понятия обсуждаются в разделе, посвящённом сложности алгоритма, ниже). Этот подход можно адаптировать для сложения классического и квантового чисел.
Подход квантовой теории поля (КТП) был предложен в работе Дрейпера [4]. Он начинается с воздействия на |x⟩ с помощью КТП-вентиля, состоящего из вентилей H и P(π/2j), что приводит к суперпозиции состояний
[ QFT|xrangle = frac{1}{2^{n/2}} sum_{y=0}^{2^n-1} e^{2ipi frac{xy}{2^n}} |yrangle ]
В этом представлении добавление классического числа Y может быть реализовано с помощью n вентилей поворота фазы, действующих на n кубитов регистра
[ prod_{i=0}^{n-1} Pleft(2pi Yfrac{2^i}{2^n}right) QFT|xrangle = QFT|(x + Y) , text{mod} , 2^n rangle ]
Таким образом, стратегия заключается в том, чтобы вставить фазовые повороты между QFT и QFT-1 для реализации добавления
[ |(x + Y), text{mod}, 2^n rangle = QFT^{-1} prod_{i=0}^{n-1} Pleft(2pi Yfrac{2^i}{2^n}right) QFT |xrangle ]
Реализация управляемого сложения достигается путем замены фазовых вентилей на управляемые фазовые вентили.
Хотя число элементарных вентилей в операциях QFT и QFT-1 велико, фактически O(n2), последующее сложение в пространстве Фурье требует всего n фазовых вентилей, которые могут работать параллельно. Несколько сложений, или управляемых сложений, могут быть реализованы последовательно в ходе выполнения квантовой схемы, в то время как квантовое целое число x представляется в пространстве Фурье посредством последовательности (управляемых) фазовых поворотов. Более того, весь вентиль QFT-сумматора не требует вспомогательных кубитов. Это делает подход QFT предпочтительным выбором во многих проектах, требующих квантовых сумматоров.
Недавний обзор С. Вана и др. [5] сравнивает различные современные алгоритмы квантовой арифметики и предоставляет обширную библиографию по этой теме.
Важно отметить, что описанная выше операция сложения всегда выполняется по модулю 2n . Это ожидаемо, поскольку мы можем представлять целые числа только в диапазоне [0, 2n) с помощью n кубитов. Таким образом, реализованная на данный момент операция выглядит следующим образом:
[ text{add}(Y): quad |xrangle_n rightarrow |x+Yrangle_n := |(x + Y), text{mod}, 2^n rangle_n ]
где индекс n указывает количество кубитов в квантовом регистре.
Следующий шаг — реализация части «по модулю N». Это значительно сложнее и требует серии (контролируемых) сложений и (контролируемых) вычитаний. Основные идеи описаны в работе Борегара [2].
Шаги, предложенные Борегаром, при 0 ≤ Y < N и 0 ≤ x < N, следующие:
- При n = ⌈log2(N)⌉ рассмотрим состояние кубита n+1 |x⟩n+1. Это на один кубит больше, чем необходимо для хранения x, то есть имеется один кубит «переполнения», инициализированный значением |0⟩.
- Складываем YN, используя операцию add(YN). Получаем |x+YN⟩n+1, если x+YN≥0, или |2n+1-x+N)⟩, если x+YN < 0.
- Вычислить знак x+YN во вспомогательном кубите |a⟩. Это делается с помощью вентиля CNOT, действующего на |a⟩ и управляемого старшим битом (то есть битом переполнения) регистра из n+1 кубитов. После этого шага |a⟩ = |0⟩, если x+Y ≥ N, и |a⟩ = |1⟩, если x+Y < N.
- Добавляем N обратно в регистр размером n+1 кубит, управляемый по |a⟩, используя управляемую операцию add(N). Результирующее состояние: |(x + Y) mod N⟩|a⟩.
Следующие шаги позволяют сбросить вспомогательный кубит в исходное состояние |0⟩:
- Добавьте -Y с помощью операции add(-Y). После этого шага регистр n+1 находится в состоянии |x⟩, если x + Y < N, или в состоянии |2n+1+xN)⟩, если x + Y ≥ N.
- Инвертируем вспомогательный бит, управляемый старшим битом n+1-кубитного регистра, с помощью вентиля CNOT. После этого шага вспомогательный бит всегда находится в состоянии |a⟩ = |1⟩. Мы сбрасываем его в |0⟩, используя вентиль НЕ: |a⟩ = НЕ|1⟩ = |0⟩.
- Добавляем Y обратно с помощью операции add(Y). Это приводит к конечному состоянию |(x + Y) mod N⟩|0⟩.
Это может показаться немного сложным, но это, пожалуй, самый простой из найденных на сегодняшний день квантовых алгоритмов для выполнения модульного сложения.
Последние три шага, возвращающие вспомогательный кубит |a⟩ в исходное состояние |0⟩, важны, если вспомогательный кубит планируется повторно использовать в последующих операциях модульного сложения, как это происходит в алгоритме Шора. В качестве альтернативы, можно использовать новые вспомогательные кубиты для каждого модульного сложения, уменьшая глубину и количество вентилей полной схемы поиска порядка за счёт увеличения количества кубитов. Минимизация количества кубитов обычно является основной целью, поскольку современные квантовые процессоры имеют ограниченное количество кубитов (подробнее об этом ниже).
Реализация контролируемого модульного сложения достигается путем замены каждого сложения/вычитания множителя Y контролируемым сложением/вычитанием.
Следующий шаг – реализация операции.
[ |xrangle |yrangle -> |xrangle|(y+Ax) ,text{mod}, Nrangle ]
где 0 ≤ y < N — ещё одно квантовое целое число. Это достигается путём разложения модульного сложения y ↦ (y + Ax) mod N в последовательность модульных сложений y ↦ (y + 2iA) mod N, реализуемую как add(2iA, N)|y⟩ = |(y + 2iA) mod N⟩, управляемую i-м битом |xi⟩ числа x = Σi xi 2i. Как мы видели, модульное сложение требует кубита переполнения и вспомогательного кубита, поэтому истинная операция, которую мы реализуем с помощью этого рецепта, выглядит так:
[ V_A: |xrangle_n |yrangle_{n+1} |0rangle rightarrow |xrangle_n |(y+Ax) , text{mod}, Nrangle_{n+1} |0rangle ]
с нижними индексами, указывающими количество кубитов.
Наконец, операция UA реализуется с помощью
[
begin{align}
U_A , : quad
|xrangle_n |0rangle_{n+1} |0rangle &rightarrow |xrangle_n |Ax,text{mod}, Nrangle_{n+1} |0rangle \
&rightarrow |Ax,text{mod}, Nrangle_n |xrangle_{n+1} |0rangle \
&rightarrow |Ax,text{mod}, Nrangle_n |0rangle_{n+1} |0rangle
end{align}
]
Первый шаг — операция VA. Второй шаг использует вентили SWAP для обмена двумя наборами из n кубитов. Обратите внимание, что кубит переполнения среднего состояния не переставляется (на этом этапе он находится в состоянии |0>). Третий шаг — операция VB с B = A-1, обратным к A в ZN, с использованием того факта, что (x – BAx) mod N = (x – x) mod N = 0. Это первое и единственное место, где используется условие взаимной простоты A и N (иначе B не существует).
Подсчитав количество используемых кубитов, мы видим, что для полной операции UA требуется 2n+2 кубитов.
Квантовый анализ сложности
«Сложность» квантового алгоритма обычно выражается тремя величинами: числом используемых кубитов, числом используемых вентилей и глубиной схемы.
Количество используемых кубитов — понятие чёткое. Это важно, поскольку квантовые процессоры всё ещё имеют ограниченное число кубитов для работы (обычно исчисляемое сотнями по состоянию на 2025 год).
Количество вентилей — более расплывчатое понятие, часто относящееся к числу однокубитных и двухкубитных вентилей, таких как H, NOT, P, SWAP, CNOT. Это может быть обманчивым, поскольку физическая реализация этих вентилей может потребовать нескольких «физических» вентилей, представляющих операции над кубитами, реализованные на аппаратном уровне. Обычно двухкубитные вентили, такие как SWAP и CNOT, между удалёнными кубитами требуют цепочки физических двухкубитных вентилей, действующих на соседние кубиты. Количество физических вентилей зависит от «связности» квантовых процессоров, а именно от того, какие двухкубитные операции разрешены физически. Они соответствуют операциям над соседними кубитами. Даже однокубитные вентили, такие как вентиль Адамара, могут потребовать нескольких физических однокубитных вентилей.
Поскольку набор физических вентилей и возможности подключения оборудования различаются у разных поставщиков, большая часть академических исследований просто фокусируется на подсчете количества «базовых» однокубитных и двухкубитных вентилей.
Глубина квантовой схемы определяется количеством последовательных операций над кубитами, необходимых для достижения конечного этапа измерения. Чем больше параллельных операций над кубитами, тем меньше глубина. Глубину можно приблизительно представить как длину схемы в графическом представлении. Важно минимизировать глубину квантовой схемы, поскольку квантовая когерентность кубитов уменьшается с увеличением глубины. Чем больше последовательных операций, тем больше времени требуется для работы схемы до измерения её результатов и тем больше времени требуется кубитам для взаимодействия с окружающей средой и потери когерентности.
Если взглянуть на нашу реализацию UA, то мы увидим, что она требует (как минимум) 2n+2 кубитов. Количество используемых вентилей равно O(n3) (множитель n2 достигается за счёт использования вентиля QFT), а глубина равна O(n2) (множитель n достигается за счёт использования вентиля QFT).
Полная схема нахождения порядка требует еще одного вспомогательного кубита, если мы используем упрощение с 1 управляющим кубитом, и выполняет O(n) последовательных операций UA, поэтому общее количество требуемых кубитов составляет 2n+3 (4n+2, если мы используем схему с 2n управляющими кубитами), общее количество вентилей составляет O(n4), а глубина составляет O(n3).
Существует ещё одно стандартное упрощение: использовать приближённое преобразование QFT, использующее всего O(n log n) вентилей вместо O(n2). Это делает оценку дроби поиска порядка k/22n немного менее точной, но всё ещё достаточной для запуска алгоритма Шора с высокой вероятностью успеха. Это снижает количество вентилей до O(n3 log n).
Во многих исследовательских работах были представлены небольшие улучшения этих показателей, но, насколько мне известно, серьезных прорывов не произошло.
В целом стоимость выполнения алгоритма, как с точки зрения числа кубитов, так и числа операций, полиномиальна по n, что и было обещано алгоритмом Шора, демонстрирующим квантовое преимущество в задаче разложения на множители для очень больших целых чисел N.
Моделирование и запуск на квантовом оборудовании IBM
До сих пор всё, что мы обсуждали, было теоретическим и было известно ещё 20 лет назад. Сегодня несколько компаний пытаются разработать квантовые процессоры, которые в принципе могли бы поддерживать алгоритм Шора. В частности, платформа IBM Quantum Platform предлагает возможность бесплатного выполнения ограниченного числа квантовых вычислений на квантовых процессорах (QPU) с 128 кубитами.
Пакет Qiskit SDK предоставляет удобный интерфейс для реализации квантовых схем, моделирования и запуска схем на квантовом оборудовании IBM. Эта обучающая платформа предлагает вводную информацию о Qiskit для новичков.
$ pip install qiskit qiskit-ibm-runtime qiskit-aer qiskit[визуализация]
Для запуска алгоритма Шора мы используем библиотеку с открытым исходным кодом qiskit-shor, реализованную автором этой статьи. Любого читателя, интересующегося точной реализацией, мы приглашаем ознакомиться с репозиторием по ссылке.
API qiskit-shor имеет две функции: find_order(A, N), которая запускает схему поиска порядка и возвращает порядок r для A в ZN вместе с распределением измеренных выходных данных, и find_factor(N), которая полностью запускает алгоритм Шора и возвращает фактор N, если он был найден.
Чтобы повысить шансы на успех, мы запускаем схему поиска порядка много раз, от 100 до 1000 раз, и наблюдаем распределение измеренных выходных данных. Из этого распределения мы выбираем 10 наиболее часто встречающихся значений, чтобы попытаться извлечь порядок.
Библиотека реализует как схему поиска порядка с 2n управляющими кубитами, так и оптимизированную версию с одним управляющим кубитом. Однако мы в основном используем менее оптимальную версию с 2n управляющими кубитами, поскольку платформа IBM имеет более строгие ограничения на использование схем, использующих операции потока управления.
Симуляции
После клонирования репозитория qiskit-shor мы можем начать симуляции с помощью симулятора Qiskit Aer. Мы запускаем симуляции без шума для тестирования кода. Мы будем работать только с небольшими целыми числами, поскольку моделирование квантового состояния множества кубитов на классическом компьютере требует больших вычислительных затрат, и мы хотим лишь проиллюстрировать вышеизложенное на простых примерах.
из qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager из qiskit.visualization import plot_distribution из qiskit_aer import AerSimulator из qiskit_aer.primitives import SamplerV2 as AerSampler из qiskit_shor.shor import find_order aer_sim = AerSimulator() pm = generate_preset_pass_manager(backend=aer_sim, optimize_level=1) sampler = AerSampler() # Находим порядок 7 в Z_15. r, dist = find_order(A=7, N=15, sampler=sampler, pass_manager=pm, num_shots=100) plot_distribution(dist) Начинаем поиск порядка 7 в Z_15 Найдено значение 4 для порядка 7 в Z_15.
Функция возвращает порядок 4, что является правильным, 74 = 1 mod 15. Выходное распределение показывает четыре значения для возвращенного целого числа k: 00000000, 01000000, 1000000, 11000000, что соответствует двоичной записи целых чисел 0, 26, 27 и 26+27 соответственно. Выходные данные содержат 2n=8 кубитов, при этом n=⌈log2(15)⌉=4. Распределение приближенных дробей k/28 имеет значения 0, 1/4, 1/2, 3/4 с похожим количеством вхождений. Они соответствуют ожидаемым оценкам фаз j/4, j=0, 1, 2, 3, оператора U7. Общий знаменатель 4 этих дробей дает нам порядок 7 в Z15.
Давайте рассмотрим второй пример и найдем порядок 5 в Z21.
r, dist = find_order(A=5, N=21, sampler=sampler, pass_manager=pm, num_shots=500) plot_distribution(dist) Начать поиск порядка 5 в Z_21 Найдено значение 6 для порядка 5 в Z_21.
Квантовый поиск возвращает правильное значение 6. Распределение выходных данных содержит больше результатов и, что важно, демонстрирует несколько пиков. Заменив метки ячеек гистограммы соответствующими дробями k/210 (округленными до 4 знаков после запятой), гистограмма становится
Мы видим пики в точках 0, 1/6, 1/3, 1/2, 2/3 и 5/6, которые представляют собой значения вида j/6, j = 0, 1, 2, 3, 4, 5 (пики на рисунке расположены неравномерно из-за отбрасывания интервалов с нулевыми результатами). Значения j/6 соответствуют собственным значениям унитарного оператора U5, причём 6 соответствует порядку 5 в Z21, как и ожидалось.
Мы можем смоделировать полный алгоритм для полноты и извлечь нетривиальные множители для N=15 и N=21. Следующий код запускает алгоритм Шора с максимум тремя пробными значениями для A, останавливаясь при обнаружении множителя N. Каждая проба заключается в 100-кратном запуске схемы поиска порядка.
из qiskit_shor.shor import find_factor f = find_factor( N=15, sampler=sampler, pass_manager=pm, num_tries=3, num_shots_per_trial=100 ) Начать поиск порядка 4 в Z_15 Найдено значение 2 для порядка 4 в Z_15 Найденный фактор: 3
Значение A=4 было выбрано случайным образом, затем был найден порядок 2, и, наконец, был возвращен фактор 3 числа N=15.
f = find_factor( N=21, sampler=sampler, pass_manager=pm, num_tries=3, num_shots_per_trial=100 ) Начать поиск порядка 17 в Z_21 Найдено значение 6 для порядка 17 в Z_21 Начать поиск порядка 19 в Z_21 Найдено значение 6 для порядка 19 в Z_21 Найденный фактор: 3
Сначала было опробовано значение A=17, что дало порядок 6, но НОД(Ar/2 – 1, N) = НОД(4912, 21) = 1, поэтому это не даёт множителя 21. Следующим было опробовано значение 19, что снова дало порядок 6. На этот раз НОД(Ar/2 – 1, N) = НОД(6858, 21) = 3, что дало множитель 3 для 21.
Квантовые пробеги
Теперь, когда мы убедились, что схема поиска порядка реализована правильно, мы можем попробовать запустить ее на реальных квантовых процессорах.
from qiskit_ibm_runtime import QiskitRuntimeService from qiskit_ibm_runtime import SamplerV2 as Sampler # Для запуска необходимо настроить учётную запись IBM Cloud и сгенерировать # токен API. См. https://cloud.ibm.com # Загрузка сохранённых учётных данных по умолчанию service = QiskitRuntimeService() backend = service.least_busy(operational=True, simulator=False, min_num_qubits=127) print(f»backend: {backend.name}») pm = generate_preset_pass_manager(target=backend.target, optimize_level=1) sampler = Sampler(mode=backend) backend: ibm_brisbane
Давайте теперь попробуем найти порядок 7 в Z15, как в моделировании выше.
r, dist = find_order(A=7, N=15, sampler=sampler, pass_manager=pm, num_shots=1000) plot_distribution(dist) Начать поиск порядка 7 в Z_15 Найдено значение 4 для порядка 7 в Z_15
Возвращается правильный порядок 4 из 7 в Z15, но распределение результатов далеко от того, что было в моделировании, где наблюдалось всего 4 значения. Здесь представлены почти все значения от 0 до 28-1, что делает график довольно нечитаемым. Есть несколько небольших пиков, но результат в основном зашумлён. Удивительно, что из 10 наиболее частых значений алгоритму удаётся извлечь правильный порядок.
Другие прогоны с другими значениями A, N=15 или N=21, дают схожие зашумлённые данные. Это связано с тем, что квантовое оборудование подвержено квантовому шуму, мешающему операциям с унитарными вентилями. Чем больше вентилей, тем больше шума. В схеме поиска порядка при N=15 наша реализация уже содержит 2482 вентиля. Это слишком много для текущих возможностей квантовых вычислений.
из qiskit_shor.shor import order_finding_circuit qc = order_finding_circuit(A=7, N=15) print(f»Количество кубитов: {qc.num_qubits}») # 4n+2 кубитов, где n = ceil(log2(N)) = 4 print(f»Количество вентилей: {qc.size()}») print(f»Глубина схемы: {qc.thought()}») Количество кубитов: 18 Количество вентилей: 2482 Глубина схемы: 1632
Мы можем попробовать случай с меньшим количеством кубитов, выполнив поиск порядка 5 в Z6, используя оптимизированную схему с одним управляющим кубитом.
из qiskit_shor.shor import order_finding_circuit_one_control qc = order_finding_circuit_one_control(A=5, N=6) print(f»Количество кубитов: {qc.num_qubits}») # 2n+3 кубитов, где n = ceil(log2(N)) = 3 print(f»Количество вентилей: {qc.size()}») print(f»Глубина схемы: {qc.thought()}») Количество кубитов: 9 Количество вентилей: 1246 Глубина схемы: 861 r, dist = find_order(A=5, N=6, sampler=sampler, pass_manager=pm, num_shots=1000, one_control_circuit=True) plot_distribution(dist) Начинаем поиск порядка 5 в Z_6 Найдено значение 2 для порядка 5 в Z_6
Возвращается правильный порядок 2, но в распределении по-прежнему доминирует квантовый шум.
Заключительные мысли
Мы представили практически полную презентацию реализации алгоритма Шора, включая довольно подробное описание используемых операций квантовой модульной арифметики. Используя реализацию модуля qiskit-shor, мы провели ряд симуляций и реальных квантовых вычислений на платформе IBM Quantum. Квантовые вычисления оказались подвержены влиянию квантового шума, что на данный момент делает невозможным запуск алгоритма Шора и получение значимых результатов.
Использованная нами реализация была наивной в том смысле, что не включала в себя передовые методы оптимизации. Однако наблюдаемые шумовые результаты этой наивной реализации при запуске алгоритма Шора для очень малых значений N указывают на то, что аналогичные результаты были бы получены даже при дополнительной оптимизации схемы.
В будущем успешное применение алгоритма Шора может стать более реалистичным. Огромный прогресс в области квантового оборудования за последние годы даёт нам надежду увидеть это через несколько лет.
Ссылки
[1] Оригинальная статья: Шор, П. В. (1999). Полиномиальные алгоритмы разложения на простые множители и дискретного логарифмирования на квантовом компьютере. Обзор SIAM, 41(2), 303-332.
[2] С. Борегард, Схема для алгоритма Шора с использованием 2n+ 3 кубитов. arxiv: quant-ph/0205095.
[3] Паркер, С. и Пленио, М.Б. (2000). Эффективная факторизация с одним чистым кубитом и log N смешанных кубитов. Physical Review Letters, 85(14), 3049. arxiv: quant-ph/0001066.
[4] Т. Дрейпер, Сложение на квантовом компьютере, препринт arxiv: quant-ph/0008033
[5] С. Ван и др., Комплексное исследование квантовых арифметических схем, arxiv: quant-ph/2406.03867.
[6] С. Куккаро и др., Новая квантовая схема сложения пульсирующего переноса, arxiv: quant-ph/0410184.
Источник: towardsdatascience.com
