Вибір кількості ітерацій

Ми встановили, що вектор стану регістра $\mathsf{Q}$ в алгоритмі Гровера залишається у двовимірному підпросторі, натягнутому на $\vert A_0\rangle$ і $\vert A_1\rangle,$ після виконання кроку ініціалізації.

Мета — знайти елемент $x\in A_1,$ і ця мета буде досягнута, якщо вдасться отримати стан $\vert A_1\rangle,$ оскільки при вимірюванні цього стану ми гарантовано отримаємо результат $x\in A_1.$ Враховуючи, що стан $\mathsf{Q}$ після $t$ ітерацій на кроці 2 дорівнює

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

слід обрати $t$ таким чином, щоб

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

було якомога ближчим до $1$ за модулем, максимізуючи ймовірність отримати $x\in A_1$ при вимірюванні. Для будь-якого кута $\theta \in (0,2\pi)$ значення $\sin((2t + 1)\theta)$ коливається зі збільшенням $t,$ хоча й не обов'язково є періодичним — немає гарантії, що ми коли-небудь отримаємо одне й те саме значення двічі.

Звичайно, окрім того, щоб зробити ймовірність отримання елемента $x\in A_1$ при вимірюванні великою, ми також хочемо обрати $t$ якомога меншим, оскільки $t$ застосувань операції $G$ вимагають $t$ запитів до функції $f.$ Оскільки ми прагнемо зробити $\sin( (2t + 1) \theta)$ близьким до $1$ за модулем, природний спосіб — обрати $t$ так, щоб

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

Розв'язуючи відносно $t,$ отримуємо

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Звичайно, $t$ повинно бути цілим числом, тому ми не завжди можемо точно влучити в це значення — але можемо взяти найближче ціле число до цього значення, а саме

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

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

(Зауважимо до речі, що якщо цільове значення $\pi/(4\theta) - 1/2$ виявляється рівно посередині між двома цілими числами, цей вираз для $t$ відповідає округленню вгору. Можна також округлити вниз, що має сенс, оскільки означає на один запит менше — але це другорядне і несуттєве для цілей уроку.)

Згадуючи, що значення кута $\theta$ задається формулою

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

бачимо, що рекомендована кількість ітерацій $t$ залежить від кількості рядків у $A_1.$ Це становить проблему, якщо ми не знаємо кількість розв'язків, як ми обговоримо пізніше.

Унікальний пошук

Спочатку зосередимось на ситуації, коли існує єдиний рядок $x$ такий, що $f(x)=1.$ Інший спосіб сказати це — ми розглядаємо екземпляр задачі унікального пошуку. У цьому випадку маємо

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

що зручно апроксимується як

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

при великих $N.$ Підставляючи $\theta = 1/\sqrt{N}$ у вираз

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

отримуємо

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Згадуючи, що $t$ — це не лише кількість разів, коли виконується операція $G,$ але й кількість запитів до функції $f,$ необхідних алгоритму, бачимо, що ми на шляху до отримання алгоритму, що вимагає $O(\sqrt{N})$ запитів.

Тепер дослідимо, наскільки добре працює рекомендований вибір $t.$ Ймовірність того, що фінальне вимірювання дасть єдиний розв'язок, можна явно виразити як

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

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

Ось таблиця ймовірностей успіху для зростаючих значень $N = 2^n.$

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Зауважимо, що ці ймовірності не є строго зростаючими. Зокрема, є цікава аномалія при $N=4,$ де розв'язок отримується з повною визначеністю. Проте можна довести у загальному випадку, що

$$p(N,1) \geq 1 - \frac{1}{N}$$

для всіх $N,$ тож ймовірність успіху прямує до $1$ в границі при $N\to\infty,$ що й видно з наведених значень. Це добре!

Проте зауважимо, що навіть слабка оцінка $p(N,1) \geq 1/2$ підтверджує корисність алгоритму Гровера. Для будь-якого результату вимірювання $x,$ отриманого від запуску процедури, ми завжди можемо перевірити, чи $f(x) = 1$ за допомогою одного запиту до $f.$ І якщо ймовірність не отримати єдиний рядок $x,$ для якого $f(x) = 1,$ при одному запуску процедури не перевищує $1/2,$ то після $m$ незалежних запусків ймовірність не отримати цей рядок $x$ не перевищує $2^{-m}.$ Тобто, використовуючи $O(m \sqrt{N})$ запитів до $f,$ ми знайдемо єдиний розв'язок $x$ з ймовірністю принаймні $1 - 2^{-m}.$ Використовуючи кращу оцінку $p(N,1) \geq 1 - 1/N,$ можна показати, що ймовірність знайти $x\in A_1$ цим методом насправді становить принаймні $1 - N^{-m}.$

Кілька розв'язків

Зі зміною кількості елементів у $A_1$ змінюється і кут $\theta,$ що може суттєво впливати на ймовірність успіху алгоритму. Для стислості позначимо $s = \vert A_1 \vert$ кількість розв'язків, і, як раніше, припустимо $s\geq 1.$

Як мотивуючий приклад, уявімо, що маємо $s = 4$ розв'язки замість одного, як розглядалось вище. Це означає, що

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

що приблизно вдвічі більший за кут у випадку $\vert A_1 \vert = 1$ при великих $N.$ Припустимо, що ми не знали нічого кращого і обрали те саме значення $t,$ що й у випадку єдиного розв'язку:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

Наслідки будуть катастрофічними, як показує така таблиця ймовірностей.

