Algoritmo de Grover

Em computação quântica, o algoritmo de Grover, também conhecido como algoritmo de busca quântica, é um algoritmo quântico para busca não estruturada que encontra com alta probabilidade a única entrada para uma função de caixa preta que produz um determinado valor de saída, usando apenas ${\displaystyle O({\sqrt {N}})}$ avaliações da função, onde ${\displaystyle N}$ é o tamanho do domínio da função. Ele foi concebido por Lov Grover em 1996.

O problema análogo na computação clássica teria uma complexidade de consulta de ${\displaystyle O(N)}$ (isto é, a função teria de ser avaliada ${\displaystyle O(N)}$ vezes: não existe abordagem melhor do que testar todos os valores de entrada um após o outro, o que, em média, leva ${\displaystyle N/2}$ passos).

Charles H. Bennett, Ethan Bernstein, Gilles Brassard e Umesh Vazirani provaram que qualquer solução quântica para o problema precisa avaliar a função ${\displaystyle \Omega ({\sqrt {N}})}$ vezes, logo o algoritmo de Grover é assintoticamente ótimo. Uma vez que os algoritmos clássicos para problemas NP-completos requerem um número exponencial de passos, e o algoritmo de Grover fornece, no máximo, uma aceleração quadrática sobre a solução clássica para a busca não estruturada, isso sugere que o algoritmo de Grover, por si só, não fornecerá soluções em tempo polinomial para problemas NP-completos (já que a raiz quadrada de uma função exponencial continua sendo uma função exponencial, não polinomial).

Ao contrário de outros algoritmos quânticos, que podem fornecer aceleração exponencial sobre suas contrapartes clássicas, o algoritmo de Grover fornece apenas uma aceleração quadrática. No entanto, mesmo uma aceleração quadrática é considerável quando ${\displaystyle N}$ é grande, e o algoritmo de Grover pode ser aplicado para acelerar amplas classes de algoritmos. O algoritmo de Grover poderia quebrar por força bruta uma chave criptográfica simétrica de 128 bits em aproximadamente 2⁶⁴ iterações, ou uma chave de 256 bits em cerca de 2¹²⁸ iterações. Porém, pode não ser o caso de que o algoritmo de Grover represente um risco significativamente maior à criptografia do que os algoritmos clássicos existentes.

Aplicações e limitações

O algoritmo de Grover, junto com variantes como a amplificação de amplitude, pode ser usado para acelerar uma ampla gama de algoritmos. Em particular, algoritmos para problemas NP-completos que contêm buscas exaustivas como uma sub-rotina podem ser acelerados pelo algoritmo de Grover. O melhor algoritmo teórico atual, em termos de complexidade de pior caso, para o 3SAT é um desses exemplos. Problemas genéricos de satisfação de restrições também veem acelerações quadráticas com o algoritmo de Grover. Esses algoritmos não exigem que a entrada seja dada na forma de um oráculo, já que o algoritmo de Grover é aplicado com uma função explícita, por exemplo, a função que verifica se um conjunto de bits satisfaz uma instância do 3SAT. No entanto, não está claro se o algoritmo de Grover poderia acelerar os melhores algoritmos práticos para esses problemas.

O algoritmo de Grover também pode fornecer acelerações comprováveis para problemas de caixa preta na complexidade de consulta quântica, incluindo a distinção de elementos e o problema da colisão (resolvido com o algoritmo de Brassard–Høyer–Tapp). Nestes tipos de problemas, trata-se a função oráculo f como um banco de dados, e o objetivo é usar a consulta quântica a essa função o menor número de vezes possível.

Descrição do problema

Como entrada para o algoritmo de Grover, suponha que tenhamos uma função ${\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}$. Na analogia do "banco de dados não estruturado", o domínio representa os índices de um banco de dados, e ${\displaystyle f(x)=1}$ se o dado que ${\displaystyle x}$ aponta satisfaz o critério de busca. Assumimos adicionalmente que apenas um índice satisfaz ${\displaystyle f(x)=1}$, e chamamos esse índice de ${\displaystyle \omega }$. Nosso objetivo é identificar ${\displaystyle \omega }$.

Podemos acessar ${\displaystyle f}$ com uma sub-rotina (às vezes chamada de oráculo) na forma de um operador unitário ${\displaystyle U_{\omega }}$ que age da seguinte forma:

$${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{para }}x=\omega {\text{, isto é, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{para }}x\neq \omega {\text{, isto é, }}f(x)=0.\end{cases}}}$$

Isso utiliza o espaço de estados ${\displaystyle {\mathcal {H}}}$ de ${\displaystyle N}$ dimensões, fornecido por um registrador com ${\displaystyle n=\lceil \log _{2}N\rceil }$ qubits. Isso é frequentemente escrito como:

