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

Тепер звернімо увагу на задачу факторизації цілих чисел і подивимося, як її можна ефективно розв'язати на квантовому комп'ютері за допомогою оцінки фази. Алгоритм, який ми отримаємо, — це алгоритм Шора для факторизації цілих чисел. Шор не описував свій алгоритм саме в термінах оцінки фази, але це природний та інтуїтивний спосіб пояснити, як він працює.

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

Задача знаходження порядку

Деякі основи теорії чисел

Щоб пояснити задачу знаходження порядку та те, як її можна розв'язати за допомогою оцінки фази, корисно почати з кількох базових понять теорії чисел і попутно ввести зручні позначення.

Для початку: для будь-якого заданого натурального числа $N$ визначимо множину $\mathbb{Z}_N$ таким чином.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Наприклад, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ і так далі.

Це множини чисел, але можна розглядати їх ширше. Зокрема, можна думати про арифметичні операції над $\mathbb{Z}_N$, такі як додавання та множення — і якщо ми домовимося завжди брати результати за модулем $N$ (тобто ділити на $N$ і брати залишок як результат), ми завжди залишатимемося в цій множині під час виконання цих операцій. Дві конкретні операції — додавання та множення, обидві за модулем $N$, — перетворюють $\mathbb{Z}_N$ на кільце, яке є фундаментально важливим типом об'єкта в алгебрі.

Наприклад, $3$ і $5$ — елементи $\mathbb{Z}_7$, і якщо ми перемножимо їх, отримаємо $3\cdot 5 = 15$, що дає залишок $1$ при діленні на $7.$ Іноді це записують так.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Але можна також просто писати $3 \cdot 5 = 1$, якщо зрозуміло, що ми працюємо в $\mathbb{Z}_7$, — щоб позначення були якомога простішими.

Як приклад, ось таблиці додавання та множення для $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Серед $N$ елементів $\mathbb{Z}_N$ особливими є елементи $a\in\mathbb{Z}_N$, що задовольняють $\gcd(a,N) = 1.$ Множину, що містить ці елементи, часто позначають зірочкою ось так.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

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

Як перший приклад, розглянемо $N=6.$ Маємо $5\in\mathbb{Z}_6^{\ast}$, бо $\gcd(5,6) = 1$, і якщо перемножити $5$ на себе, отримаємо $1,$ що підтверджує таблиця вище.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Як другий приклад, розглянемо $N = 21.$ Якщо перебрати числа від $0$ до $20$, ті з них, що мають НСД рівний $1$ з $21$, такі.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Для кожного з цих елементів можна піднести це число до деякого натурального степеня й отримати $1.$ Ось найменші степені, для яких це виконується:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Звичайно, ми працюємо в $\mathbb{Z}_{21}$ для всіх цих рівнянь, що ми не стали вказувати — це вважається неявним, щоб не захаращувати запис. Так само будемо робити і далі впродовж усього уроку.

Формулювання задачі та зв'язок з оцінкою фази

Тепер можна сформулювати задачу знаходження порядку.

Знаходження порядку

Вхід: натуральні числа $N$ і $a$, що задовольняють $\gcd(N,a) = 1$
Вихід: найменше натуральне число $r$ таке, що $a^r \equiv 1$ $(\textrm{mod } N)$

Інакше кажучи, у термінах щойно введених позначень, нам дано $a \in \mathbb{Z}_N^{\ast}$ і ми шукаємо найменше натуральне число $r$ таке, що $a^r = 1.$ Це число $r$ називається порядком $a$ за модулем $N.$

Щоб пов'язати задачу знаходження порядку з оцінкою фази, подумаймо про операцію, визначену на системі, класичні стани якої відповідають $\mathbb{Z}_N$, де ми множимо на фіксований елемент $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

Для ясності: ми виконуємо множення в $\mathbb{Z}_N$, тому неявно мається на увазі, що ми беремо добуток за модулем $N$ всередині кета у правій частині рівняння.

