Алгоритм Саймона

Алгоритм Саймона — це квантовий алгоритм запитів для задачі, відомої як задача Саймона. Це задача з обіцянкою, що за своїм характером схожа на задачі Дойча-Жожа та Бернштейна-Вазірані, але відрізняється деталями.

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

Задача Саймона

Функція на вхід задачі Саймона має вигляд

$$f:\Sigma^n \rightarrow \Sigma^m$$

для натуральних чисел $n$ та $m.$ З метою спрощення можна було б обмежитися випадком $m = n,$ але це не дає суттєвої переваги — алгоритм Саймона та його аналіз залишаються практично однаковими в обох випадках.

Задача Саймона

Вхідні дані: функція $f:\Sigma^n \rightarrow \Sigma^m$
Обіцянка: існує рядок $s\in\Sigma^n$ такий, що $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ для всіх $x,y\in\Sigma^n$
Результат: рядок $s$

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

Є два основні випадки: перший — коли $s$ є рядком із самих нулів $0^n,$ другий — коли $s$ не є рядком із самих нулів.

• Випадок 1: $s=0^n.$ Якщо $s$ — рядок із самих нулів, то обіцянка спрощується до $[f(x) = f(y)] \Leftrightarrow [x = y].$ Це рівносильно тому, що $f$ є функцією «один до одного» (ін'єкцією).

• Випадок 2: $s\neq 0^n.$ Якщо $s$ не є рядком із самих нулів, то виконання обіцянки для цього рядка означає, що $f$ є функцією «два до одного», тобто для кожного можливого вихідного рядка $f$ існує рівно два вхідних рядки, що дають цей вихід. Більше того, ці два вхідних рядки мають вигляд $w$ та $w \oplus s$ для деякого рядка $w.$

Важливо розуміти, що існує лише один рядок $s,$ який задовольняє обіцянку, — тобто для функцій, що задовольняють обіцянку, завжди є єдина правильна відповідь.

Ось приклад функції вигляду $f:\Sigma^3 \rightarrow \Sigma^5,$ яка задовольняє обіцянку для рядка $s = 011.$

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

Тут $8$ різних вхідних рядків і $4$ різних вихідних рядки, кожен із яких зустрічається двічі — тобто це функція «два до одного». Більше того, для будь-яких двох різних вхідних рядків, що дають однаковий вихід, порозрядне XOR цих рядків дорівнює $011,$ що рівносильно тому, що один із них дорівнює іншому, XOR-ованому з $s.$

Зауважимо, що насправді важливо лише те, чи збігаються вихідні рядки для різних вхідних, а не конкретні значення цих рядків. Наприклад, у наведеному прикладі як виходи $f$ зустрічаються чотири рядки: $10011,$ $00101,$ $00001,$ $11010.$ Ці чотири рядки можна замінити на будь-які чотири різних рядки, і правильна відповідь $s = 011$ не зміниться.

Опис алгоритму

Нижче наведено діаграму квантової схеми алгоритму Саймона.

Уточнимо: зверху $n$ кубітів, на які діють вентилі Адамара, а знизу $m$ кубітів, що безпосередньо входять у вентиль запиту. Схема дуже схожа на алгоритми, розглянуті раніше в уроці, але цього разу немає фазового відлуння; нижні $m$ кубітів входять у вентиль запиту в стані $\vert 0\rangle.$

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

Аналіз

Аналіз алгоритму Саймона починається аналогічно до алгоритму Дойча-Жожа. Після застосування першого шару вентилів Адамара до верхніх $n$ кубітів стан стає

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

Після застосування $U_f$ вихід функції $f$ XOR-ується до нульового стану нижніх $m$ кубітів, і стан стає

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

Після застосування другого шару вентилів Адамара отримуємо такий стан, використовуючи ту саму формулу для дії шару вентилів Адамара:

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

На цьому місці аналіз відхиляється від попередніх алгоритмів.

Нас цікавить ймовірність того, що вимірювання дадуть кожен можливий рядок $y\in\Sigma^n.$ Використовуючи правила аналізу вимірювань із уроку «Множинні системи» курсу «Основи квантової інформації», отримуємо, що ймовірність $p(y)$ отримати рядок $y$ дорівнює

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

Щоб краще зрозуміти ці ймовірності, введемо трохи більше позначень. По-перше, образ функції $f$ — це множина всіх вихідних рядків:

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

По-друге, для кожного рядка $z\in\operatorname{range}(f)$ множину всіх вхідних рядків, що відображаються у $z,$ позначимо як $f^{-1}(\{z\}).$

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

Множина $f^{-1}(\{z\})$ відома як прообраз $\{z\}$ відносно $f.$ Прообраз можна визначити для довільної множини замість $\{z\}$ аналогічним чином — це множина всіх елементів, що відображаються $f$ у цю множину. (Цю позначення не слід плутати з оберненою функцією $f,$ яка може не існувати. Аргументом ліворуч є множина $\{z\},$ а не елемент $z$ — це й дозволяє уникнути плутанини.)

Використовуючи ці позначення, розіб'ємо суму у виразі для ймовірностей:

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

Кожен рядок $x\in\Sigma^n$ зустрічається рівно один раз у двох сумах — ми, по суті, розкладаємо рядки по «кошиках» залежно від вихідного рядка $z = f(x),$ а потім підсумовуємо окремо по кожному «кошику».

Обчислюємо квадрат евклідової норми:

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

Щоб далі спростити ймовірності, розглянемо значення

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

для довільного $z\in\operatorname{range}(f).$

Якщо $s = 0^n,$ то $f$ є функцією «один до одного» і для кожного $z\in\operatorname{range}(f)$ існує рівно один елемент $x\in f^{-1}(\{z\}).$ Тоді значення виразу $(1)$ дорівнює $1.$

Якщо ж $s\neq 0^n,$ то в множині $f^{-1}(\{z\})$ рівно два рядки. Якщо позначити будь-який із них як $w\in f^{-1}(\{z\}),$ то другий має бути $w \oplus s$ за обіцянкою задачі Саймона. Використовуючи це спостереження, спростимо $(1)$:

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

Отже, значення $(1)$ не залежить від конкретного вибору $z\in\operatorname{range}(f)$ в обох випадках.

Завершимо аналіз, розглянувши ті самі два випадки окремо.

• Випадок 1: $s = 0^n.$ У цьому випадку $f$ є функцією «один до одного», тому існує $2^n$ рядків $z\in\operatorname{range}(f),$ і ми отримуємо

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  Тобто вимірювання дають рядок $y\in\Sigma^n,$ вибраний рівномірно випадково.

• Випадок 2: $s \neq 0^n.$ У цьому випадку $f$ є функцією «два до одного», тому в $\operatorname{range}(f)$ є $2^{n-1}$ елементів. Використовуючи формулу вище, отримуємо, що ймовірність виміряти кожне $y\in\Sigma^n$ дорівнює

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  Тобто ми отримуємо рядок, вибраний рівномірно випадково з множини $\{y\in\Sigma^n : y \cdot s = 0\},$ яка містить $2^{n-1}$ рядків. (Оскільки $s\neq 0^n,$ рівно половина двійкових рядків довжини $n$ має двійковий скалярний добуток $1$ з $s,$ а інша половина — $0,$ як ми вже бачили в аналізі алгоритму Дойча-Жожа для задачі Бернштейна-Вазірані.)

Класичне постоброблення

Тепер ми знаємо ймовірності всіх можливих результатів вимірювань при запуску квантової схеми алгоритму Саймона. Чи достатньо цього для визначення $s$?

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

Припустимо, що ми запускаємо схему незалежно $k$ разів, де $k = n + 10.$ Це не унікальне значення — ми можемо взяти $k$ більшим (або меншим) залежно від допустимої ймовірності невдачі. Вибір $k = n + 10$ гарантує успіх із ймовірністю понад $99.9$%.

Запускаючи схему $k$ разів, ми отримуємо рядки $y^1,...,y^{k} \in \Sigma^n.$ Надрядкові індекси — це частини назв рядків, а не степені чи індекси бітів:

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

Формуємо матрицю $M$ з $k$ рядків та $n$ стовпців, взявши біти цих рядків як елементи:

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

Наразі ми не знаємо $s$ — наша мета якраз і полягає в тому, щоб його знайти. Але уявімо на мить, що ми знаємо $s,$ і побудуємо вектор-стовпець $v$ з бітів рядка $s = s_{n-1} \cdots s_0$:

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

Виконавши добуток матриці на вектор $M v$ за модулем $2$ — тобто звичайне множення, після якого від результату беруть лишок від ділення на $2,$ — отримаємо нульовий вектор:

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

Тобто рядок $s,$ записаний як вектор-стовпець $v,$ завжди належить до нуль-простору матриці $M$ за модулем $2.$ Це вірно як у випадку $s = 0^n,$ так і в разі $s\neq 0^n.$ Точніше, нульовий вектор завжди належить нуль-простору $M,$ а у випадку $s\neq 0^n$ до нього також належить вектор з бітів $s.$

Питання лишається: чи можуть у нуль-просторі $M$ бути інші вектори, крім тих, що відповідають $0^n$ та $s$? Відповідь: це стає дедалі менш імовірним зі зростанням $k$ — при $k = n + 10$ нуль-простір $M$ не міститиме інших векторів із ймовірністю понад $99.9$%. Загалом, замінивши $k = n + 10$ на $k = n + r$ для довільного натурального $r,$ ймовірність того, що нуль-простір $M$ містить лише вектори, що відповідають $0^n$ та $s,$ становить щонайменше $1 - 2^{-r}.$

За допомогою лінійної алгебри можна ефективно обчислити нуль-простір матриці $M$ за модулем $2.$ Зокрема, це можна зробити методом Гаусового виключення, який при арифметиці за модулем $2$ працює так само, як із дійсними або комплексними числами. Якщо вектори, що відповідають $0^n$ та $s,$ є єдиними в нуль-просторі $M$ — а це відбувається з великою ймовірністю — ми можемо визначити $s$ за результатами цього обчислення.

Класична складність

Скільки запитів потребує класичний алгоритм запитів для розв'язання задачі Саймона? Відповідь: дуже багато в загальному випадку.

Можна зробити різні точні твердження про класичну складність цієї задачі, і ось одне з них. Якщо будь-який імовірнісний алгоритм запитів робить менше ніж $2^{n/2 - 1} - 1$ запитів — а це експоненційна кількість відносно $n$ — то з ймовірністю щонайменше $1/2$ він не зможе розв'язати задачу Саймона.

Іноді доведення таких результатів неможливості може бути дуже складним, але цей результат не надто складно довести за допомогою елементарного ймовірнісного аналізу. Тут ми лише коротко розглянемо основну інтуїцію.

Ми намагаємося знайти прихований рядок $s,$ але поки ми не запитуємо функцію на двох рядках із однаковим вихідним значенням, ми отримуємо дуже мало інформації про $s.$ Інтуїтивно, ми дізнаємося лише те, що прихований рядок $s$ не є XOR жодних двох різних запитаних рядків. І якщо запитати менше ніж $2^{n/2 - 1} - 1$ рядків, залишається ще безліч варіантів $s,$ які ми не виключили, оскільки пар рядків недостатньо. Це не формальний доказ, а лише основна ідея.

Отже, підсумовуючи, алгоритм Саймона демонструє вражаючу перевагу квантових алгоритмів над класичними в моделі запитів. Зокрема, алгоритм Саймона розв'язує задачу Саймона з кількістю запитів, що є лінійною відносно кількості вхідних бітів $n$ нашої функції, тоді як будь-який класичний алгоритм, навіть імовірнісний, потребує експоненційної кількості запитів відносно $n,$ щоб розв'язати задачу Саймона з розумною ймовірністю успіху.