Алгоритм Шора

Для цього модуля Qiskit у класі студенти повинні мати робоче середовище Python із встановленими такими пакетами:

• qiskit v2.1.0 або новіша версія
• qiskit-ibm-runtime v0.40.1 або новіша версія
• qiskit-aer v0.17.0 або новіша версія
• qiskit.visualization
• numpy
• pylatexenc

Щоб налаштувати та встановити зазначені пакети, ознайомся з посібником Встановлення Qiskit. Щоб запускати завдання на реальних квантових комп'ютерах, студентам потрібно створити обліковий запис IBM Quantum®, виконавши кроки з посібника Налаштування облікового запису IBM Cloud.

Цей модуль було протестовано та використано три секунди часу QPU. Це лише оцінка. Фактичне використання може відрізнятися.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Вступ

На початку 1990-х років навколо потенціалу квантових комп'ютерів у розв'язанні задач, важких для класичних комп'ютерів, панувало дедалі більше ентузіазму. Кілька талановитих учених у галузі комп'ютерних наук розробили алгоритми, що демонструвала потужність квантових обчислень для деяких нішевих, штучних задач, але ніхто ще не знайшов «вбивчого застосування» квантових обчислень, яке точно революціонізувало б галузь. Так тривало аж до 1994 року, коли Пітер Шор запропонував те, що нині зветься алгоритмом Шора для факторизації великих чисел.

На той час було добре відомо, що знаходження простих множників великого числа — надзвичайно складне завдання для класичного комп'ютера. Більше того, саме на цій складності ґрунтувалися протоколи інтернет-безпеки. Шор знайшов спосіб знаходити ці множники експоненційно ефективніше, перекладаючи деякі найскладніші кроки на теоретичний майбутній квантовий комп'ютер.

У цьому модулі ми досліджуємо алгоритм Шора. Спочатку ми трохи більше окреслимо контекст алгоритму, формалізуємо задачу, яку він розв'язує, і пояснимо її зв'язок із кібербезпекою. Далі коротко розглянемо модульну арифметику та її застосування до задачі факторизації, покажемо, як факторизація зводиться до іншої задачі — «пошуку порядку». Ми з'ясуємо, яку роль відіграють Квантове перетворення Фур'є та Квантова оцінка фази, вивчені у попередньому модулі, і як їх використати для розв'язання задачі пошуку порядку.

Нарешті, ми запустимо алгоритм Шора на реальному квантовому комп'ютері! Майте на увазі, однак, що цей алгоритм буде по-справжньому корисним лише тоді, коли з'являться великі відмовостійкі квантові комп'ютери — а це ще кілька років попереду. Тож ми просто розкладемо на множники мале число, щоб продемонструвати, як алгоритм працює.

Задача факторизації

Мета задачі факторизації — знайти прості множники числа $N$. Для деяких чисел $N$ це доволі просто. Наприклад, якщо $N$ парне, одним із його простих множників буде 2. Якщо $N$ є степенем простого числа, тобто $N=p^k$ для деякого простого числа $p$, знайти $p$ також нескладно: достатньо наблизити $k$-й корінь із $N$ і пошукати поблизу прості числа, які могли б бути $p$.

Класичні комп'ютери зазнають труднощів, коли $N$ непарне та не є степенем простого числа. Саме цей випадок і розв'язує алгоритм Шора. Алгоритм знаходить два множники $p$ та $q$ такі, що $N=pq$. Його можна застосовувати рекурсивно, поки всі множники не стануть простими. У наступних розділах ми побачимо, як підходити до цієї задачі.

Зв'язок із кібербезпекою

Чимало криптографічних схем побудовано на тому, що факторизація великих чисел є складною задачею, зокрема одна з найпоширеніших сьогодні — RSA. В RSA відкритий ключ створюється множенням двох великих простих чисел, що дає $N = p\cdot q$. Потім будь-хто може використовувати цей відкритий ключ для шифрування даних. Але розшифрувати їх може лише той, хто знає закритий ключ — $p$ та $q$.