Наприклад, якщо взяти $N = 15$ і $a=2$, то дія $M_2$ на стандартний базис $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ така.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Це унітарна операція за умови $\gcd(a,N)=1$; вона переставляє елементи стандартного базису $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$, тому як матриця є матрицею перестановки. З її визначення очевидно, що ця операція детермінована, а простий спосіб переконатися в її оборотності — подумати про порядок $r$ елемента $a$ за модулем $N$ і помітити, що обернена до $M_a$ — це $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Є ще один спосіб думати про обернену операцію, що не потребує знання $r$ (яке, зрештою, і є тим, що ми намагаємося обчислити). Для кожного елемента $a\in\mathbb{Z}_N^{\ast}$ завжди існує єдиний елемент $b\in\mathbb{Z}_N^{\ast}$, що задовольняє $ab=1.$ Цей елемент $b$ позначаємо $a^{-1}$, і він обчислюється ефективно; розширення алгоритму Евкліда для НСД робить це з вартістю, квадратичною відносно $\operatorname{lg}(N).$ Отже,

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Таким чином, операція $M_a$ є і детермінованою, і оборотною. Це означає, що вона описується матрицею перестановки і тому є унітарною.

Тепер подумаймо про власні вектори та власні значення операції $M_a$, припускаючи, що $a\in\mathbb{Z}_N^{\ast}.$ Як щойно було доведено, це припущення говорить нам, що $M_a$ унітарна.

Операція $M_a$ має $N$ власних значень, можливо, включаючи одне й те саме власне значення, повторене кілька разів, і загалом є певна свобода у виборі відповідних власних векторів — але нам не потрібно переймалися всіма можливостями. Почнімо просто і визначимо лише один власний вектор $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Число $r$ — це порядок $a$ за модулем $N$, тут і далі в цьому уроці. Власне значення, відповідне цьому власному вектору, дорівнює $1$, оскільки він не змінюється при множенні на $a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Це відбувається тому, що $a^r = 1$, тому кожен стан стандартного базису $\vert a^k \rangle$ переходить у $\vert a^{k+1} \rangle$ при $k\leq r-1$, а $\vert a^{r-1} \rangle$ повертається назад у $\vert 1\rangle.$ Образно кажучи, це ніби ми повільно перемішуємо $\vert \psi_0 \rangle$, але він уже повністю перемішаний, тому нічого не змінюється.

Ось ще один приклад власного вектора $M_a.$ Цей є більш цікавим у контексті знаходження порядку та оцінки фази.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Альтернативно, цей вектор можна записати за допомогою суми ось так.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Тут ми бачимо, як комплексне число $\omega_r = e^{2\pi i/r}$ виникає природним чином завдяки тому, як множення на $a$ працює за модулем $N.$ Цього разу відповідне власне значення дорівнює $\omega_r.$ Щоб переконатися в цьому, спочатку обчислимо таке.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Потім, оскільки $\omega_r^{-r} = 1 = \omega_r^0$ і $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$, бачимо, що

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

отже $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Використовуючи ті самі міркування, можна знайти додаткові пари власний вектор/власне значення для $M_a.$ Для будь-якого вибору $j\in\{0,\ldots,r-1\}$ маємо, що

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

є власним вектором $M_a$, відповідне власне значення якого дорівнює $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

У $M_a$ є й інші власні вектори, але нам не потрібно ними переймалися — ми зосередимося виключно на власних векторах $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$, які ми щойно знайшли.

Знаходження порядку через оцінку фази

Щоб розв'язати задачу знаходження порядку для заданого вибору $a\in\mathbb{Z}_N^{\ast}$, можна застосувати процедуру оцінки фази до операції $M_a.$

Для цього потрібно ефективно реалізувати квантовою схемою не тільки $M_a$, а й $M_a^2,$ $M_a^4,$ $M_a^8,$ і так далі — стільки, скільки потрібно для отримання достатньо точної оцінки з процедури оцінки фази. Тут ми пояснимо, як це можна зробити, і з'ясуємо, скільки точності потрібно, трохи пізніше.

