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 avaliações da função, onde é o tamanho do domínio da função. Ele foi concebido por Lov Grover em 1996.
Imagem: IBM España. · PDM · Openverse
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.
Criptografia
O algoritmo de Grover essencialmente resolve a tarefa de inversão de função. Em termos gerais, se temos uma função y = f ( x ) {\displaystyle y=f(x)} que pode ser avaliada em um computador quântico, o algoritmo de Grover nos permite calcular x {\displaystyle x} quando recebemos y {\displaystyle y} . Consequentemente, o algoritmo de Grover fornece amplas acelerações assintóticas para muitos tipos de ataques de força bruta em criptografia de chave simétrica, incluindo ataques de colisão e ataques de preimagem. No entanto, esse não é necessariamente o algoritmo mais eficiente; por exemplo, o algoritmo rho de Pollard é capaz de encontrar uma colisão no SHA-2 de forma mais eficiente que o algoritmo de Grover.
Limitações
O artigo original de Grover descrevia o algoritmo como um algoritmo de busca em banco de dados, e essa descrição ainda é comum. O banco de dados nessa analogia é uma tabela de todas as saídas da função, indexadas pela entrada correspondente. No entanto, esse banco de dados não é representado explicitamente. Em vez disso, um oráculo é invocado para avaliar um item pelo seu índice. Ler um banco de dados completo item por item e convertê-lo para essa representação pode demorar muito mais do que a busca de Grover em si. Para dar conta de tais efeitos, o algoritmo de Grover pode ser visto como resolvendo uma equação ou satisfazendo um problema de restrição. Nessas aplicações, o oráculo é uma forma de verificar a restrição e não está relacionado ao algoritmo de busca. Essa separação geralmente impede otimizações algorítmicas, ao passo que os algoritmos de busca convencionais frequentemente dependem dessas otimizações e evitam a busca exaustiva. Felizmente, uma implementação rápida de oráculo para o algoritmo de Grover é possível em muitos problemas de satisfação de restrições e otimização.
Imagem: PVParellada · BY-SA · Openverse
Como entrada para o algoritmo de Grover, suponha que tenhamos uma função f : { 0 , 1 , … , N − 1 } → { 0 , 1 } {\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 f ( x ) = 1 {\displaystyle f(x)=1} se o dado que x {\displaystyle x} aponta satisfaz o critério de busca. Assumimos adicionalmente que apenas um índice satisfaz f ( x ) = 1 {\displaystyle f(x)=1} , e chamamos esse índice de ω {\displaystyle \omega } . Nosso objetivo é identificar ω {\displaystyle \omega } . Podemos acessar f {\displaystyle f} com uma sub-rotina (às vezes chamada de oráculo) na forma de um operador unitário U ω {\displaystyle U_{\omega }} que age da seguinte forma: { U ω | x ⟩ = − | x ⟩ para x = ω , isto é, f ( x ) = 1 , U ω | x ⟩ = | x ⟩ para x ≠ ω , isto é, f ( x ) = 0. {\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}}}
Definição alternativa de oráculo
Esta seção compara o oráculo acima U ω {\displaystyle U_{\omega }} com um oráculo U f {\displaystyle U_{f}} . O U ω {\displaystyle U_{\omega }} é diferente do oráculo quântico padrão para uma função f {\displaystyle f} . Este oráculo padrão, denotado aqui como U f {\displaystyle U_{f}} , usa um sistema de qubits auxiliares (ancilla). A operação então representa uma inversão (porta NOT) no sistema principal condicionada ao valor de f(x) vindo do sistema auxiliar: { U f | x ⟩ | y ⟩ = | x ⟩ | ¬ y ⟩ para x = ω , isto é, f ( x ) = 1 , U f | x ⟩ | y ⟩ = | x ⟩ | y ⟩ para x ≠ ω , isto é, f ( x ) = 0 , {\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{para }}x=\omega {\text{, isto é, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{para }}x\neq \omega {\text{, isto é, }}f(x)=0,\end{cases}}}
Os passos do algoritmo de Grover são dados a seguir: Para o valor corretamente escolhido de r {\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 r ( N ) {\displaystyle r(N)} satisfaz r ( N ) ≤ ⌈ π 4 N ⌉ {\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 é O ( log ( N ) r ( N ) ) {\displaystyle O(\log(N)r(N))} , ou O ( log ( N ) ) {\displaystyle O(\log(N))} por iteração.
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 | s ⟩ {\displaystyle |s\rangle } e | ω ⟩ {\displaystyle |\omega \rangle } ; equivalentemente, o plano gerado por | ω ⟩ {\displaystyle |\omega \rangle } e o ket perpendicular | s ′ ⟩ = 1 N − 1 ∑ x ≠ ω | x ⟩ {\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 | s ⟩ {\displaystyle |s\rangle } , que se encontra no subespaço. O operador U ω {\displaystyle U_{\omega }} é uma reflexão no hiperplano ortogonal a | ω ⟩ {\displaystyle |\omega \rangle } para vetores no plano gerado por | s ′ ⟩ {\displaystyle |s'\rangle } e | ω ⟩ {\displaystyle |\omega \rangle } , isto é, ele atua como uma reflexão através de | s ′ ⟩ {\displaystyle |s'\rangle } . Isto pode ser visto escrevendo U ω {\displaystyle U_{\omega }} na forma de uma reflexão de Householder:
Para completar a análise algébrica, precisamos descobrir o que acontece quando aplicamos repetidamente U s U ω {\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 s {\displaystyle s} e ω {\displaystyle \omega } . Podemos escrever a ação de U s {\displaystyle U_{s}} e U ω {\displaystyle U_{\omega }} no espaço gerado por { | s ⟩ , | ω ⟩ } {\displaystyle \{|s\rangle ,|\omega \rangle \}} como: U s : a | ω ⟩ + b | s ⟩ ↦ [ | ω ⟩ | s ⟩ ] [ − 1 0 2 / N 1 ] [ a b ] . U ω : a | ω ⟩ + b | s ⟩ ↦ [ | ω ⟩ | s ⟩ ] [ − 1 − 2 / N 0 1 ] [ a b ] . {\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}}}
Múltiplas entradas correspondentes
Se, em vez de 1 entrada correspondente, houver k entradas correspondentes, o mesmo algoritmo funciona, mas o número de iterações deverá ser de π 4 N k {\textstyle {\frac {\pi }{4}}{\sqrt {\frac {N}{k}}}} em vez de π 4 N {\textstyle {\frac {\pi }{4}}{\sqrt {N}}} . Existem diversas maneiras de lidar com a situação se k for desconhecido. Uma solução simples tem desempenho ótimo a menos de um fator constante: execute o algoritmo de Grover repetidamente para valores de k cada vez menores, por exemplo, tomando k = N, N/2, N/4, ..., e assim por diante, tomando k = N / 2 t {\displaystyle k=N/2^{t}} para a iteração t até que uma entrada correspondente seja encontrada.
Busca parcial quântica
Uma modificação do algoritmo de Grover, chamada de busca parcial quântica, foi descrita por Grover e Radhakrishnan em 2004. Na busca parcial, não se tem o interesse em encontrar o endereço exato do item procurado, apenas os primeiros dígitos desse endereço. Equivalentemente, podemos pensar em "dividir" o espaço de busca em blocos e depois perguntar "em que bloco está o item procurado?". Em muitas aplicações, uma pesquisa assim rende informações suficientes se o endereço alvo contém a informação almejada. Por exemplo, usando a analogia dada por L. K. Grover, se tivermos uma lista de alunos organizada por classificação da turma, podemos estar interessados apenas em saber se um aluno está no percentil inferior 25%, 25–50%, 50–75% ou 75–100%.
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 1 − o ( 1 ) {\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 logc 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 N {\displaystyle N} itens em, no máximo, O ( N 3 ) {\displaystyle O({\sqrt[{3}]{N}})} passos. Isso é mais rápido do que os O ( N ) {\displaystyle O({\sqrt {N}})} passos levados pelo algoritmo de Grover.