Якби $N$ легко факторизувалося, будь-хто міг би визначити $p$ та $q$ і зламати шифрування. Але це не так. Це загальновідомо складна задача. Зокрема, прості множники числа RSA1024 — довжиною 1024 двійкові цифри і 309 десяткових цифр — досі не знайдені, хоча за їхню факторизацію ще з 1991 року пропонується приз у розмірі $100 000.

Рішення Шора

У 1994 році Пітер Шор зрозумів, що квантовий комп'ютер здатний факторизувати велике число експоненційно ефективніше, ніж класичний. Його ідея спиралася на зв'язок між задачею факторизації та модульною арифметикою. Ми коротко розглянемо основи модульної арифметики, а потім побачимо, як її застосувати для факторизації $N$.

Модульна арифметика

Модульна арифметика — це циклічна система підрахунку: лічба починається звичайним чином — цілими числами 0, 1, 2 тощо, — але після деякого «обходу» $N$ знов обнуляється. Розглянемо це на прикладі. Нехай $N = 5$. Тоді там, де в звичайному підрахунку ми дійшли б до 5, ми натомість починаємо знову з 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Це тому, що у світі «за модулем 5» число 5 еквівалентне 0. Кажуть, що $5\bmod 5 \ = 0$. Насправді всі кратні 5 будуть еквівалентні $0\bmod 5$.

Перевір себе

Прочитай питання нижче, подумай над відповіддю, а потім натисни трикутник, щоб побачити розв'язання.

Використай модульну арифметику для розв'язання наступної задачі:

Ти вирушаєш у довгу трансконтинентальну подорож поїздом о 8:00 ранку. Поїздка триває 60 годин. Котра година буде, коли ти прибудеш?

Відповідь:

Модуль дорівнює 24, оскільки в добі 24 години. Тож задачу можна записати у вигляді модульної арифметики:

$(8+60)\text{mod}(24) = 20$

Отже, ти прибудеш до пункту призначення о 20:00.

$\mathbb{Z}_N$ та $\mathbb{Z}_N^*$

Часто зручно ввести два множини: $\mathbb{Z}_N$ та $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ — це просто множина чисел, що існують у світі «за модулем $N$». Наприклад, коли ми рахували за модулем 5, множина мала вигляд $\mathbb{Z}_5=\{0,1,2,3,4\}$. Ще один приклад: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Над елементами $\mathbb{Z}_N$ можна виконувати додавання та множення (за модулем $N$), і результат кожної із цих операцій також є елементом $\mathbb{Z}_N$, що робить $\mathbb{Z}_N$ математичним об'єктом, який називається кільцем.

Для алгоритму Шора особливий інтерес становить підмножина $\mathbb{Z}_N$ — множина чисел із $\mathbb{Z}_N$, для яких найбільший спільний дільник кожного елемента та $N$ дорівнює 1, тобто кожен елемент є «взаємно простим» із $N$. Якщо взяти цю множину разом із операцією модульного множення, отримаємо ще один математичний об'єкт — групу. Цю групу позначають $\mathbb{Z}_N^*$. Виявляється, що в $\mathbb{Z}_N^*$ (і в скінченних групах загалом), якщо взяти будь-який елемент $a \in \mathbb{Z}_N^*$ і послідовно множити $a$ на себе, ми завжди врешті-решт отримаємо число $1$. Мінімальна кількість разів, яку потрібно помножити $a$ на себе, щоб отримати $1$, називається порядком $a$. Цей факт буде дуже важливим для нашого обговорення факторизації чисел нижче.

Перевір себе

Прочитай питання нижче, подумай над відповіддю, а потім натисни трикутник, щоб побачити розв'язання.

Чому дорівнює $\mathbb{Z}_{15}^*$?

Відповідь:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Ми виключили такі числа:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Яким є порядок кожного з елементів у $\mathbb{Z}_{15}^*$?

