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 obter 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

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

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:

1. Comece com um registro de $n$ qubits inicializados no estado $\ket{0}$.
2. 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$$
3. Aplique as seguintes operações ao registro $N_{\text{ideal}}$ vezes:
   1. A fase $O_f$ do oráculo que aplica uma mudança de fase condicional de $-1$ para os itens da solução.
   2. Aplique $H$ a cada qubit no registro.
   3. 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.
   4. Aplique $H$ a cada qubit no registro.
4. Meça o registro para obter o índice de um item que é uma solução com uma probabilidade muito alta.
5. 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 normalmente é conhecida na literatura como 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}.$

1. O registro é iniciado no estado: $$|\text{registro}\rangle=|00\rangle$$

2. Depois de aplicar $H$ a cada qubit, o estado do registro transforma-se em: $$|\text{register}\rangle=\frac{{1}{\sqrt{{4}}\sum_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$

3. Em seguida, a fase Oracle é aplicada para obter: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$

4. Em seguida, $H$ atua em cada qubit novamente para fornecer: $$|\text{register}\rangle=\frac12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})$$

5. Agora, a mudança de fase condicional é aplicada a todos os estados, exceto $\ket{00}$: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$

6. Por fim, a primeira iteração de Grover termina aplicando $H$ novamente para obter: $$|\text{register}\rangle=\ket{{01}$$

   Seguindo as etapas acima, o item válido é encontrado em apenas uma iteração. Como você verá posteriormente, isso ocorre porque para N=4 e um único item válido, $N_\text{optimal}=1$.

Explicação geométrica

Para ver por que o algoritmo de Grover funciona, vamos estudar o algoritmo de uma perspectiva geométrica. Permita que $\ket{\text{ruim}}$ seja a sobreposição de todos os estados que não são uma solução para o problema de pesquisa. Supondo que há $M$ soluções válidas, temos:

$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$

O estado $\ket{\text{bom}}$ é definido como a sobreposição de todos os estados que são 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 válido, os estados $\ket{\text{bom}}$ e $\ket{\text{ruim}}$ 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 é apenas $|\braket{\text{boa}|{\text{tudo}}}|^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}} - \mathcal{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} + \mathcal{I}$$

Sabendo esse fato, é fácil verificar se a operação de difusão Grover $-H^{\otimes n} O_0 H^{\otimes n}$ também é uma reflexão sobre o estado $\ket{todos}$. Basta:

$$-H^{\otimes n} O_0 H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathcal{I}H^{\otimes n}= 2\ket{\text{all}}\bra{\text{all}} - \mathcal{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{bom}}$ estado diminui a cada iteração, resultando em uma probabilidade maior de medir um resultado válido. Para calcular essa probabilidade, você só precisa calcular $|\braket{\text{um bom}|\text{registro}}|^2$. Denotando o ângulo entre $\ket{\text{good}}$ e $\ket{\text{register}}$$\gamma (k)$, em que $k$ é a contagem da iteração, obtemos:

$$\gamma (k) =\frac{\pi}{2}-\theta -k2\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}$ para ser $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 oracle $O_f$. Se uma avaliação de função for muito mais complicada em um computador quântico do que em um clássico, o runtime geral do algoritmo será mais longo no caso quântico, mesmo que tecnicamente, ele 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 pesquisa quântica da Nielsen, M. A. &Amp; Chuang, I. L. (2010). Computação quântica e informações do Quantum.
• Algoritmo de Grover em Arxiv.org

Próximas etapas

• Representação Intermediária Quântica
• Vetores e matrizes
• T portões e fábricas T
• Vários qubits