Escolhendo o número de iterações

Estabelecemos que o vetor de estado do registrador $\mathsf{Q}$ no algoritmo de Grover permanece no subespaço bidimensional gerado por $\vert A_0\rangle$ e $\vert A_1\rangle$ uma vez que a etapa de inicialização tenha sido executada.

O objetivo é encontrar um elemento $x\in A_1$, e esse objetivo será alcançado se conseguirmos obter o estado $\vert A_1\rangle$ — pois se medirmos esse estado, teremos a garantia de obter um resultado de medição $x\in A_1$. Dado que o estado de $\mathsf{Q}$ após $t$ iterações na etapa 2 é

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

devemos escolher $t$ de forma que

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

seja o mais próximo possível de $1$ em valor absoluto, para maximizar a probabilidade de obter $x\in A_1$ a partir da medição. Para qualquer ângulo $\theta \in (0,2\pi)$, o valor $\sin((2t + 1)\theta)$ oscila conforme $t$ aumenta, mas não é necessariamente periódico — não há garantia de que obteremos o mesmo valor duas vezes.

Naturalmente, além de tornar grande a probabilidade de obter um elemento $x\in A_1$ a partir da medição, também gostaríamos de escolher $t$ o menor possível, porque $t$ aplicações da operação $G$ requerem $t$ consultas à função $f$. Como queremos que $\sin( (2t + 1) \theta)$ seja próximo de $1$ em valor absoluto, uma forma natural de fazer isso é escolher $t$ de forma que

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

Isolando $t$, obtemos

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

É claro que $t$ deve ser um inteiro, portanto não necessariamente conseguiremos atingir exatamente esse valor — mas o que podemos fazer é tomar o inteiro mais próximo desse valor, que é

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Esse é o número recomendado de iterações para o algoritmo de Grover. À medida que prosseguirmos com a análise, veremos que a proximidade desse inteiro em relação ao valor-alvo afeta naturalmente o desempenho do algoritmo.

(A título de observação: se o valor-alvo $\pi/(4\theta) - 1/2$ estiver exatamente no meio entre dois inteiros, esta expressão de $t$ é o que obtemos ao arredondar para cima. Poderíamos, alternativamente, arredondar para baixo, o que faz sentido pois significa uma consulta a menos — mas isso é secundário e sem importância para o propósito desta lição.)

Lembrando que o valor do ângulo $\theta$ é dado pela fórmula

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

vemos que o número recomendado de iterações $t$ depende do número de strings em $A_1$. Isso representa um desafio se não soubermos quantas soluções temos, como discutiremos mais adiante.

Busca única

Primeiro, vamos nos concentrar na situação em que existe uma única string $x$ tal que $f(x)=1$. Outra forma de dizer isso é que estamos considerando uma instância do problema de Busca única. Nesse caso, temos

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

que pode ser convenientemente aproximado como

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

quando $N$ se torna grande. Se substituirmos $\theta = 1/\sqrt{N}$ na expressão

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

obtemos

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Lembrando que $t$ é não apenas o número de vezes que a operação $G$ é executada, mas também o número de consultas à função $f$ exigido pelo algoritmo, vemos que estamos no caminho certo para obter um algoritmo que requer $O(\sqrt{N})$ consultas.

Agora investigaremos quão bem a escolha recomendada de $t$ funciona. A probabilidade de que a medição final resulte na solução única pode ser expressa explicitamente como

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

O primeiro argumento, $N,$ refere-se ao número de itens sobre os quais estamos buscando, e o segundo argumento, que é $1$ neste caso, refere-se ao número de soluções. Um pouco mais adiante usaremos a mesma notação de forma mais geral, onde há múltiplas soluções.

Aqui está uma tabela das probabilidades de sucesso para valores crescentes de $N = 2^n$.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Observe que essas probabilidades não são estritamente crescentes. Em particular, temos uma anomalia interessante quando $N=4$, onde obtemos uma solução com certeza. Pode-se, no entanto, provar em geral que

$$p(N,1) \geq 1 - \frac{1}{N}$$

para todo $N$, portanto a probabilidade de sucesso tende a $1$ no limite conforme $N$ se torna grande, como os valores acima parecem sugerir. Isso é ótimo!

Observe, porém, que mesmo um limite fraco como $p(N,1) \geq 1/2$ estabelece a utilidade do algoritmo de Grover. Para qualquer resultado de medição $x$ que obtenhamos ao executar o procedimento, sempre podemos verificar se $f(x) = 1$ usando uma única consulta a $f$. E se deixarmos de obter a string única $x$ para a qual $f(x) = 1$ com probabilidade de no máximo $1/2$ ao executar o procedimento uma vez, então após $m$ execuções independentes do procedimento teremos deixado de obter essa string única $x$ com probabilidade de no máximo $2^{-m}$. Ou seja, usando $O(m \sqrt{N})$ consultas a $f$, obteremos a solução única $x$ com probabilidade de pelo menos $1 - 2^{-m}$. O uso do limite mais preciso $p(N,1) \geq 1 - 1/N$ revela que a probabilidade de encontrar $x\in A_1$ usando esse método é na verdade pelo menos $1 - N^{-m}$.

Múltiplas soluções

À medida que o número de elementos em $A_1$ varia, o ângulo $\theta$ também varia, o que pode ter um efeito significativo na probabilidade de sucesso do algoritmo. Por brevidade, vamos escrever $s = \vert A_1 \vert$ para denotar o número de soluções, e como antes assumiremos que $s\geq 1$.

Como exemplo motivador, vamos imaginar que temos $s = 4$ soluções em vez de uma única solução, como consideramos acima. Isso significa que

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

