Algoritmo de pesquisa da Teoria de Grover
Neste artigo, você encontrará uma explicação teórica detalhada dos princípios matemáticos que fazem com que o algoritmo de Grover funcione.
Para uma implementação prática do algoritmo de Grover para resolver problemas matemáticos, consulte Implementar o algoritmo de pesquisa de Grover.
Declaração do problema
O algoritmo de Grover acelera a solução para pesquisas de dados não estruturados (ou problema de pesquisa), executando a pesquisa em menos etapas do que qualquer algoritmo clássico poderia. Qualquer tarefa de pesquisa pode ser expressa com uma função abstrata $f(x)$ que aceita itens de pesquisa $x$. Se o item $x$ for uma solução para a tarefa de pesquisa, então $f(x)=1$. Se o item $x$ não for uma solução, então $f(x)=0$. O problema de pesquisa consiste em localizar qualquer item $x_0$, tal que $f(x_0)=1$.
Qualquer problema que permita verificar se um determinado valor $x$ é uma solução válida (um "yes ou no problem") pode ser formulado em termos do problema de pesquisa. Estes são alguns exemplos:
- Problema de satisfação booliana: dado um conjunto de valores boolianos, o conjunto satisfaz uma determinada fórmula booliana?
- Problema do vendedor viajante: Qual é o loop mais curto possível que conecta todas as cidades?
- Problema de pesquisa de banco de dados: uma tabela de banco de dados contém o registro $x$?
- Problema de fatoração de inteiros: o número $N$ é divisível pelo número $x$?
A tarefa que o algoritmo de Grover pretende resolver pode ser expressa da seguinte maneira: dada uma função clássica $f(x):\{0,1\}^n \rightarrow\{0,1\}$, em que $n$ é o tamanho do bit do espaço de pesquisa, encontre uma entrada $x_0$ para a qual $f(x_0)=1$. A complexidade do algoritmo é medida pelo número de usos da função $f(x)$. De modo clássico, no pior cenário, temos que avaliar $f(x)$ um total de $N-1$ vezes, em que $N=2^n$, experimentando todas as possibilidades. Depois de $N-1$ elementos, esse precisa ser o último elemento. O algoritmo quântico de Grover pode resolver esse problema muito mais rapidamente, garantindo uma velocidade quadrática. A quadrática aqui implica que apenas cerca de $\sqrt{N}$ avaliações seriam necessárias, em comparação com $N$.
Estrutura do algoritmo
Suponha que há $N=2^n$ itens qualificados para a tarefa de pesquisa e eles são indexados atribuindo a cada item um inteiro de $0$ a $N-1$. Além disso, suponha que há $M$ entradas válidas diferentes, o que significa que há $M$ entradas para as quais $f(x)=1$. As etapas do algoritmo são as seguintes:
- Comece com um registro de $n$ qubits inicializados no estado $\ket{0}$.
- Prepare o registro em uma sobreposição uniforme aplicando $H$ a cada qubit do registro: $$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
- Aplique as seguintes operações ao registro $N_{\text{optimal}}$ número de vezes:
- A fase $O_f$ do oráculo que aplica uma mudança de fase condicional de $-1$ para os itens da solução.
- Aplique $H$ a cada qubit no registro.
- Uma mudança de fase condicional de $-1$ a cada estado de base computacional, exceto $\ket{0}$. Isso pode ser representado pela operação unitária $-O_0$, já que $O_0$ representa a mudança de fase condicional para $\ket{0}$ apenas.
- Aplique $H$ a cada qubit no registro.
- Meça o registro para obter o índice de um item que é uma solução com uma probabilidade muito alta.
- Verifique se é uma solução válida. Caso contrário, comece novamente.
$N_{\text{optimal}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$ é o número ideal de iterações que maximiza a probabilidade de obter o item correto medindo o registro.
Observação
A aplicação conjunta das etapas 3.b, 3.c e 3.d é geralmente conhecida como o operador de difusão de Grover .
A operação unitária geral aplicada ao registro é:
$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{ideal}}}H^{\otimes n}$$
Seguindo o estado do registro, passo a passo
Para ilustrar o processo, vamos seguir as transformações matemáticas do estado do registro para um caso simples no qual há apenas dois qubits e o elemento válido é $\ket{01}.$
O registro começa no estado:
$\ket{\text{register}}=\ket{{00}$
Depois de aplicar $H$ a cada qubit, o estado do registro se transforma em:
$\ket{\text{registrar}}=\frac{{1}{\sqrt{4}}\sum_{i \in \lbrace 0,1 \rbrace}^2\ket{i}=\frac12(\ket{00}+\ket{01}+\ket{{10}+\ket{11})$
Em seguida, o oráculo de fase é aplicado para obter:
$\ket{\text{register}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$
Em seguida, $H$ atua em cada qubit novamente para dar:
$\ket{\text{register}}=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$
Agora, a mudança de fase condicional é aplicada em todos os estados, exceto $\ket{00}$:
$\ket{\text{register}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$
Por fim, a primeira iteração Grover termina aplicando $H$ novamente para obter:
$\ket{\text{register}}=\ket{{01}$
Seguindo as etapas acima, o item válido é encontrado em apenas uma iteração. Como você verá mais tarde, isso ocorre porque para N=4 e um único item válido, o número ideal de vezes é $N_{\text{ideal}}=1$.
Explicação geométrica
Para ver por que o algoritmo de Grover funciona, vamos estudar o algoritmo de uma perspectiva geométrica. Supondo que haja $M$ soluções válidas, a superposição de todos os estados quânticos que não sejam uma solução para o problema de pesquisa:
$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$
A superposição de todos os estados que sejam uma solução para o problema de pesquisa:
$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$
Como bom e ruim são conjuntos mutuamente exclusivos porque um item não pode ser válido e não ser válido, os estados são ortogonais. Ambos os estados formam a base ortogonal de um plano no espaço de vetor. É possível usar esse plano para visualizar o algoritmo.
Agora, suponha que $\ket{\psi}$ seja um estado arbitrário que reside no plano, distribuído por $\ket{\text{bom}}$ e $\ket{\text{ruim}}$. Qualquer estado que estiver nesse plano pode ser expresso como:
$$\ket{\psi}=\alpha\ket{\text{good}} + \beta\ket{\text{bad}}$$
em que $\alpha$ e $\beta$ são números reais. Agora, vamos introduzir o operador de reflexão $R_ {\ket{\psi}}$, em que $\ket{\psi}$ é qualquer estado qubit que esteja no plano. O operador é definido como:
$$R_{\ket{\psi}}=2\ket{\psi}\bra{\psi}-\mathcal{I}$$
Ele é chamado de operador de reflexão sobre $\ket{\psi}$, pois pode ser interpretado geometricamente como reflexão sobre a direção de $\ket{\psi}$. Para vê-lo, use a base ortogonal do plano formado por $\ket{\psi}$ e seu complemento ortogonal $\ket{\psi^{\perp}}$. Qualquer estado $\ket{\xi}$ do plano pode ser decomposto de acordo com esta base:
$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$
Se uma pessoa aplicar o operador $R_{\ket{\psi}}$ a $\ket{\xi}$:
$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$
O operador $R_{\ket{\psi}}$ inverte o componente ortogonal para $\ket{\psi}$, mas deixa o componente $\ket{\psi}$ inalterado. Portanto, $R_{\ket{\psi}}$ é uma reflexão sobre $\ket{\psi}$.
O algoritmo de Grover, após a primeira aplicação de $H$ a cada qubit, começa com uma sobreposição uniforme de todos os estados. Isso pode ser escrito como:
$$\ket{\text{all}}=\sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$
E, portanto, o estado reside no plano. Observe que a probabilidade de obter um resultado correto ao medir a partir da superposição igual é boa $|\bra{\text{}}\ket{\text{para todos}}| ^ 2=M / N$, que é o que você esperaria de um palpite aleatório.
O$O_f$ do oráculo adiciona uma fase negativa a qualquer solução para o problema de pesquisa. Portanto, ele pode ser escrito como uma reflexão sobre o eixo $\ket{\text{ruim}}$:
$O_f = R_{\ket{\text{bad}}}= 2\ket{\text{bad}}\bra{\text{bad}} - \mathbb{I}$
De forma análoga, a mudança de fase condicional $O_0$ é apenas uma reflexão invertida sobre o estado $\ket{0}$:
$O_{0}= R_{\ket{0}}= -2\ket{{0}\bra{{0} + \mathbb{I}$
Sabendo disso, é fácil verificar se a operação de difusão Grover $-H^{\otimes n} O_{0} H^{\otimes n}$ também é um reflexo sobre o estado $\ket{all}$. Basta:
$-H^{\otimes n} O_{{0} H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathbb{I}H^{\otimes n}= 2\ket{\text{all}}\bra{\text{all}} - \mathbb{I}= R_{\ket{\text{all}}}$
Foi demonstrado que cada iteração do algoritmo de Grover é uma composição de dois reflexos $R_{\ket{\text{ruim}}}$ e $R_{\ket{\text{todos}}}$.
O efeito combinado de cada iteração de Grover é uma rotação no sentido anti-horário de um ângulo $2\theta$. Felizmente, o ângulo $\theta$ é fácil de encontrar. Como $\theta$ é apenas o ângulo entre $\ket{\text{todos}}$ e $\ket{\text{ruim}}$, podemos usar o produto escalar para encontrar o ângulo. É sabido que $\cos{\theta}=\braket{\text{todos}|\text{ruim}}$, então é necessário calcular $\braket{\text{todos}|\text{ruim}}$. Da decomposição de $\ket{\text{todos}}$ em termos de $\ket{\text{ruim}}$ e $\ket{\text{bom}}$, vemos que:
$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$
O ângulo entre o estado do registro e o $\ket{\text{estado bom}}$ diminui a cada iteração, resultando em uma maior probabilidade de medir um resultado válido. Para calcular essa probabilidade, você só precisa calcular $|\braket{\text{um bom}|\text{registro}}| ^ 2$. O ângulo entre $\ket{\text{good}}$ e $\ket{\text{register}}$ é denotado como $\gamma (k)$, onde $k$ é a contagem da iteração:
$\gamma = \frac{\pi}{2}-\theta -2k\theta =\frac{\pi}{{2} -(2k + 1) \theta $
Portanto, a probabilidade de sucesso é:
$$P(\text{success}) = \cos^2(\gamma(k)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$
Número ideal de iterações
Como a probabilidade de sucesso pode ser escrita como uma função do número de iterações, podemos encontrar o número de iterações $N_{\text{ideal}}$ calculando o menor inteiro positivo que (aproximadamente) maximiza a função de probabilidade de sucesso.
É sabido que $\sin^2{x}$ atinge o primeiro máximo para $x=\frac{\pi}{2}$, então:
$\frac{\pi}{{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$
Isso fornece:
$$k_{\text{optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 =\frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$
Em que, na última etapa, usamos o fato de que, $\arccos \sqrt{1-x}=\sqrt{x} + O(x^{3/2})$.
Portanto, você pode escolher $N_{\text{optimal}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\rfloor$.
Análise de complexidade
Na análise anterior, sabemos que $O\left(\sqrt{\frac{N}{M}}\right)$ consultas do oracle $O_f$ são necessárias para encontrar um item válido. No entanto, o algoritmo pode ser implementado com eficiência em termos de complexidade de tempo? $O_0$ se baseia em operações boolianas de computação em $n$ bits e é conhecido como passível de implementação usando $O(n)$ portas. Também temos duas camadas de $n$ portas Hadamard. Os dois componentes exigem, portanto, apenas $O(n)$ portas por iteração. $N=2^n$, então, consequentemente, $O(n)=O(log(N))$. Portanto, se $O\left(\sqrt{\frac{N}{M}}\right)$ iterações e $O(log(N))$ portões por iteração forem necessários, a complexidade do tempo total (sem levar em conta a implementação do oracle) é $O\left(\sqrt{\frac{N}{M}}log(N)\right)$.
A complexidade geral do algoritmo depende, em última análise, da complexidade da implementação do O_f$ oracle$. Se uma avaliação de função for muito mais complicada em um computador quântico do que em um clássico, o tempo de execução geral do algoritmo será mais longo no caso quântico, embora tecnicamente use menos consultas.
Referências
Se quiser continuar aprendendo o algoritmo de Grover, você pode verificar uma das seguintes fontes:
- Artigo original de Lov K. Grover
- Seção de algoritmos de busca quântica de Nielsen, M. A. & Chuang, I. L. (2010). Computação quântica e informações do Quantum.
- Algoritmo de Grover em Arxiv.org