Análise

Agora, analisaremos o algoritmo do Grover para entender como ele funciona. Começaremos com o que poderia ser descrito como uma análise simbólica, em que calculamos como a operação de Grover $G$ atua em determinados estados e, em seguida, vincularemos essa análise simbólica a uma imagem geométrica que é útil para visualizar como o algoritmo funciona.

---

Soluções e não soluções

Vamos começar definindo dois conjuntos de strings.

$$\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}$$

O conjunto $A_1$ contém todas as soluções para o nosso problema de pesquisa, enquanto $A_0$ contém as cadeias de caracteres que não são soluções (às quais podemos nos referir como não-soluções quando for conveniente). Esses dois conjuntos satisfazem $A_0 \cap A_1 = \varnothing$ e $A_0 \cup A_1 = \Sigma^n,$, o que significa que essa é uma bipartição de $\Sigma^n.$

Em seguida, definiremos dois vetores unitários que representam superposições uniformes sobre os conjuntos de soluções e não soluções.

$$\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}$$

Em termos formais, cada um desses vetores só é definido quando o conjunto correspondente não é vazio, mas daqui em diante vamos nos concentrar no caso em que nem $A_0$ nem $A_1$ são vazios. Os casos de $A_0 = \varnothing$ e $A_1 = \varnothing$ são facilmente tratados separadamente, e faremos isso mais tarde.

Como um aparte, a notação que está sendo usada aqui é comum: sempre que tivermos um conjunto finito e não vazio $S,$, podemos escrever $\vert S\rangle$ para denotar o vetor de estado quântico que é uniforme sobre os elementos de $S.$

Vamos também definir $\vert u \rangle$ como um estado quântico uniforme em todas as cadeias de bits $n$ :

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

Observe que

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

Também temos que $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ so $\vert u\rangle$ representa o estado do registro $\mathsf{Q}$ após a inicialização na etapa 1 do algoritmo de Grover.

Isso implica que, pouco antes de as iterações de $G$ acontecerem na etapa 2, o estado de $\mathsf{Q}$ está contido no espaço vetorial bidimensional abrangido por $\vert A_0\rangle$ e $\vert A_1\rangle,$ e, além disso, os coeficientes desses vetores são números reais. Como veremos, o estado de $\mathsf{Q}$ sempre terá essas propriedades - o que significa que o estado é uma combinação linear real de $\vert A_0\rangle$ e $\vert A_1\rangle$ - após qualquer número de iterações da operação $G$ na etapa 2.

---

Uma observação sobre a operação Grover

Agora vamos voltar nossa atenção para a operação de Grover

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

começando com uma observação interessante sobre ele.

Imagine, por um momento, que substituímos a função $f$ pela composição de $f$ com a função NOT - ou, em outras palavras, a função que obtemos ao inverter o bit de saída de $f.$ Chamaremos essa nova função de $g,$ e podemos expressá-la usando símbolos de algumas maneiras alternativas.

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

Observe que

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

para cada string $x\in\Sigma^n,$ e, portanto

$$Z_g = - Z_f.$$

Isso significa que, se substituíssemos a função $f$ pela função $g,$, o algoritmo de Grover não funcionaria de forma diferente, pois os estados que obtemos do algoritmo nos dois casos são necessariamente equivalentes até uma fase global.

Isso não é um problema! Intuitivamente falando, o algoritmo não se importa com quais cadeias são soluções e quais não são - ele só precisa ser capaz de distinguir soluções e não soluções para operar corretamente.

---

Ação da operação Grover

Agora vamos considerar a ação de $G$ nos vetores de estado quântico $\vert A_0\rangle$ e $\vert A_1\rangle.$

Primeiro, vamos observar que a operação $Z_f$ tem uma ação muito simples em $\vert A_0\rangle$ e $\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}$$

Em segundo lugar, temos a operação $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ A operação $Z_{\mathrm{OR}}$ é definida como

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

novamente para cada string $x\in\Sigma^n,$ e uma maneira alternativa conveniente de expressar essa operação é assim:

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

Uma maneira simples de verificar se essa expressão está de acordo com a definição de $Z_{\mathrm{OR}}$ é avaliar sua ação em estados de base padrão.

