Análise

Agora vamos analisar o algoritmo de Grover para entender como ele funciona. Começaremos com o que poderia ser descrito como uma análise simbólica, onde calculamos como a operação de Grover $G$ age sobre certos estados, e depois conectaremos 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 do nosso problema de busca, enquanto $A_0$ contém as strings que não são soluções (que podemos chamar de não-soluções quando 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 representando 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}$$

Formalmente, cada um desses vetores só está 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$ é vazio. Os casos em que $A_0 = \varnothing$ e $A_1 = \varnothing$ podem ser tratados separadamente com facilidade, e faremos isso mais tarde.

Como observação, a notação usada 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 uniforme sobre os elementos de $S.$

Vamos também definir $\vert u \rangle$ como o estado quântico uniforme sobre todas as strings de $n$ bits:

$$\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,$ portanto $\vert u\rangle$ representa o estado do registrador $\mathsf{Q}$ após a inicialização no passo 1 do algoritmo de Grover.

Isso implica que, imediatamente antes das iterações de $G$ acontecerem no passo 2, o estado de $\mathsf{Q}$ está contido no espaço vetorial bidimensional gerado 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 — ou seja, 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$ no passo 2.

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

Voltaremos agora 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 ela.

Imagine por um momento que substituímos a função $f$ pela composição de $f$ com a função NOT — ou seja, 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 formas 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 toda 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 — porque os estados obtidos pelo algoritmo nos dois casos são necessariamente equivalentes a menos de uma fase global.

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

Ação da operação de Grover

Agora vamos considerar a ação de $G$ sobre os 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 sobre $\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 toda string $x\in\Sigma^n,$ e uma forma alternativa conveniente de expressar essa operação é:

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

Uma maneira simples de verificar que essa expressão concorda com a definição de $Z_{\mathrm{OR}}$ é avaliar sua ação sobre os estados da base computacional.

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

$$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 sobre todas as strings de $n$ bits.

E agora temos o que precisamos para calcular a ação de $G$ sobre $\vert A_0\rangle$ e $\vert A_1\rangle.$ Primeiro, vamos calcular a ação de $G$ sobre $\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$ sobre $\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{e}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

que decorrem dela.

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 do passo 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 de $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 de 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 nada ó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 podemos alternativamente expressar 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$ vai desempenhar um papel muito importante na análise que se segue, portanto vale a pena enfatizar sua importância aqui quando o vemos pela primeira vez.

À luz dessa expressão da 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 rotacionar pelo ângulo $\theta$ duas vezes é equivalente a rotacionar pelo ângulo $2\theta.$ Outra forma 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 do â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 registrador $\mathsf{Q}$ no início do passo 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 é rotacioná-lo por um ângulo $2\theta$ dentro do espaço gerado 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 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}$$

Dentro do espaço vetorial bidimensional gerado por $\vert A_0\rangle$ e $\vert A_1\rangle,$ essa é uma reflexão em torno da reta paralela a $\vert A_0\rangle,$ que chamaremos de $L_1.$ Aqui está uma figura ilustrando a ação dessa reflexão sobre um vetor unitário hipotético $\vert\psi\rangle,$ que assumimos 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 poder 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, desta vez em torno da reta $L_2$ paralela ao vetor $\vert u\rangle.$ Aqui está uma figura que ilustra a ação dessa reflexão sobre um vetor unitário $\vert\psi\rangle.$

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

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