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 busca, enquanto $A_0$ contém as sequências 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$, ou seja, trata-se de 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.

A título de observação, a notação utilizada aqui é comum: sempre que temos 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.$$

Temos também que $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, de modo que $\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, imediatamente antes das iterações de $G$ ocorrerem na etapa 2, o estado de $\mathsf{Q}$ está contido no espaço vetorial bidimensional gerado por $\vert A_0\rangle$ e $\vert A_1\rangle$; além disso, os coeficientes desses vetores são números reais. Como veremos, o estado $\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íssemos a função $f$ pela composição de $f$ com a função NOT — ou, em outras palavras, a função que obtemos invertendo 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 sequência $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 maneira diferente — pois os estados que obtemos do algoritmo nos dois casos são necessariamente equivalentes, exceto por 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 uma operação de $G$ e sobre os vetores de estado quântico $\vert A_0\rangle$ e $\vert A_1\rangle$.

Primeiro, observemos que a operação $Z_f$ tem um comportamento 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 sequência $x\in\Sigma^n$, e uma maneira alternativa e prática 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},$$

utilizando a mesma notação, $\vert u \rangle$, que usamos acima para a superposição uniforme sobre todas as sequências de bits $n$.

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 gerado 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 associamos as linhas e colunas das matrizes aos 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 vemos 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 duas vezes no ângulo $\theta$ equivale a girar no ângulo $2\theta$. Outra maneira de perceber isso é utilizar 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$ no espaço definido 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 relacionar a análise que acabamos de fazer com uma representação geométrica. A ideia é que a operação $G$ seja o produto de duas reflexões : $Z_f$ e $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. E o efeito final de realizar duas reflexões é realizar 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 gerado por $\vert A_0\rangle$ e $\vert A_1\rangle$, essa é uma reflexão em relação à reta paralela a $\vert A_0\rangle$, que chamaremos de $L_1$. Aqui está uma figura que ilustra a ação dessa reflexão sobre um vetor unitário hipotético $\vert\psi\rangle$, que supomos 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, como já vimos, pode ser escrita da seguinte forma:

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

Esta também é uma reflexão, desta vez sobre a reta $L_2$, paralela ao vetor $\vert u\rangle$. Aqui está uma figura que ilustra o efeito dessa reflexão sobre 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 consiste em girar combinações lineares de $\vert A_0\rangle$ e $\vert A_1\rangle$ em um ângulo de $2\theta$.