Почнімо з операції $M_a$ самої по собі. Природно, оскільки ми працюємо з моделлю квантових схем, ми будемо використовувати двійкову нотацію для кодування чисел від $0$ до $N-1.$ Найбільше число, яке нам потрібно закодувати, — $N-1$, тому кількість потрібних бітів:

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Наприклад, якщо $N = 21$, маємо $n = \operatorname{lg}(N-1) = 5.$ Ось як виглядає кодування елементів $\mathbb{Z}_{21}$ у вигляді двійкових рядків довжини $5$.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

А тепер — точне визначення того, як $M_a$ визначається як $n$-кубітна операція.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

Суть у тому, що хоча нас цікавить лише те, як $M_a$ працює для $\vert 0\rangle,\ldots,\vert N-1\rangle$, ми все ж маємо вказати, як вона діє на решту $2^n - N$ станів стандартного базису — і зробити це так, щоб операція залишалася унітарною. Визначення $M_a$ таким чином, що вона нічого не робить з рештою станів стандартного базису, вирішує цю задачу.

Використовуючи алгоритми для цілочисельного множення та ділення, розглянуті в попередньому уроці, разом із методологією їх оборотних реалізацій без «сміттєвих» кубітів, можна побудувати квантову схему, що виконує $M_a$ для будь-якого вибору $a\in\mathbb{Z}_N^{\ast}$, з вартістю $O(n^2).$ Ось один зі способів це зробити.

1. Побудувати схему для виконання операції

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   де

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   використовуючи метод, описаний у попередньому уроці. Це дає нам схему розміру $O(n^2).$

2. Поміняти місцями дві $n$-кубітні системи за допомогою $n$ вентилів swap для поперемінного обміну кубітів.

3. Аналогічно до першого кроку, побудувати схему для операції

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   де $a^{-1}$ — обернений до $a$ в $\mathbb{Z}_N^{\ast}.$

Ініціалізувавши нижні $n$ кубітів і склавши три кроки, отримуємо таке перетворення:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

Метод потребує допоміжних (workspace) кубітів, але наприкінці вони повертаються до початкового стану, що дозволяє використовувати ці схеми для оцінки фази. Загальна вартість отриманої схеми — $O(n^2).$

Щоб виконати $M_a^2,$ $M_a^4,$ $M_a^8,$ і так далі, можна використовувати той самий метод, тільки замінити $a$ на $a^2,$ $a^4,$ $a^8,$ і так далі як елементи $\mathbb{Z}_N^{\ast}.$ Тобто для будь-якого степеня $k$ можна побудувати схему для $M_a^k$ не ітеруванням схеми для $M_a$ $k$ разів, а обчисленням $b = a^k \in \mathbb{Z}_N^{\ast}$ і подальшим використанням схеми для $M_b.$

Обчислення степенів $a^k \in \mathbb{Z}_N$ — це задача модульного піднесення до степеня, згадана в попередньому уроці. Це обчислення можна виконати класично, використовуючи алгоритм модульного піднесення до степеня, згаданий у попередньому уроці (який у обчислювальній теорії чисел часто називають алгоритмом швидкого піднесення до степеня). Насправді нам потрібні лише степені-степені-двійки числа $a$, а саме $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$, і ці степені можна отримати послідовним зведенням у квадрат $m-1$ разів. Кожне зведення в квадрат може бути виконане булевою схемою розміру $O(n^2).$

По суті, ми фактично перекладаємо задачу ітерування $M_a$ до $2^{m-1}$ разів на ефективне класичне обчислення. І добре, що це можливо! Для довільного вибору квантової схеми в задачі оцінки фази це, швидше за все, неможливо — і тоді отримана вартість для оцінки фази зростає експоненційно залежно від кількості контрольних кубітів $m.$

Розв'язання при зручному власному векторі