Відповідь:

Порядок $r$ — це найменше число таке, що $a^r\text{mod}(15)=1$ для кожного елемента $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Зауваж, що хоча нам вдалося знайти порядки чисел у $\mathbb{Z}_{15}^*$, у загальному випадку для більших $N$ це НЕ легке завдання. Саме в цьому суть задачі факторизації і причина, чому нам потрібен квантовий комп'ютер. Ми побачимо чому, коли пройдемо решту ноутбука.

Застосування модульної арифметики до задачі факторизації

Ключ до знаходження множників $p$ та $q$ таких, що $N=pq$, полягає у пошуку деякого іншого цілого числа $x$ такого, що

$x^2 \equiv 1 \bmod N$ та $x \not\equiv \pm 1 \bmod N.$

Як знаходження $x$ допомагає нам знайти множники $p$ та $q$? Розберемо аргумент. Оскільки $x^2 \equiv 1 \bmod N$, це означає, що $x^2 - 1 \equiv 0 \bmod N$. Іншими словами, $x^2 - 1$ є кратним $N$. Отже, для деякого цілого числа $l$:

$x^2 - 1 = l N$

Розкладемо $x^2 - 1$ на множники:

$(x+1)(x-1) = l N$

З початкових умов знаємо, що $x \not\equiv \pm 1 \bmod N$, тож $N$ не ділиться рівно ні на $x+1$, ні на $x-1$. Отже, два множники $N$ — $p$ та $q$ — мають ділити $x-1$ та $x+1$. Або $p$ є множником $x-1$, а $q$ — $x+1$, або навпаки. Тому якщо обчислити найбільші спільні дільники (НСД) між $N$ та обома $x-1$ і $x+1$, це дасть нам множники $p$ та $q$. Обчислення НСД двох чисел — класично проста задача, яку можна розв'язати, наприклад, за допомогою алгоритму Евкліда.

Перевір себе

Прочитай питання нижче, подумай над відповіддю, а потім натисни трикутник, щоб побачити розв'язання.

Кожен крок наведеної вище логіки може бути нелегким для розуміння, тому спробуй пройти через нього на прикладі. Використай $N=15$ та $x=11$. Спочатку перевір, що $x^2 \equiv 1 \text{mod}(N)$ та $x \not\equiv \pm 1 \bmod N$. Потім продовжуй перевіряти кожен крок. Нарешті, обчисли $\text{GCD}(11\pm1,15)$ і переконайся, що ці значення є множниками $15$.

Відповідь:

$11^2 = 121$, що дорівнює $15*8 + 1$, тож $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, що не еквівалентно $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, що не еквівалентно $0\bmod 15$. $\checkmark$

Тепер ми знаємо, що $(x+1)(x-1) = l N$ для деякого цілого числа $l$. Це підтверджується, коли підставляємо $x$ та $N$: $(12)(10) = l 15$ при $l = 8$. $\checkmark$

Тепер потрібно обчислити $\text{GCD}(12,15)$ та $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Отже, ми знайшли множники числа $15$!

Алгоритм

Тепер, коли ми побачили, як знаходження цілого числа $x$ такого, що $x^2 \equiv 1\bmod N$, допомагає факторизувати $N$, можемо розглянути алгоритм Шора. Він, по суті, зводиться до знаходження $x$:

1. Вибери випадкове ціле число Вибери випадкове ціле число $a$ таке, що $1 < a < N$.

• Обчисли $\text{GCD}(a, N)$ класично.
  • Якщо $\text{GCD}(a, N) > 1$, множник уже знайдено. Зупинись.
  • Інакше продовжуй.

2. Знайди порядок $r$ числа $a$ за модулем $N$ Знайди найменше додатне ціле число $r$, що задовольняє $a^r \equiv 1 \pmod N$.

3. Перевір, чи порядок парний

