Pular para o conteúdo principal

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 Uf,U_f, definida para uma dada função ff da maneira usual descrita anteriormente, uma porta de consulta de fase para a função ff é definida como

Zf∣x⟩=(−1)f(x)∣x⟩Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle

para toda string x∈Σn.x\in\Sigma^n.

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

A quantum circuit implementing a Z_f gate using one query gate together with the phase kickback phenomenon

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 ZfZ_f subsequentes, por exemplo) ou simplesmente descartado.

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

OR(x)={0x=0n1x≠0n\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 nn bits opera da seguinte maneira:

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n.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 ZORZ_{\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 ZORZ_{\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 UORU_{\mathrm{OR}} (ou seja, uma porta de consulta padrão para a função OR de nn bits) usando o procedimento descrito na lição Fundamentos algorítmicos quânticos, e finalmente uma operação ZORZ_{\mathrm{OR}} usando o fenômeno de phase kickback conforme descrito acima. Note que a operação ZORZ_{\mathrm{OR}} não tem dependência da função ff 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 ZfZ_f e ZOR,Z_{\mathrm{OR}}, podemos descrever o algoritmo de Grover.

O algoritmo faz referência a um número t,t, que é o número de iterações que ele executa (e, portanto, o número de consultas à função ff que ele requer). Esse número tt 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 nn qubits Q\mathsf{Q} no estado todos-zero ∣0n⟩\vert 0^n \rangle e depois aplique uma operação de Hadamard a cada qubit de Q.\mathsf{Q}.
  2. Aplique tt vezes a operação unitária G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f ao registrador Q\mathsf{Q}
  3. Meça os qubits de Q\mathsf{Q} com respeito a medições da base padrão e produza a string resultante.

A operação G=H⊗nZORH⊗nZfG = 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 ⁣:n=7\!:

A quantum circuit representation of the Grover operation

Nesse diagrama, a operação ZfZ_f é representada como sendo maior do que ZORZ_{\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, ZfZ_f requer uma consulta enquanto ZORZ_{\mathrm{OR}} não requer nenhuma consulta. Se em vez disso tivermos um circuito booleano para a função ff e o convertermos em um circuito quântico para Zf,Z_f, podemos razoavelmente esperar que o circuito quântico resultante seja maior e mais complexo do que um para ZOR.Z_{\mathrm{OR}}.

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

A quantum circuit for Grover's algorithm when t=3

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

  • Escolha o número tt no passo 2. (Isso é discutido mais adiante na lição.)
  • Execute o algoritmo de Grover na função f,f, usando qualquer escolha que fizermos para t,t, para obter uma string x∈Σn.x\in\Sigma^n.
  • Consulte a função ff na string xx para verificar se é uma solução válida:
    • Se f(x)=1,f(x) = 1, então encontramos uma solução, e podemos parar e produzir x.x.
    • Caso contrário, se f(x)=0,f(x) = 0, podemos executar o procedimento novamente, possivelmente com uma escolha diferente para t,t, ou podemos decidir desistir e produzir "nenhuma solução."

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