Щоб зрозуміти, як можна розв'язати задачу знаходження порядку за допомогою оцінки фази, почнімо з припущення, що ми запускаємо процедуру оцінки фази для операції $M_a$ з використанням власного вектора $\vert\psi_1\rangle.$ Як виявляється, отримати цей власний вектор нелегко, тому це ще не кінець розповіді — але тут корисно почати.

Власне значення $M_a$, відповідне власному вектору $\vert \psi_1\rangle$, дорівнює

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Тобто $\omega_r = e^{2\pi i \theta}$ при $\theta = 1/r.$ Отже, якщо запустити процедуру оцінки фази для $M_a$ з власним вектором $\vert\psi_1\rangle$, ми отримаємо наближення до $1/r.$ Обчисливши обернене значення, ми зможемо дізнатися $r$ — за умови, що наше наближення достатньо точне.

Детальніше: коли ми запускаємо процедуру оцінки фази з $m$ контрольними кубітами, ми отримуємо число $y\in\{0,\ldots,2^m-1\}.$ Потім беремо $y/2^m$ як здогадку для $\theta$, що у нашому випадку дорівнює $1/r.$ Щоб з'ясувати, чому дорівнює $r$ за цим наближенням, природним є обчислення оберненого від нашого наближення та округлення до найближчого цілого.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Наприклад, припустимо, що $r = 6$ і ми виконуємо оцінку фази для $M_a$ з власним вектором $\vert\psi_1\rangle$ з використанням $m = 5$ контрольних бітів. Найкраще $5$-бітне наближення до $1/r = 1/6$ — це $5/32$, і ми маємо непогані шанси (близько $68\%$ у цьому випадку) отримати результат $y=5$ з оцінки фази. Маємо

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

і округлення до найближчого цілого дає $6$, що є правильною відповіддю.

З іншого боку, якщо не використовувати достатньої точності, можна не отримати правильної відповіді. Наприклад, якщо взяти $m = 4$ контрольні кубіти в оцінці фази, можна отримати найкраще $4$-бітне наближення до $1/r = 1/6$, яким є $3/16.$ Обчислення оберненого дає

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

і округлення до найближчого цілого дає неправильну відповідь $5.$

То скільки ж точності потрібно, щоб отримати правильну відповідь? Ми знаємо, що порядок $r$ — ціле число, і інтуїтивно кажучи нам потрібно достатньо точності, щоб відрізнити $1/r$ від близьких значень, зокрема $1/(r+1)$ і $1/(r-1).$ Найближче до $1/r$ число, про яке варто турбуватися, — це $1/(r+1)$, і відстань між цими двома числами:

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Отже, якщо ми хочемо переконатися, що не сплутаємо $1/r$ з $1/(r+1)$, достатньо використовувати таку точність, щоб гарантувати, що найкраще наближення $y/2^m$ до $1/r$ ближче до $1/r$, ніж до $1/(r+1).$ Якщо ми використовуємо достатню точність, щоб гарантувати, що

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

тобто похибка менша за половину відстані між $1/r$ і $1/(r+1)$, то $y/2^m$ буде ближче до $1/r$, ніж до будь-якої іншої можливості, включаючи $1/(r+1)$ і $1/(r-1).$

Перевіримо це таким чином. Припустимо, що

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

для $\varepsilon$, що задовольняє

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Обчисливши обернене, отримуємо

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Максимізуючи чисельник і мінімізуючи знаменник, можна обмежити відстань від $r$ таким чином.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Ми відхилилися від $r$ менш ніж на $1/2$, тому, як і очікувалося, при округленні отримаємо $r.$

На жаль, оскільки ми ще не знаємо $r$, ми не можемо використовувати його для визначення потрібної нам точності. Натомість можна скористатися тим фактом, що $r$ менше за $N$, щоб гарантувати достатню точність. Зокрема, якщо ми використовуємо достатню точність, щоб гарантувати, що найкраще наближення $y/2^m$ до $1/r$ задовольняє

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

