Descrição do algoritmo de Grover

Nesta seção, vamos descrever o algoritmo de Grover. Começaremos discutindo as portas de consulta de fase e como construí-las, seguidas da descrição do próprio algoritmo de Grover. Por fim, discutiremos brevemente como esse algoritmo é naturalmente aplicado à busca.

Portas de consulta de fase

O algoritmo de Grover faz uso de operações conhecidas como portas de consulta de fase. Em contraste com uma porta de consulta comum $U_f$, definida para uma dada função $f$ da maneira usual descrita anteriormente, uma porta de consulta de fase para a função $f$ é definida como

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

para toda string $x\in\Sigma^n$.

A operação $Z_f$ pode ser implementada usando uma única porta de consulta $U_f$, como sugere este diagrama:

Essa implementação faz uso do fenômeno de phase kickback e requer que um qubit de espaço de trabalho, inicializado no estado $\vert -\rangle,$ esteja disponível. Esse qubit permanece no estado $\vert - \rangle$ após a conclusão da implementação, podendo ser reutilizado (para implementar portas $Z_f$ subsequentes, por exemplo) ou simplesmente descartado.

Além da operação $Z_f$, também faremos uso de uma porta de consulta de fase para a função OR de $n$ bits, definida da seguinte forma para cada string $x\in\Sigma^n$.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Explicitamente, a porta de consulta de fase para a função OR de $n$ bits opera da seguinte maneira:

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

Para deixar claro, é assim que $Z_{\mathrm{OR}}$ opera sobre estados da base padrão; seu comportamento em estados arbitrários é determinado a partir dessa expressão pela linearidade.

A operação $Z_{\mathrm{OR}}$ pode ser implementada como um circuito quântico começando com um circuito booleano para a função OR, depois construindo uma operação $U_{\mathrm{OR}}$ (ou seja, uma porta de consulta padrão para a função OR de $n$ bits) usando o procedimento descrito na lição Fundamentos algorítmicos quânticos, e finalmente uma operação $Z_{\mathrm{OR}}$ usando o fenômeno de phase kickback conforme descrito acima. Note que a operação $Z_{\mathrm{OR}}$ não depende da função $f$ e, portanto, pode ser implementada por um circuito quântico sem nenhuma porta de consulta.

Descrição do algoritmo

Agora que temos as duas operações $Z_f$ e $Z_{\mathrm{OR}}$, podemos descrever o algoritmo de Grover.

O algoritmo faz referência a um número $t$, que é o número de iterações que ele executa (e, portanto, o número de consultas à função $f$ que ele requer). Esse número $t$ não é especificado pelo algoritmo de Grover conforme o estamos descrevendo, e discutiremos mais adiante na lição como ele pode ser escolhido.

Algoritmo de Grover

1. Inicialize um registrador de $n$ qubits $\mathsf{Q}$ no estado todos-zero $\vert 0^n \rangle$ e depois aplique uma operação de Hadamard a cada qubit de $\mathsf{Q}$.
2. Aplique $t$ vezes a operação unitária $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ ao registrador $\mathsf{Q}$
3. Meça os qubits de $\mathsf{Q}$ com respeito a medições da base padrão e produza a string resultante.

A operação $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ iterada no passo 2 será chamada de operação de Grover ao longo do restante desta lição. Aqui está uma representação em circuito quântico da operação de Grover quando $n=7\!:$

Nesse diagrama, a operação $Z_f$ é representada como sendo maior do que $Z_{\mathrm{OR}}$ como uma dica visual informal para sugerir que ela tende a ser a operação mais custosa. Em particular, quando estamos trabalhando dentro do modelo de consulta, $Z_f$ requer uma consulta enquanto $Z_{\mathrm{OR}}$ não requer nenhuma consulta. Se em vez disso tivermos um circuito booleano para a função $f$ e o convertermos em um circuito quântico para $Z_f,$ podemos razoavelmente esperar que o circuito quântico resultante seja maior e mais complexo do que um para $Z_{\mathrm{OR}}.$

Aqui está um diagrama de um circuito quântico para o algoritmo completo quando $n=7$ e $t=3$. Para valores maiores de $t$, basta inserir instâncias adicionais da operação de Grover imediatamente antes das medições.

Aplicação à busca

O algoritmo de Grover pode ser aplicado ao problema de Busca da seguinte forma:

• Escolha o número $t$ no passo 2. (Isso é discutido mais adiante na lição.)

• Execute o algoritmo de Grover na função $f$, usando qualquer escolha que fizermos para $t$, para obter uma string $x\in\Sigma^n$.

• Consulte a função $f$ na string $x$ para verificar se é uma solução válida:

  • Se $f(x) = 1$, então encontramos uma solução, e podemos parar e retornar $x$.

  • Caso contrário, se $f(x) = 0$, podemos executar o procedimento novamente, possivelmente com uma escolha diferente para $t$, ou podemos decidir desistir e produzir "nenhuma solução."

Depois de analisarmos como o algoritmo de Grover funciona, veremos que tomando $t = O(\sqrt{N})$, obtemos uma solução para o nosso problema de busca (se existir alguma) com alta probabilidade.