$${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}$$

O algoritmo de Grover retorna ${\displaystyle \omega }$ com probabilidade de pelo menos ${\displaystyle 1/2}$ utilizando ${\displaystyle O({\sqrt {N}})}$ aplicações de ${\displaystyle U_{\omega }}$. Esta probabilidade pode se tornar arbitrariamente grande rodando-se o algoritmo de Grover múltiplas vezes. Se alguém rodar o algoritmo de Grover até que ${\displaystyle \omega }$ seja encontrado, o número esperado de aplicações continuará sendo ${\displaystyle O({\sqrt {N}})}$, uma vez que, em média, ele será executado apenas duas vezes.

Algoritmo

Os passos do algoritmo de Grover são dados a seguir:

1. Inicialize o sistema na superposição uniforme sobre todos os estados
   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$
2. Realize a seguinte "iteração de Grover" ${\displaystyle r(N)}$ vezes:
   1. Aplique o operador ${\displaystyle U_{\omega }}$
   2. Aplique o operador de difusão de Grover ${\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}$
3. Meça o estado quântico resultante na base computacional.

Para o valor corretamente escolhido de ${\displaystyle r}$, a saída será ${\displaystyle |\omega \rangle }$ com probabilidade aproximando-se de 1 para N ≫ 1. A análise mostra que esse valor ideal para ${\displaystyle r(N)}$ satisfaz ${\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}$.

Implementar as etapas deste algoritmo pode ser feito usando um número de portas lineares no número de qubits. Portanto, a complexidade de portas desse algoritmo é ${\displaystyle O(\log(N)r(N))}$, ou ${\displaystyle O(\log(N))}$ por iteração.

Prova geométrica

Há uma interpretação geométrica do algoritmo de Grover, oriunda da observação de que o estado quântico do algoritmo de Grover permanece num subespaço bidimensional após cada passo. Considere o plano gerado por ${\displaystyle |s\rangle }$ e ${\displaystyle |\omega \rangle }$; equivalentemente, o plano gerado por ${\displaystyle |\omega \rangle }$ e o ket perpendicular ${\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }$.

O algoritmo de Grover começa com o ket inicial ${\displaystyle |s\rangle }$, que se encontra no subespaço. O operador ${\displaystyle U_{\omega }}$ é uma reflexão no hiperplano ortogonal a ${\displaystyle |\omega \rangle }$ para vetores no plano gerado por ${\displaystyle |s'\rangle }$ e ${\displaystyle |\omega \rangle }$, isto é, ele atua como uma reflexão através de ${\displaystyle |s'\rangle }$. Isto pode ser visto escrevendo ${\displaystyle U_{\omega }}$ na forma de uma reflexão de Householder:

$${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}$$