то ми матимемо достатньо точності, щоб правильно визначити $r$ при обчисленні оберненого. Вибір $m = 2\operatorname{lg}(N)+1$ гарантує, що ми маємо великі шанси отримати оцінку з такою точністю, використовуючи описаний вище метод. (Вибір $m = 2\operatorname{lg}(N)$ достатній, якщо нас влаштовує нижня межа 40% для ймовірності успіху.)

Загальний розв'язок

Як ми щойно побачили, якщо ми маємо власний вектор $\vert \psi_1 \rangle$ оператора $M_a,$ ми можемо дізнатися $r$ за допомогою оцінки фази, за умови, що використовуємо достатньо керуючих кубітів для необхідної точності. На жаль, отримати власний вектор $\vert\psi_1\rangle$ непросто, тому потрібно з'ясувати, як діяти далі.

Уявімо на мить, що ми діємо так само, як вище, але замість $\vert\psi_1\rangle$ беремо власний вектор $\vert\psi_k\rangle$ для будь-якого $k\in\{0,\ldots,r-1\}$ на наш вибір. Результат, який ми отримаємо з процедури оцінки фази, буде наближенням

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Припускаючи, що ні $k,$ ні $r$ нам невідомі, це може або не може дозволити нам визначити $r.$ Наприклад, якщо $k = 0,$ ми отримаємо наближення $y/2^m$ до $0,$ що, на жаль, нічого нам не скаже. Проте це рідкісний випадок; для інших значень $k$ ми принаймні зможемо дізнатися щось про $r.$

Ми можемо скористатися алгоритмом, відомим як алгоритм ланцюгових дробів, щоб перетворити наближення $y/2^m$ на близькі дроби — зокрема $k/r,$ якщо наближення достатньо точне. Пояснювати алгоритм ланцюгових дробів тут ми не будемо. Натомість наведемо твердження про відомий факт стосовно цього алгоритму.

Факт

Нехай дано ціле число $N\geq 2$ та дійсне число $\alpha\in(0,1).$ Тоді існує щонайбільше один вибір цілих чисел $u,v\in\{0,\ldots,N-1\}$ з $v\neq 0$ та $\gcd(u,v)=1,$ що задовольняє $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ За заданими $\alpha$ та $N$ алгоритм ланцюгових дробів знаходить $u$ та $v,$ або повідомляє, що вони не існують. Цей алгоритм може бути реалізований у вигляді булевої схеми розміром $O((\operatorname{lg}(N))^3).$

Якщо ми маємо дуже точне наближення $y/2^m$ до $k/r$ і запустимо алгоритм ланцюгових дробів для $N$ та $\alpha = y/2^m,$ ми отримаємо $u$ та $v,$ як описано у твердженні. Аналіз цього факту дозволяє зробити висновок, що

$$\frac{u}{v} = \frac{k}{r}.$$

Зверни увагу: ми не обов'язково дізнаємося $k$ та $r$ окремо — ми дізнаємося лише $k/r$ у найменшому спільному вигляді.

Наприклад, як ми вже зауважили, при $k=0$ ми нічого не дізнаємося. Але це єдине значення $k,$ де так трапляється. Коли $k$ ненульове, воно може мати спільні множники з $r,$ але число $v,$ яке ми отримаємо від алгоритму ланцюгових дробів, принаймні ділить $r.$

Це не очевидно, але справді: якщо ми маємо змогу дізнаватися $u$ та $v$ для $u/v = k/r,$ де $k\in\{0,\ldots,r-1\}$ вибирається рівномірно випадково, то після кількох спроб ми, швидше за все, зможемо відновити $r.$ Зокрема, якщо наш здогад про $r$ — це найменше спільне кратне всіх значень знаменника $v,$ які ми спостерігаємо, то ми будемо праві з високою ймовірністю. Інтуїтивно, деякі значення $k$ є «невдалими», бо мають спільні множники з $r,$ і ці множники приховані від нас, коли ми дізнаємося $u$ та $v.$ Але випадкові вибори $k$ навряд чи приховуватимуть множники $r$ надовго, і ймовірність неправильного здогаду про $r$ через взяття НСК спостережуваних знаменників зменшується експоненційно зі збільшенням кількості спроб.

