Перейти до основного вмісту

Аналіз

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

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

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

A0={x∈Σn:f(x)=0}A1={x∈Σn:f(x)=1}\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}

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

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

∣A0⟩=1∣A0∣∑x∈A0∣x⟩∣A1⟩=1∣A1∣∑x∈A1∣x⟩\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}

Формально кожен з цих векторів визначений лише тоді, коли відповідна множина непорожня, але далі ми зосередимось на випадку, коли жодна з A0A_0 і A1A_1 не є порожньою. Випадки A0=∅A_0 = \varnothing і A1=∅A_1 = \varnothing легко розглядаються окремо, і ми зробимо це пізніше.

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

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

∣u⟩=1N∑x∈Σn∣x⟩.\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.

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

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩.\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.

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

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

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

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

G=H⊗nZORH⊗nZf,G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,

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

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

g(x)=¬f(x)=1⊕f(x)=1−f(x)={1f(x)=00f(x)=1g(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⊕f(x)=−(−1)f(x)(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}

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

Zg=−Zf.Z_g = - Z_f.

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

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

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

Тепер розглянемо дію GG на вектори квантових станів ∣A0⟩\vert A_0\rangle і ∣A1⟩.\vert A_1\rangle.

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

Zf∣A0⟩=∣A0⟩Zf∣A1⟩=−∣A1⟩\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⊗nZORH⊗n.H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}. Операція ZORZ_{\mathrm{OR}} визначається як

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n,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∈Σn,x\in\Sigma^n, і зручний альтернативний спосіб виразити цю операцію такий:

ZOR=2∣0n⟩⟨0n∣−I.Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.

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

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

H⊗nZORH⊗n=2H⊗n∣0n⟩⟨0n∣H⊗n−I=2∣u⟩⟨u∣−I,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},

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

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

G∣A0⟩=(2∣u⟩⟨u∣−I)Zf∣A0⟩=(2∣u⟩⟨u∣−I)∣A0⟩=2∣A0∣N∣u⟩−∣A0⟩=2∣A0∣N(∣A0∣N∣A0⟩+∣A1∣N∣A1⟩)−∣A0⟩=(2∣A0∣N−1)∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩=∣A0∣−∣A1∣N∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩\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}

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

G∣A1⟩=(2∣u⟩⟨u∣−I)Zf∣A1⟩=−(2∣u⟩⟨u∣−I)∣A1⟩=−2∣A1∣N∣u⟩+∣A1⟩=−2∣A1∣N(∣A0∣N∣A0⟩+∣A1∣N∣A1⟩)+∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+(1−2∣A1∣N)∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+∣A0∣−∣A1∣N∣A1⟩\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}

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

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩\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

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

⟨u∣A0⟩=∣A0∣Nта⟨u∣A1⟩=∣A1∣N\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}}

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

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

G∣A0⟩=∣A0∣−∣A1∣N∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩G∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+∣A0∣−∣A1∣N∣A1⟩.\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}

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

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

M=(∣A0∣−∣A1∣N−2∣A1∣⋅∣A0∣N2∣A0∣⋅∣A1∣N∣A0∣−∣A1∣N),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},

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

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

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)2=(∣A0∣−∣A1∣N−2∣A1∣⋅∣A0∣N2∣A0∣⋅∣A1∣N∣A0∣−∣A1∣N)=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

Матриця

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)\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}

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

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)=(cos⁡(θ)−sin⁡(θ)sin⁡(θ)cos⁡(θ))\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}

для

θ=sin⁡−1(∣A1∣N).\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).

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

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

M=(cos⁡(θ)−sin⁡(θ)sin⁡(θ)cos⁡(θ))2=(cos⁡(2θ)−sin⁡(2θ)sin⁡(2θ)cos⁡(2θ)).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θ.2\theta. Інший спосіб побачити це — скористатися альтернативним виразом

θ=cos⁡−1(∣A0∣N),\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),

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

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

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

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩=cos⁡(θ)∣A0⟩+sin⁡(θ)∣A1⟩,\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,

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

G∣u⟩=cos⁡(3θ)∣A0⟩+sin⁡(3θ)∣A1⟩G2∣u⟩=cos⁡(5θ)∣A0⟩+sin⁡(5θ)∣A1⟩G3∣u⟩=cos⁡(7θ)∣A0⟩+sin⁡(7θ)∣A1⟩\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}

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

Gt∣u⟩=cos⁡((2t+1)θ)∣A0⟩+sin⁡((2t+1)θ)∣A1⟩.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.

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

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

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

Zf∣A0⟩=∣A0⟩Zf∣A1⟩=−∣A1⟩.\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}

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

Рисунок, що зображує дію відображення на вектор.

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

H⊗nZORH⊗n=2∣u⟩⟨u∣−I.H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.

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

Рисунок, що зображує дію другого відображення на вектор.

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

Рисунок, що зображує дію операції Гровера на вектор.

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