• Якщо $r$ непарне, повернись до кроку 1 і вибери нове $a$.
• Якщо $r$ парне, переходь до кроку 4.

4. Обчисли $x = a^{r/2} \bmod N$

• Перевір, що $x \not\equiv 1 \pmod N$ та $x \not\equiv -1 \pmod N$.
  • Якщо $x \equiv \pm 1 \pmod N$, повернись до кроку 1 і вибери нове $a$.
• Інакше обчисли НСД для отримання множників:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Це будуть нетривіальні множники $N$.

5. Рекурсивно факторизуй за необхідності

• Якщо $p$ та/або $q$ не є простими, рекурсивно застосуй алгоритм для їхньої повної факторизації.
• Як тільки всі множники стануть простими, факторизацію завершено.

Виходячи з цієї процедури, може бути незрозуміло, навіщо для виконання цього завдання потрібен квантовий комп'ютер. Він необхідний тому, що крок 2 — знаходження порядку $a$ за модулем $N$ — є класично дуже складною задачею. Складність масштабується експоненційно відносно числа $N$. Але за допомогою квантового комп'ютера ми можемо скористатися Квантовою оцінкою фази для її розв'язання. Крок 4 — знаходження НСД двох цілих чисел — насправді класично досить просте завдання. Тож єдиним кроком, який дійсно потребує потужності квантового комп'ютера, є крок пошуку порядку. Кажуть, що задача факторизації «зводиться» до задачі пошуку порядку.

Найскладніша частина: пошук порядку

Тепер розглянемо, як можна використати квантовий комп'ютер для пошуку порядку. Спочатку уточнимо, що ми маємо на увазі під «порядком». Звісно, я вже пояснював математичний зміст порядку: це перше ненульове ціле число $r$ таке, що $a^r = 1 \pmod N.$ Але спробуємо набути трохи більше інтуїції щодо цього поняття.

Для достатньо малого $N$ можна просто визначити порядок, послідовно обчислюючи кожний степінь $a$, беручи залишок від ділення на $N$, і зупиняючись, коли знайдено степінь $r$ такий, що $a^r = 1 \text{mod}(N)$. Саме це ми й робили у прикладі $N=15$ вище. Подивімось на графіки цих модульних степенів для кількох значень $a$ та $N$:

Помітив щось? Це — періодичні функції! А порядок $r$ — це той самий період! Отже, пошук порядку еквівалентний пошуку періоду.

Квантові комп'ютери дуже добре підходять для знаходження периоду функцій. Для цього ми можемо використати алгоритмічну підпрограму, що зветься Квантовою оцінкою фази. Ми обговорили QPE та її зв'язок із Квантовим перетворенням Фур'є у попередньому модулі. Для детального повторення зверніться до модуля про QFT або до уроку Джона Ватруса з Квантової оцінки фази у його курсі з квантових алгоритмів. Ось стисло суть процедури:

У Квантовій оцінці фази (QPE) ми починаємо з унітарного оператора $U$ та власного стану цього унітарного $|\psi\rangle$. Потім використовуємо QPE для наближеного обчислення відповідного власного значення, яке, оскільки оператор є унітарним, матиме вигляд $e^{2\pi i \theta}$. Таким чином, знаходження власного значення еквівалентне знаходженню значення $\theta$ у цій периодичній функції. Схема Circuit виглядає так:

де кількість контрольних Qubit (верхні $m$ Qubit на малюнку вище) визначає точність апроксимації.

В алгоритмі Шора ми застосовуємо QPE до унітарного оператора $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Тут $|y\rangle$ позначає базисний стан обчислень багатокубітного регістра, де двійкове значення Qubit відповідає цілому числу $y$. Наприклад, якщо $N=15$ та $y = 2$, то $|y\rangle$ представлено чотирикубітним базисним станом $|0010\rangle$, оскільки чотири Qubit потрібні для кодування чисел до 15. (Якщо ця концепція незнайома, зверніться до вступного модуля Qiskit у класі для повторення двійкового кодування квантових станів.)