Залишається вирішити питання про те, як отримати власний вектор $\vert\psi_k\rangle$ оператора $M_a,$ на якому запускати процедуру оцінки фази. Виявляється, нам насправді не потрібно їх створювати!

Натомість ми запустимо процедуру оцінки фази на стані $\vert 1\rangle,$ маючи на увазі $n$-бітне двійкове кодування числа $1,$ замість власного вектора $\vert\psi\rangle$ оператора $M_a.$ До цього моменту ми говорили лише про запуск процедури оцінки фази на конкретному власному векторі, але ніщо не заважає нам запускати її на вхідному стані, який не є власним вектором $M_a,$ — саме це ми й робимо зі станом $\vert 1\rangle.$ (Це не власний вектор $M_a,$ якщо тільки $a=1,$ а такий вибір нас не цікавить.)

Обґрунтування вибору стану $\vert 1\rangle$ замість власного вектора $M_a$ полягає в тому, що справджується таке рівняння:

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Один зі способів перевірити це рівняння — порівняти скалярні добутки обох частин з кожним стандартним базисним станом, використовуючи формули, згадані раніше в цьому уроці, щоб обчислити результати для правої частини. Внаслідок цього ми отримаємо рівно ті самі результати вимірювань, що й якби ми вибрали $k\in\{0,\ldots,r-1\}$ рівномірно випадково та використали $\vert\psi_k\rangle$ як власний вектор.

Розглянемо детальніше: уявімо, що ми запускаємо процедуру оцінки фази зі станом $\vert 1\rangle$ замість одного з власних векторів $\vert\psi_k\rangle.$ Після виконання оберненого квантового перетворення Фур'є ми отримаємо стан

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

де

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

Вектор $\vert\gamma_k\rangle$ представляє стан верхніх $m$ кубітів після виконання оберненого квантового перетворення Фур'є над ними.

Отже, з огляду на те, що $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ є ортонормованим набором, вимірювання верхніх $m$ кубітів дає наближення $y/2^m$ до значення $k/r,$ де $k\in\{0,\ldots,r-1\}$ вибирається рівномірно випадково. Як ми вже обговорювали, це дозволяє нам визначити $r$ з високим ступенем впевненості після кількох незалежних запусків, що і було нашою метою.

Загальна вартість

Вартість реалізації кожної керованої унітарної операції $M_a^k$ становить $O(n^2).$ Усього є $m$ керованих унітарних операцій, і $m = O(n),$ тому загальна вартість для керованих унітарних операцій — $O(n^3).$ Крім того, є $m$ воріт Адамара (що вносять $O(n)$ у вартість), а обернене квантове перетворення Фур'є вносить $O(n^2).$ Таким чином, вартість керованих унітарних операцій домінує над вартістю всієї процедури — яка тому складає $O(n^3).$

На додаток до самої квантової схеми є кілька класичних обчислень, які потрібно виконати по ходу. Це включає обчислення степенів $a^k$ у $\mathbb{Z}_N$ для $k = 2, 4, 8, \ldots, 2^{m-1},$ які потрібні для створення керованих унітарних воріт, а також алгоритм ланцюгових дробів, що перетворює наближення $\theta$ на дроби. Ці обчислення можна виконати булевими схемами із загальною вартістю $O(n^3).$

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

Факторизація через пошук порядку

Останнє, що нам залишається обговорити, — це як розв'язання задачі пошуку порядку допомагає нам факторизувати. Ця частина є повністю класичною — вона не має нічого спеціально квантового.

