Busca não estruturada

Resumo

Vamos começar com uma descrição do problema que o algoritmo de Grover resolve. Como de costume, vamos usar $\Sigma = \{0,1\}$ para denotar o alfabeto binário ao longo desta discussão.

Suponha que

$$f:\Sigma^n \rightarrow \Sigma$$

é uma função de strings binárias de comprimento $n$ para bits. Vamos assumir que podemos computar essa função de forma eficiente, mas fora isso ela é arbitrária e não podemos contar com uma estrutura especial ou implementação específica que nos convenha.

O que o algoritmo de Grover faz é buscar uma string $x\in\Sigma^n$ para a qual $f(x) = 1.$ Vamos nos referir a strings assim como soluções para o problema de busca. Se houver múltiplas soluções, qualquer uma delas é considerada uma saída correta; se não houver nenhuma solução, uma resposta correta exige que relatemos que não existem soluções.

Essa tarefa é descrita como um problema de busca não estruturada porque não podemos contar com $f$ tendo nenhuma estrutura particular que facilite o processo. Não estamos buscando em uma lista ordenada nem dentro de alguma estrutura de dados especificamente projetada para facilitar a busca — estamos essencialmente procurando uma agulha no palheiro.

De forma intuitiva, podemos imaginar que temos um circuito booleano extremamente complicado que computa $f,$ e podemos facilmente executar esse circuito em uma string de entrada escolhida. Mas como o circuito é tão complicado, não temos como compreendê-lo simplesmente examinando-o (além da capacidade de avaliá-lo em strings de entrada escolhidas).

Uma forma de realizar essa tarefa de busca classicamente é simplesmente iterar por todas as strings $x\in\Sigma^n,$ avaliando $f$ em cada uma para verificar se é ou não uma solução. Daqui em diante, vamos escrever

$$N = 2^n$$

por conveniência. Há $N$ strings em $\Sigma^n,$ portanto iterar por todas elas requer $N$ avaliações de $f.$ Operando sob a premissa de que estamos limitados a avaliar $f$ em entradas escolhidas, isso é o melhor que podemos fazer com um algoritmo determinístico se quisermos garantir o sucesso. Com um algoritmo probabilístico, poderíamos esperar economizar tempo escolhendo strings de entrada aleatórias para $f,$ mas ainda precisaríamos de $O(N)$ avaliações de $f$ se quisermos que esse método tenha alta probabilidade de sucesso.

O algoritmo de Grover resolve esse problema de busca com alta probabilidade usando apenas $O(\sqrt{N})$ avaliações de $f.$ Para ser claro, essas avaliações de função devem ocorrer em superposição, de forma semelhante aos algoritmos de consulta discutidos na lição Algoritmos quânticos de consulta, incluindo o algoritmo de Deutsch, o algoritmo de Deutsch-Jozsa e o algoritmo de Simon. Ao contrário desses algoritmos, o algoritmo de Grover adota uma abordagem iterativa: ele avalia $f$ em superposições de strings de entrada e intercala essas avaliações com outras operações que têm o efeito de criar padrões de interferência, levando a uma solução com alta probabilidade (se existir) após $O(\sqrt{N})$ iterações.

Enunciado formal do problema

Vamos formalizar o problema que o algoritmo de Grover resolve usando o modelo de consulta de computação. Ou seja, vamos assumir que temos acesso à função $f:\Sigma^n\rightarrow\Sigma$ por meio de uma porta de consulta definida da maneira usual:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

para todo $x\in\Sigma^n$ e $a\in\Sigma.$ Essa é a ação de $U_f$ sobre estados da base computacional, e sua ação em geral é determinada pela linearidade.

Como discutido na lição Fundamentos algorítmicos quânticos, se temos um circuito booleano para computar $f,$ podemos transformar essa descrição do circuito booleano em um circuito quântico que implementa $U_f$ (usando algum número de qubits de espaço de trabalho que iniciam e encerram a computação no estado $\vert 0\rangle$). Assim, embora estejamos usando o modelo de consulta para formalizar o problema que o algoritmo de Grover resolve, ele não está limitado a esse modelo; podemos executar o algoritmo de Grover em qualquer função $f$ para a qual tenhamos um circuito booleano.

Aqui está um enunciado preciso do problema, que recebe o nome de Busca porque estamos procurando uma solução, ou seja, uma string $x$ que faz $f$ avaliar para $1.$

Busca

Entrada: uma função $f:\Sigma^n\rightarrow\Sigma$
Saída: uma string $x\in\Sigma^n$ satisfazendo $f(x) = 1,$ ou "sem solução" se nenhuma string $x$ com essa propriedade existir

Note que este não é um problema de promessa — a função $f$ é arbitrária. No entanto, será útil considerar a seguinte variante do problema com promessa, onde garantimos que há exatamente uma solução. Esse problema apareceu como um exemplo de problema de promessa na lição Algoritmos quânticos de consulta.

Busca única

Entrada: uma função da forma $f:\Sigma^n \rightarrow \Sigma$
Promessa: existe exatamente uma string $z\in\Sigma^n$ para a qual $f(z) = 1,$ com $f(x) = 0$ para todas as strings $x\neq z$
Saída: a string $z$

Note também que o problema Ou mencionado na mesma lição está intimamente relacionado à Busca. Nesse problema, o objetivo é simplesmente determinar se uma solução existe ou não, ao contrário de realmente encontrar uma solução.