O operador ${\displaystyle U_{s}=2|s\rangle \langle s|-I}$ é uma reflexão através de ${\displaystyle |s\rangle }$. Ambos os operadores ${\displaystyle U_{s}}$ e ${\displaystyle U_{\omega }}$ levam estados no plano gerado por ${\displaystyle |s'\rangle }$ e ${\displaystyle |\omega \rangle }$ para estados no mesmo plano. Portanto, o algoritmo de Grover permanece neste plano por toda a sua execução.

É simples verificar que o operador ${\displaystyle U_{s}U_{\omega }}$ de cada iteração de Grover gira o vetor de estado por um ângulo de ${\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}$. Assim, com iterações suficientes, podemos girar do estado inicial ${\displaystyle |s\rangle }$ até o estado de saída desejado ${\displaystyle |\omega \rangle }$. O ket inicial está próximo do estado ortogonal a ${\displaystyle |\omega \rangle }$:

$${\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}$$

Em termos geométricos, o ângulo ${\displaystyle \theta /2}$ entre ${\displaystyle |s\rangle }$ e ${\displaystyle |s'\rangle }$ é dado por

$${\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}$$

Nós precisamos parar quando o vetor de estado passar perto de ${\displaystyle |\omega \rangle }$; depois disso, iterações subsequentes giram o vetor de estado para longe de ${\displaystyle |\omega \rangle }$, reduzindo a probabilidade de obter a resposta correta. A probabilidade exata de medir a resposta correta é

$${\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}$$

onde r é o número (inteiro) de iterações de Grover. O tempo mais curto em que conseguimos uma medição quase ótima é, portanto, ${\displaystyle r\approx \pi {\sqrt {N}}/4}$.

Prova algébrica

Para completar a análise algébrica, precisamos descobrir o que acontece quando aplicamos repetidamente ${\displaystyle U_{s}U_{\omega }}$. Uma maneira natural de fazer isso é através da análise de autovalores de uma matriz. Note que durante todo o cálculo, o estado do algoritmo é uma combinação linear de ${\displaystyle s}$ e ${\displaystyle \omega }$. Podemos escrever a ação de ${\displaystyle U_{s}}$ e ${\displaystyle U_{\omega }}$ no espaço gerado por ${\displaystyle \{|s\rangle ,|\omega \rangle \}}$ como:

${\displaystyle {\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}}$

Portanto, na base ${\displaystyle \{|\omega \rangle ,|s\rangle \}}$ (que não é ortogonal nem é base do espaço todo) a ação ${\displaystyle U_{s}U_{\omega }}$ de aplicar ${\displaystyle U_{\omega }}$ seguido de ${\displaystyle U_{s}}$ é dada pela matriz

$${\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}$$

Esta matriz, por acaso, tem uma Forma de Jordan muito conveniente. Se definirmos ${\displaystyle t=\arcsin(1/{\sqrt {N}})}$, ela é

$${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$$

onde ${\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}$

Segue que a r-ésima potência da matriz (correspondente a r iterações) é

$${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$$

Usando essa forma, podemos usar identidades trigonométricas para calcular a probabilidade de observar ω após as r iterações mencionadas na seção anterior,

$${\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}$$

Alternativamente, é razoável imaginar que um tempo quase ótimo para a distinção seria quando os ângulos 2rt e −2rt estivessem o mais distantes possível, o que corresponde a ${\displaystyle 2rt\approx \pi /2}$, ou ${\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}$. O sistema estará então no estado

$${\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}$$

Um pequeno cálculo mostra agora que a observação produz a resposta correta ω com erro ${\displaystyle O\left({\frac {1}{N}}\right)}$.

Extensões e variantes

Otimalidade

O algoritmo de Grover é ótimo a menos de fatores subconstantes. Ou seja, qualquer algoritmo que acesse o banco de dados utilizando apenas o operador U_ω deverá aplicar U_ω pelo menos uma fração ${\displaystyle 1-o(1)}$ das vezes que o algoritmo de Grover o faz. A extensão do algoritmo de Grover para k entradas correspondentes, π(N/k)^1/2/4, também é ótima. Este resultado é importante para entender os limites da computação quântica.

Se o problema de busca de Grover fosse solucionável com log^c N aplicações de U_ω, isso implicaria que NP estaria contido em BQP, transformando problemas em NP para problemas do tipo de busca de Grover. A otimalidade do algoritmo de Grover sugere que computadores quânticos não são capazes de resolver problemas NP-Completos em tempo polinomial e, portanto, NP não está contido em BQP.

Demonstrou-se que uma classe de computadores quânticos não-locais de variáveis ocultas poderia implementar a pesquisa num banco de dados de ${\displaystyle N}$ itens em, no máximo, ${\displaystyle O({\sqrt[{3}]{N}})}$ passos. Isso é mais rápido do que os ${\displaystyle O({\sqrt {N}})}$ passos levados pelo algoritmo de Grover.

Ver também

• Amplificação de amplitude
• Algoritmo de Brassard–Høyer–Tapp (para resolver o problema da colisão)
• Algoritmo de Shor (para fatoração)
• Busca de passeio quântico

Referências

Bibliografia

• Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
• Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769–777, 2001. Pedagogical review of the algorithm and its history.
• Grover L.K.: QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today The Sciences, July/August 1999, pp. 24–30.
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• What's a Quantum Phone Book?, Lov Grover, Lucent Technologies

Ligações externas

O Wikiquote tem citações relacionadas a Algoritmo de Grover.

• Davy Wybiral. «Quantum Circuit Simulator». Consultado em 13 de janeiro de 2017. Cópia arquivada em 16 de janeiro de 2017 
• Craig Gidney (5 de março de 2013). «Grover's Quantum Search Algorithm». Consultado em 8 de março de 2013. Cópia arquivada em 17 de novembro de 2020 
• François Schwarzentruber (18 de maio de 2013). «Grover's algorithm» 
• Alexander Prokopenya. «Quantum Circuit Implementing Grover's Search Algorithm». Wolfram Alpha 
• Hazewinkel, Michiel, ed. (2001), «Quantum computation, theory of», Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer 
• Roberto Maestre (11 de maio de 2018). «Grover's Algorithm implemented in R and C». GitHub 
• Bernhard Ömer. «QCL - A Programming Language for Quantum Computers». Consultado em 30 de abril de 2022. Implemented in /qcl-0.6.4/lib/grover.qcl 

• Portal das tecnologias de informação