Ось основна ідея. Ми хочемо факторизувати число $N,$ і можемо робити це рекурсивно. Зокрема, ми можемо зосередитися на задачі розщеплення $N,$ що означає знаходження двох цілих чисел $b,c\geq 2,$ для яких $N = bc.$ Це неможливо, якщо $N$ — просте число, але ми можемо ефективно перевірити простоту $N$ за допомогою алгоритму тестування простоти, і якщо $N$ не просте — спробувати його розщепити. Після розщеплення $N$ ми просто рекурсивно застосовуємо алгоритм до $b$ та $c,$ поки всі множники не стануть простими і ми не отримаємо розклад $N$ на прості множники.

Розщепити парні числа просто: виводимо $2$ та $N/2.$

Також легко розщепити досконалі степені, тобто числа вигляду $N = s^j$ для цілих $s,j\geq 2,$ — достатньо наближено обчислити корені $N^{1/2},$ $N^{1/3},$ $N^{1/4}$ і так далі, перевіряючи сусідні цілі числа як кандидатів для $s.$ Не потрібно заходити далі, ніж $\log(N)$ кроків у цій послідовності, бо на тому етапі корінь стає меншим за $2$ і нових кандидатів не виявить.

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

Імовірнісний алгоритм для розщеплення непарного складеного цілого числа N, яке не є степенем простого

1. Випадково вибираємо $a\in\{2,\ldots,N-1\}.$

2. Обчислюємо $d=\gcd(a,N).$

3. Якщо $d > 1,$ виводимо $b = d$ та $c = N/d$ і зупиняємося. Інакше переходимо до наступного кроку, знаючи, що $a\in\mathbb{Z}_N^{\ast}.$

4. Нехай $r$ — порядок $a$ за модулем $N.$ (Тут нам потрібен пошук порядку.)

5. Якщо $r$ парне:

   5.1 Обчислюємо $x = a^{r/2} - 1$ за модулем $N$
   5.2 Обчислюємо $d = \gcd(x,N).$
   5.3 Якщо $d>1,$ виводимо $b=d$ та $c = N/d$ і зупиняємося.

6. Якщо досягнуто цього кроку, алгоритм не зміг знайти множник $N.$

Один запуск цього алгоритму може не знайти множника $N.$ Зокрема, це трапляється у двох ситуаціях:

• Порядок $a$ за модулем $N$ непарний.
• Порядок $a$ за модулем $N$ парний і $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

Використовуючи базову теорію чисел, можна довести, що для випадкового вибору $a$ з імовірністю принаймні $1/2$ жодна з цих подій не трапляється. Насправді ймовірність того, що хоча б одна з них трапиться, не перевищує $2^{-(m-1)},$ де $m$ — кількість різних простих множників $N,$ — саме тому потрібне припущення, що $N$ не є степенем простого числа. (Припущення про непарність $N$ також необхідне для справедливості цього факту.)

Це означає, що кожен запуск має принаймні 50% шанс розщепити $N.$ Тому, якщо ми запустимо алгоритм $t$ разів, щоразу випадково вибираючи $a,$ ми успішно розщепимо $N$ з імовірністю принаймні $1 - 2^{-t}.$

Основна ідея алгоритму така. Якщо ми вибрали $a,$ для якого порядок $r$ числа $a$ за модулем $N$ є парним, то $r/2$ — ціле число, і ми можемо розглянути числа

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{та} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Використовуючи формулу $Z^2 - 1 = (Z+1)(Z-1),$ ми отримуємо, що

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Ми знаємо, що $a^r \; (\textrm{mod}\; N) = 1$ за визначенням порядку — тобто $N$ ділить $a^r - 1$ без залишку. Це означає, що $N$ ділить добуток

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Щоб це було правдою, всі прості множники $N$ мають бути також простими множниками $a^{r/2} - 1$ або $a^{r/2} + 1$ (або обох) — і для випадкового вибору $a$ малоймовірно, що всі прості множники $N$ поділять один із доданків і жоден не поділить інший. Інакше, якщо частина простих множників $N$ ділить перший доданок, а частина — другий, ми зможемо знайти нетривіальний множник $N,$ обчисливши НСД з першим доданком.