A operação $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ pode, portanto, ser escrita da seguinte forma:

$$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},$$

usando a mesma notação, $\vert u \rangle,$ que usamos acima para a superposição uniforme em todas as cadeias de $n$ bits.

E agora temos o que precisamos para calcular a ação de $G$ em $\vert A_0\rangle$ e $\vert A_1\rangle.$ Primeiro, vamos calcular a ação de $G$ em $\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}$$

E, em segundo lugar, vamos calcular a ação de $G$ em $\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}$$

Em ambos os casos, estamos usando a equação

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

juntamente com as expressões

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

que se seguem.

Em resumo, temos

$$\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}$$

Como já observamos, o estado de $\mathsf{Q}$ imediatamente antes da etapa 2 está contido no espaço bidimensional abrangido por $\vert A_0\rangle$ e $\vert A_1\rangle,$ e acabamos de estabelecer que $G$ mapeia qualquer vetor nesse espaço para outro vetor no mesmo espaço. Isso significa que, para fins de análise, podemos concentrar nossa atenção exclusivamente nesse subespaço.

Para entender melhor o que está acontecendo nesse espaço bidimensional, vamos expressar a ação do $G$ nesse espaço como uma matriz,

$$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},$$

cujas primeira e segunda linhas/colunas correspondem a $\vert A_0\rangle$ e $\vert A_1\rangle,$, respectivamente. Até agora, nesta série, sempre conectamos as linhas e colunas das matrizes com os estados clássicos de um sistema, mas as matrizes também podem ser usadas para descrever as ações de mapeamentos lineares em diferentes bases, como temos aqui.

Embora não seja óbvio à primeira vista, a matriz $M$ é o que obtemos ao elevar ao quadrado uma matriz de aparência mais simples.

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

A matriz

$$\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}$$

é uma matriz de rotação, que pode ser expressa alternativamente como

$$\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}$$

para

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

Esse ângulo $\theta$ desempenhará um papel muito importante na análise a seguir, portanto, vale a pena enfatizar sua importância aqui, pois o vemos pela primeira vez.

À luz dessa expressão dessa matriz, observamos que

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

Isso ocorre porque girar o ângulo $\theta$ duas vezes é equivalente a girar o ângulo $2\theta.$ Outra maneira de ver isso é usar a expressão alternativa

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

juntamente com as fórmulas de ângulo duplo da trigonometria:

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

Em resumo, o estado do registro $\mathsf{Q}$ no início da etapa 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,$$

e o efeito de aplicar $G$ a esse estado é girá-lo em um ângulo $2\theta$ dentro do espaço abrangido por $\vert A_0\rangle$ e $\vert A_1\rangle.$ Assim, por exemplo, temos

$$\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}$$

e em geral

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

---

Imagem geométrica

Agora vamos conectar a análise que acabamos de fazer a uma imagem geométrica. A ideia é que a operação $G$ é o produto de duas reflexões, $Z_f$ e $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ E o efeito líquido da realização de duas reflexões é a realização de uma rotação.

Vamos começar com $Z_f.$ Como já observamos anteriormente, temos

$$\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}$$

No espaço vetorial bidimensional abrangido por $\vert A_0\rangle$ e $\vert A_1\rangle,$ essa é uma reflexão sobre a linha paralela a $\vert A_0\rangle,$ que chamaremos de $L_1.$ Aqui está uma figura que ilustra a ação dessa reflexão em um vetor unitário hipotético $\vert\psi\rangle,$ que estamos supondo ser uma combinação linear real de $\vert A_0\rangle$ e $\vert A_1\rangle.$

Em segundo lugar, temos a operação $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$, que já vimos que pode ser escrita como

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

Essa também é uma reflexão, dessa vez sobre a linha $L_2$ paralela ao vetor $\vert u\rangle.$ Aqui está uma figura que descreve a ação dessa reflexão em um vetor unitário $\vert\psi\rangle.$

Quando compomos essas duas reflexões, obtemos uma rotação - pelo dobro do ângulo entre as linhas de reflexão - como ilustra esta figura.

Isso explica, em termos geométricos, por que o efeito da operação de Grover é girar as combinações lineares de $\vert A_0\rangle$ e $\vert A_1\rangle$ em um ângulo de $2\theta.$