Тепер нам потрібно знайти власний стан цього унітарного. Якщо ми починаємо у стані $|1\rangle$, то кожне наступне застосування $U$ множить стан нашого регістра на $a \pmod N$, і після $r$ застосувань ми знову повернемося до стану $|1\rangle$. Наприклад, при $a = 3$ та $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Тож суперпозиції станів із цього циклу ($|\psi_j\rangle$) вигляду:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

є власними станами $M_a$. (Власних станів більше, ніж наведено вище. Але нас цікавлять лише ті, що мають зазначений вигляд.)

Перевір себе

Прочитай питання нижче, подумай над відповіддю, а потім натисни трикутник, щоб побачити розв'язання.

Знайди власний стан унітарного оператора, що відповідає $a=2$ та $N = 15$.

Відповідь:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Отже, порядок $r=4$. Власні стани, що нас цікавлять, будуть рівними суперпозиціями всіх станів, через які пройшов цикл вище, з різними фазами:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Припустімо, що ми змогли ініціалізувати стан нашого Qubit у один із цих власних станів (спойлер — ні, або принаймні не легко. Незабаром пояснимо чому і що натомість можна зробити). Тоді ми могли б використати QPE для оцінки відповідного власного значення $\omega_j = e^{2 \pi i \theta_j}$, де $\theta_j = \frac{j}{r}$. Після цього порядок $r$ можна визначити з простого рівняння:

$r = \frac{j}{\theta_j}.$

Але пам'ятай: QPE оцінює $\theta_j$ — вона не дає точного значення. Нам потрібно, щоб оцінка була достатньо точною для розрізнення між $r$ та $r+1$. Чим більше контрольних Qubit $m$, тим точнішою буде оцінка. У задачах наприкінці уроку тобі запропонують визначити мінімальне $m$, необхідне для факторизації числа $N$.

Тепер нам потрібно вирішити одну проблему. Усе наведене вище пояснення того, як знайти $r$, починається з підготовки власного стану $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Але ми не знаємо, як це зробити, не знаючи заздалегідь $r$. Логіка є замкненою. Нам потрібен спосіб оцінити власне значення без ініціалізації власного стану.

Замість того щоб починати з власного стану $M_a$, ми можемо підготувати початковий стан у вигляді $n$-кубітного стану, що відповідає $|1\rangle$ у двійковому записі (тобто $|000...01\rangle$). Хоча сам цей стан явно не є власним станом $M_a$, він є суперпозицією всіх власних станів $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Перевір себе

Прочитай питання нижче, подумай над відповіддю, а потім натисни трикутник, щоб побачити розв'язання.

Переконайся, що $|1\rangle$ еквівалентне суперпозиції власних станів, знайдених тобою для $N=15$ та $a=2$ у попередньому запитанні для самоперевірки.

Відповідь:

Чотири власні стани мали вигляд:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Тоді:

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Як це допомагає знайти порядок $r$? Оскільки початковий стан є суперпозицією всіх власних станів зазначеного вище вигляду, алгоритм QPE одночасно оцінює кожне із значень $\theta_k$, що відповідають цим власним станам. Тому вимірювання $m$ контрольних Qubit наприкінці дасть наближення до значення $k/r$, де $k \in \{0,1,2,...,r-1\}$ — одне з власних значень, вибране випадковим чином. Якщо повторити цю схему Circuit кілька разів і отримати кілька вибірок із різними значеннями $k$, ми швидко зможемо визначити $r$.

Реалізація у Qiskit

Як ми вже згадували, наше апаратне забезпечення ще не досягло того рівня, де ми могли б факторизувати величезні числа на кшталт RSA1024. Ми просто розкладемо на множники мале число, щоб продемонструвати, як алгоритм працює. Для цього демо ми використаємо спрощену версію коду, представленого в посібнику з алгоритму Шора. Якщо ти хочеш дізнатися більше подробиць, завітай до посібника.