$$\begin{array}{ll} N & \text{Success probability}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Цього разу ймовірність успіху прямує до $0$ при $N\to\infty.$ Це відбувається тому, що ми ефективно обертаємось удвічі швидше, ніж при єдиному розв'язку, тому проскакуємо мимо цільового стану $\vert A_1\rangle$ і опиняємось поблизу $-\vert A_0\rangle.$

Проте якщо замість цього використовувати рекомендований вибір $t,$ а саме

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

для

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

то продуктивність буде кращою. Точніше, цей вибір $t$ забезпечує успіх з високою ймовірністю.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Узагальнюючи сказане раніше, можна довести, що

$$p(N,s) \geq 1 - \frac{s}{N},$$

де використовуємо позначення, запропоноване раніше: $p(N,s)$ означає ймовірність того, що алгоритм Гровера, запущений на $t$ ітерацій, виявить розв'язок, коли є $s$ розв'язків з $N$ можливостей.

Ця нижня оцінка $1 - s/N$ дещо дивна тим, що більша кількість розв'язків означає гіршу нижню оцінку — але за умови, що $s$ значно менше за $N,$ ми все одно робимо висновок, що ймовірність успіху є достатньо великою. Як і раніше, сам факт, що $p(N,s)$ є достатньо великою, підтверджує корисність алгоритму.

Також виявляється, що

$$p(N,s) \geq \frac{s}{N}.$$

Ця нижня оцінка описує ймовірність того, що рядок $x\in\Sigma^n,$ обраний рівномірно випадково, є розв'язком — тобто алгоритм Гровера завжди діє принаймні так само добре, як випадкове вгадування. (Насправді, при $t=0$ алгоритм Гровера і є випадковим вгадуванням.)

Тепер розглянемо кількість ітерацій (а отже, і кількість запитів)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

для

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

Для кожного $\alpha \in [0,1]$ маємо $\sin^{-1}(\alpha)\geq \alpha,$ тому

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Це означає, що

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Це відповідає економії запитів зі зростанням $s.$ Зокрема, необхідна кількість запитів становить

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Невідома кількість розв'язків

Якщо кількість розв'язків $s = \vert A_1 \vert$ невідома, потрібен інший підхід, оскільки в цій ситуації у нас немає знань про $s$ для вибору $t.$ Насправді, існує кілька підходів.

Один простий підхід — обрати

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

рівномірно випадково. Такий вибір $t$ завжди знаходить розв'язок (якщо він існує) з ймовірністю більше 40%, хоча це не очевидно і вимагає аналізу, який тут не наводиться. Проте це має сенс, особливо якщо думати про геометричну картинку: обертання стану $\mathsf{Q}$ випадкову кількість разів схоже на вибір випадкового одиничного вектора в просторі, натягнутому на $\vert A_0\rangle$ і $\vert A_1\rangle,$ для якого ймовірно, що коефіцієнт при $\vert A_1\rangle$ буде достатньо великим. Повторюючи цю процедуру і перевіряючи результат так само, як описано раніше, ймовірність знайти розв'язок можна зробити дуже близькою до $1.$

Існує уточнений метод, що знаходить розв'язок (коли він існує) з використанням $O(\sqrt{N/s})$ запитів навіть тоді, коли кількість розв'язків $s$ невідома, і вимагає $O(\sqrt{N})$ запитів для встановлення того, що розв'язків немає, при $s=0.$

Основна ідея — обирати $t$ рівномірно випадково з множини $\{1,\ldots,T\}$ ітеративно, збільшуючи значення $T.$ Зокрема, можна почати з $T = 1$ і збільшувати його експоненційно, завжди завершуючи процес, щойно знайдено розв'язок, і обмежуючи $T,$ щоб не витрачати запити дарма, якщо розв'язку немає. Процес використовує той факт, що при більшій кількості розв'язків потрібно менше запитів. Проте слід дотримуватись певної обережності, щоб збалансувати швидкість зростання $T$ з ймовірністю успіху на кожній ітерації. (Наприклад, $T \leftarrow \lceil \frac{5}{4}T\rceil$ спрацьовує, як показує аналіз. Проте подвоєння $T$ не спрацьовує — це виявляється занадто швидким зростанням.)

Тривіальні випадки

У проведеному вище аналізі ми припускали, що кількість розв'язків ненульова. Дійсно, посилаючись на вектори

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

ми неявно припускали, що $A_0$ і $A_1$ обидві непорожні. Тут ми коротко розглянемо, що відбувається, коли одна з цих множин порожня.

Перш ніж вдаватися в аналіз, зазначимо очевидне: якщо кожний рядок $x\in\Sigma^n$ є розв'язком, то при вимірюванні ми побачимо розв'язок; а коли розв'язків немає, ми його не побачимо. У певному сенсі глибший аналіз тут не потрібен.

Проте можемо швидко перевірити математику для цих тривіальних випадків. Ситуація, коли одна з множин $A_0$ або $A_1$ порожня, виникає, коли $f$ є константною: $A_1$ порожня, якщо $f(x) = 0$ для кожного $x\in\Sigma^n,$ і $A_0$ порожня, якщо $f(x) = 1$ для кожного $x\in\Sigma^n.$ Це означає, що

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

і тому

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Отже, незалежно від кількості ітерацій $t,$ виконаних у цих випадках, вимірювання завжди виявлятиме рівномірно випадковий рядок $x\in\Sigma^n.$