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 que $f$ tenha alguma 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$ para a qual $f$ assume o valor $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, na qual temos a garantia de 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.