Аналіз

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

Розв'язки і нерозв'язки

Почнемо з означення двох множин рядків.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

Множина $A_1$ містить усі розв'язки нашої задачі пошуку, тоді як $A_0$ містить рядки, що не є розв'язками (які для зручності назвемо нерозв'язками). Ці дві множини задовольняють $A_0 \cap A_1 = \varnothing$ і $A_0 \cup A_1 = \Sigma^n$, тобто є двочастинним розбиттям $\Sigma^n$.

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

$$\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$ не є порожньою. Випадки $A_0 = \varnothing$ і $A_1 = \varnothing$ легко розглядаються окремо, і ми зробимо це пізніше.

Зауважимо, що позначення, яке тут використовується, є загальноприйнятим: для будь-якої скінченної та непорожньої множини $S$ можна записати $\vert S\rangle$ для позначення вектора квантового стану, рівномірного над елементами $S$.

Також визначимо $\vert u \rangle$ як рівномірний квантовий стан над усіма $n$-бітними рядками:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Зауважимо, що

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Також маємо $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, тому $\vert u\rangle$ представляє стан регістра $\mathsf{Q}$ після ініціалізації на кроці 1 алгоритму Гровера.

Це означає, що безпосередньо перед ітераціями $G$ на кроці 2 стан $\mathsf{Q}$ міститься у двовимірному векторному просторі, натягнутому на $\vert A_0\rangle$ і $\vert A_1\rangle$, і коефіцієнти цих векторів є дійсними числами. Як ми побачимо, стан $\mathsf{Q}$ завжди матиме ці властивості — тобто буде дійсною лінійною комбінацією $\vert A_0\rangle$ і $\vert A_1\rangle$ — після будь-якої кількості ітерацій операції $G$ на кроці 2.

Спостереження про операцію Гровера

Тепер звернемо увагу на операцію Гровера

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

розпочавши з цікавого спостереження про неї.

Уявімо на мить, що ми замінили функцію $f$ на композицію $f$ з функцією NOT — іншими словами, функцію, отриману інвертуванням вихідного біта $f$. Назвемо цю нову функцію $g$, і можна виразити її символами кількома еквівалентними способами.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Зауважимо, що

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

для кожного рядка $x\in\Sigma^n$, і тому

$$Z_g = - Z_f.$$

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

Це не проблема! Інтуїтивно кажучи, алгоритму байдуже, які рядки є розв'язками, а які — ні; йому лише потрібно вміти розрізняти розв'язки і нерозв'язки для правильної роботи.

Дія операції Гровера

Тепер розглянемо дію $G$ на вектори квантових станів $\vert A_0\rangle$ і $\vert A_1\rangle$.

По-перше, зауважимо, що операція $Z_f$ має дуже просту дію на $\vert A_0\rangle$ і $\vert A_1\rangle$.

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

По-друге, маємо операцію $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Операція $Z_{\mathrm{OR}}$ визначається як

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

знову для кожного рядка $x\in\Sigma^n$, і зручний альтернативний спосіб виразити цю операцію такий:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Простий спосіб перевірити, що цей вираз узгоджується з означенням $Z_{\mathrm{OR}},$ — оцінити його дію на стани стандартного базису.

Операцію $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ можна тому записати так:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

використовуючи те саме позначення $\vert u \rangle$ для рівномірної суперпозиції над усіма $n$-бітними рядками.

Тепер маємо все необхідне для обчислення дії $G$ на $\vert A_0\rangle$ і $\vert A_1\rangle$. Спочатку обчислимо дію $G$ на $\vert A_0\rangle$.

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

А по-друге, обчислимо дію $G$ на $\vert A_1\rangle$.

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

В обох випадках ми використовуємо рівняння

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

разом з виразами

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{та}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

що з них випливають.

Підсумовуючи, маємо

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Як вже зазначалося, стан $\mathsf{Q}$ безпосередньо перед кроком 2 міститься у двовимірному просторі, натягнутому на $\vert A_0\rangle$ і $\vert A_1\rangle$, і ми щойно встановили, що $G$ відображає будь-який вектор з цього простору на інший вектор з того самого простору. Це означає, що для цілей аналізу ми можемо зосередити увагу виключно на цьому підпросторі.

Щоб краще зрозуміти, що відбувається в цьому двовимірному просторі, виразимо дію $G$ на цьому просторі у вигляді матриці:

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

рядки та стовпці якої відповідають $\vert A_0\rangle$ і $\vert A_1\rangle$ відповідно. Досі в цій серії ми завжди пов'язували рядки та стовпці матриць з класичними станами системи, але матриці також можна використовувати для опису дій лінійних відображень на різних базисах, як тут.

Хоча це зовсім не очевидно на перший погляд, матриця $M$ є результатом піднесення до квадрата матриці простішого вигляду.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

Матриця

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

є матрицею повороту, яку можна альтернативно виразити як

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

для

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

Цей кут $\theta$ відіграватиме дуже важливу роль у подальшому аналізі, тому варто підкреслити його значення, коли ми вперше його бачимо.

З огляду на цей вираз цієї матриці, спостерігаємо, що

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Це пояснюється тим, що два повороти на кут $\theta$ еквівалентні повороту на кут $2\theta$. Інший спосіб побачити це — скористатися альтернативним виразом

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

разом з формулами подвійного кута з тригонометрії:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

Підсумовуючи, стан регістра $\mathsf{Q}$ на початку кроку 2 такий:

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

і ефект застосування $G$ до цього стану — це його поворот на кут $2\theta$ у просторі, натягнутому на $\vert A_0\rangle$ і $\vert A_1\rangle$. Наприклад, маємо

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

і в загальному випадку

$$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.$$

Геометрична картинка

Тепер пов'яжемо щойно проведений аналіз з геометричною картинкою. Ідея полягає в тому, що операція $G$ є добутком двох відображень: $Z_f$ і $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ А сумарна дія двох відображень — це поворот.

Почнемо з $Z_f$. Як ми вже спостерігали раніше:

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

У двовимірному векторному просторі, натягнутому на $\vert A_0\rangle$ і $\vert A_1\rangle$, це є відображенням відносно прямої, паралельної $\vert A_0\rangle$, яку ми назвемо $L_1$. Ось рисунок, що ілюструє дію цього відображення на гіпотетичний одиничний вектор $\vert\psi\rangle$, який, за припущенням, є дійсною лінійною комбінацією $\vert A_0\rangle$ і $\vert A_1\rangle$.

По-друге, маємо операцію $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$, яку ми вже бачили у вигляді

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Це також відображення, цього разу відносно прямої $L_2$, паралельної вектору $\vert u\rangle$. Ось рисунок, що зображує дію цього відображення на одиничний вектор $\vert\psi\rangle$.

Коли ми компонуємо ці два відображення, отримуємо поворот — на подвійний кут між осями відображень, — як ілюструє цей рисунок.

Це пояснює, у геометричних термінах, чому ефект операції Гровера полягає в повороті лінійних комбінацій $\vert A_0\rangle$ і $\vert A_1\rangle$ на кут $2\theta$.