que é aproximadamente o dobro do ângulo que tínhamos no caso $\vert A_1 \vert = 1$ quando $N$ é grande. Suponha que, por desconhecimento, escolhêssemos o mesmo valor de $t$ que no cenário de solução única:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

O efeito será catastrófico, como a seguinte tabela de probabilidades revela.

$$\begin{array}{ll} N & \text{Probabilidade de sucesso}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Desta vez, a probabilidade de sucesso tende a $0$ conforme $N$ tende ao infinito. Isso acontece porque estamos efetivamente girando duas vezes mais rápido do que quando havia uma solução única, de modo que acabamos ultrapassando o alvo $\vert A_1\rangle$ e pousando próximo de $-\vert A_0\rangle$.

Porém, se em vez disso usarmos a escolha recomendada de $t$, que é

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

para

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

então o desempenho será melhor. Para ser mais preciso, usar essa escolha de $t$ leva ao sucesso com alta probabilidade.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Generalizando o que foi afirmado anteriormente, pode-se provar que

$$p(N,s) \geq 1 - \frac{s}{N},$$

onde estamos usando a notação sugerida anteriormente: $p(N,s)$ denota a probabilidade de que o algoritmo de Grover executado por $t$ iterações revele uma solução quando há $s$ soluções no total dentre $N$ possibilidades.

Esse limite inferior de $1 - s/N$ sobre a probabilidade de sucesso é ligeiramente peculiar, pois mais soluções implica um limite inferior pior — mas sob a suposição de que $s$ é significativamente menor que $N$, concluímos, ainda assim, que a probabilidade de sucesso é razoavelmente alta. Como antes, o simples fato de que $p(N,s)$ é razoavelmente grande implica a utilidade do algoritmo.

Também acontece que

$$p(N,s) \geq \frac{s}{N}.$$

Esse limite inferior descreve a probabilidade de que uma string $x\in\Sigma^n$ selecionada uniformemente ao acaso seja uma solução — portanto o algoritmo de Grover sempre se sai pelo menos tão bem quanto um palpite aleatório. (De fato, quando $t=0$, o algoritmo de Grover é um palpite aleatório.)

Agora vamos analisar o número de iterações (e portanto o número de consultas)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

para

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

Para todo $\alpha \in [0,1]$, vale que $\sin^{-1}(\alpha)\geq \alpha$, e portanto

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Isso implica que

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Isso se traduz em uma economia no número de consultas conforme $s$ cresce. Em particular, o número de consultas necessário é

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Número desconhecido de soluções

Se o número de soluções $s = \vert A_1 \vert$ é desconhecido, então uma abordagem diferente é necessária, pois nessa situação não temos conhecimento de $s$ para informar nossa escolha de $t$. Existem, de fato, múltiplas abordagens.

Uma abordagem simples é escolher

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

uniformemente ao acaso. Selecionar $t$ dessa forma sempre encontra uma solução (assumindo que uma exista) com probabilidade maior que 40%, embora isso não seja óbvio e requeira uma análise que não será incluída aqui. Faz sentido, no entanto, especialmente quando pensamos no quadro geométrico: girar o estado de $\mathsf{Q}$ um número aleatório de vezes dessa forma não é diferente de escolher um vetor unitário aleatório no espaço gerado por $\vert A_0\rangle$ e $\vert A_1\rangle$, para o qual é provável que o coeficiente de $\vert A_1\rangle$ seja razoavelmente grande. Repetindo esse procedimento e verificando o resultado da mesma forma descrita anteriormente, a probabilidade de encontrar uma solução pode ser tornada muito próxima de $1$.

Existe um método refinado que encontra uma solução quando ela existe usando $O(\sqrt{N/s})$ consultas, mesmo quando o número de soluções $s$ não é conhecido, e requer $O(\sqrt{N})$ consultas para determinar que não há soluções quando $s=0$.

A ideia básica é escolher $t$ uniformemente ao acaso do conjunto $\{1,\ldots,T\}$ iterativamente, para valores crescentes de $T$. Em particular, podemos começar com $T = 1$ e aumentá-lo exponencialmente, sempre encerrando o processo assim que uma solução for encontrada e limitando $T$ de modo a não desperdiçar consultas quando não houver solução. O processo aproveita o fato de que menos consultas são necessárias quando mais soluções existem. É necessário, no entanto, algum cuidado para equilibrar a taxa de crescimento de $T$ com a probabilidade de sucesso em cada iteração. (Tomar $T \leftarrow \lceil \frac{5}{4}T\rceil$ funciona, por exemplo, como uma análise revela. Dobrar $T$, porém, não funciona — isso acaba sendo um aumento rápido demais.)

Os casos triviais

Ao longo da análise que acabamos de realizar, assumimos que o número de soluções é diferente de zero. De fato, ao nos referirmos aos vetores

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

implicitamente assumimos que $A_0$ e $A_1$ são ambos não vazios. Aqui consideraremos brevemente o que acontece quando um desses conjuntos é vazio.

Antes de nos preocuparmos com uma análise, vamos observar o óbvio: se toda string $x\in\Sigma^n$ é uma solução, veremos uma solução ao medir; e quando não há soluções, não veremos nenhuma. Em certo sentido, não há necessidade de ir mais fundo que isso.

Podemos, no entanto, verificar rapidamente a matemática para esses casos triviais. A situação em que um dos conjuntos $A_0$ e $A_1$ é vazio ocorre quando $f$ é constante; $A_1$ é vazio quando $f(x) = 0$ para todo $x\in\Sigma^n,$ e $A_0$ é vazio quando $f(x) = 1$ para todo $x\in\Sigma^n.$ Isso significa que

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

e portanto

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Portanto, independentemente do número de iterações $t$ que realizarmos nesses casos, as medições sempre revelarão uma string aleatória uniforme $x\in\Sigma^n$.