Ми запустимо алгоритм, використовуючи наш стандартний фреймворк для розв'язання квантових задач — фреймворк Qiskit patterns. Він складається з чотирьох кроків:

1. Відображення задачі на квантову схему Circuit
2. Оптимізація схеми Circuit для запуску на квантовому обладнанні
3. Виконання схеми Circuit на квантовому комп'ютері
4. Постобробка вимірювань

1. Відображення

Давай факторизуємо $N=15$, вибравши $a=2$ як взаємно просте ціле число.

Спочатку нам потрібно побудувати схему Circuit, яка реалізує унітарний оператор модульного множення $M_a$. Насправді це найскладніша частина всієї реалізації і може бути дуже обчислювально витратною залежно від підходу. Тут ми трохи схитруємо: ми знаємо, що починаємо зі стану $|1\rangle$, і з попереднього запитання для самоперевірки:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Тому ми побудуємо унітарний оператор, що виконує правильні дії над цими чотирма станами, залишаючи всі інші стани незмінними. Це й є «шахрайство», оскільки ми використовуємо наше знання порядку $2\bmod 15$ для спрощення унітарного. Якби ми справді намагалися факторизувати число, множники якого нам невідомі, ми б не могли цього зробити.

Перевір себе

Прочитай питання нижче, подумай над відповіддю, а потім натисни трикутник, щоб побачити розв'язання.

Знаючи, як оператор $M_2$ перетворює стани вище, побудуй оператор із серії Gate SWAP, що обмінюють стани двох Qubit. (Підказка: запис кожного стану $|i\rangle$ у двійковій формі допоможе.)

Відповідь:

Перепишемо дію $M_2$ на стани у двійковому форматі:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Кожну з цих дій можна виконати простим Gate SWAP. $M_2|0001\rangle$ досягається обміном станів Qubit $0$ та $1$. $M_2|0010\rangle$ — обміном станів Qubit $1$ та $2$. І так далі. Отже, матрицю $M_2$ можна розкласти на таку послідовність Gate SWAP:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Пам'ятаючи, що оператори діють справа наліво, перевіримо, що це дає потрібний ефект для кожного зі станів:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Тепер можна закодувати схему Circuit, еквівалентну цьому оператору, у Qiskit.

Спочатку імпортуємо необхідні пакети:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Потім створимо оператор $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Алгоритм QPE використовує керований Gate-$U$. Тому тепер, коли ми маємо схему Circuit $M_2$, нам потрібно зробити її керованою-$M_2$ схемою Circuit:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Тепер ми маємо наш керований Gate-$U$. Але для запуску алгоритму Квантової оцінки фази нам знадобляться керований-$U^2$, керований-$U^4$ аж до керованого-$U^{2^{m-1}}$, де $m$ — кількість Qubit, що використовуються для оцінки фази. Що більше Qubit, то точнішою буде оцінка фази. Для нашої процедури оцінки фази ми використаємо $m=8$ контрольних Qubit. Отже, нам потрібно:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

де індекс $k$ з $0 \le k \le m-1 = 7$ відповідає контрольному Qubit. Обчислимо $a^{2^k}\bmod N$ для кожного значення $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Оскільки $a^{2^k} \bmod N = 1$ для $k \ge 2$, усі відповідні оператори ($M_8$ і вище) еквівалентні тотожному оператору. Тому нам потрібно побудувати лише ще одну матрицю — $M_4$.

Примітка: Це спрощення працює тут лише тому, що порядок $2 \bmod 15$ дорівнює $4$. Щойно $k=2$ (тобто $2^k = 4$), кожний наступний степінь оператора є тотожним. У загальному випадку для більших $N$ або інших значень $a$ пропустити побудову вищих степенів не вийде. Саме тому це вважається іграшковим прикладом: малі числа допускають скорочення, що не працюватимуть для більших.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

І, як і раніше, зробимо його керованим-$M_4$ оператором:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Тепер можна зібрати все докупи для знаходження порядку $2\bmod 15$ за допомогою квантової схеми Circuit, використовуючи оцінку фази:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Оптимізація

Після того як ми відобразили наш Circuit, наступний крок — оптимізувати його для запуску на конкретному квантовому комп'ютері. Спершу потрібно завантажити Backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Якщо у тебе немає доступного часу на акаунті або ти хочеш з будь-якої причини скористатися симулятором, запусти клітинку нижче, щоб налаштувати симулятор, який відтворюватиме поведінку квантового пристрою, обраного вище:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Виконання

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Ми бачимо чотири чіткі піки при 00000000, 01000000, 10000000 та 11000000, а також певну кількість відліків в інших бітових рядках через шум у квантовому комп'ютері. Ми ігноруватимемо їх і залишимо лише домінуючу четвірку, встановивши поріг: враховуються лише ті відліки, що перевищують цей поріг і є справжнім сигналом над шумом.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Постобробка

В алгоритмі Шора значна частина обчислень виконується класично. Тому решту кроків ми винесемо в «постобробку» — після того як отримаємо результати вимірювань із квантового комп'ютера. Кожен із наведених вище результатів вимірювань можна перетворити на ціле число, яке після ділення на $2^m$ є наближенням для $\frac{k}{r}$, де $k$ — випадкове число щоразу.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Висновок

Пройшовши цей модуль, ти, мабуть, по-новому оціниш геніальність Пітера Шора, якому вдалося придумати такий дотепний алгоритм. Але сподіваємось, ти також досяг нового рівня розуміння його оманливої простоти. Хоча алгоритм може здаватися вражаюче (або лякаюче) складним, якщо розбити його на кожен логічний крок і пройти повільно, ти теж зможеш запустити алгоритм Шора.

Хоча ми ще далекі від використання цього алгоритму для факторизації чисел на кшталт RSA1024, наші квантові комп'ютери стають кращими щодня, і щойно буде досягнуто порогу, який називають відмовостійкістю, такі алгоритми не змусять себе чекати. Зараз — захопливий час для вивчення квантових обчислень!

Завдання

Ключові концепції:

• Сучасні криптографічні системи спираються на класичну складність факторизації великих цілих чисел.
• Модульна арифметика — зокрема структури $\mathbb{Z}_N$ та $\mathbb{Z}_N^*$ — є математичною основою алгоритму Шора.
• Задачу факторизації цілого числа $N$ можна звести до задачі знаходження порядку числа за модулем $N$.
• Квантовий пошук порядку використовує методи квантового оцінювання фази для визначення періоду функції $a^x \mod N$.
• Алгоритм Шора являє собою класично-квантовий гібридний робочий процес, який обирає основу, виконує квантовий пошук порядку, а потім класично обчислює множники з результату.

Правда/Хиба:

1. П/Х Ефективність алгоритму Шора загрожує безпеці RSA-шифрування.
2. П/Х Алгоритм Шора можна ефективно виконати на будь-якому сучасному квантовому комп'ютері.
3. П/Х Алгоритм Шора використовує квантове оцінювання фази (QPE) як ключову підпрограму.
4. П/Х Класична частина алгоритму Шора передбачає обчислення найбільшого спільного дільника (НСД).
5. П/Х Алгоритм Шора працює лише для факторизації парних чисел.
6. П/Х Успішний запуск алгоритму Шора завжди гарантує правильні множники.

Короткі відповіді:

1. Чому алгоритм Шора вважається потенційною майбутньою загрозою для RSA-шифрування?
2. Чому знаходження періоду, або порядку, функції модульного піднесення до степеня допомагає факторизувати число в алгоритмі Шора?

Задачі підвищеної складності:

1. Скільки керуючих Qubit $m$ нам потрібно для заданого числа $N$, яке ми намагаємося факторизувати, щоб отримати точність QPE, необхідну для знаходження правильного значення порядку $r$?