Como o oráculo no algoritmo de pesquisa de Grover é implementado?

O algoritmo de pesquisa de Grover fornece uma aceleração quadrática comprovável para pesquisa de banco de dados não classificada. O algoritmo é geralmente expresso pelo seguinte circuito quântico:

Na maioria das representações, uma parte crucial do protocolo é o "oracle gate" $U_\omega$ , que "magicamente" executa a operação $|x\rangle\mapsto(-1)^{f(x)}|x\rangle$ . No entanto, muitas vezes não é dito o quão difícil seria realizar esse portão. De fato, pode parecer que esse uso de um "oráculo" seja apenas uma maneira de varrer as dificuldades para debaixo do tapete.

Como sabemos se uma operação tão oracular é realmente realizável? E se sim, qual é a sua complexidade (por exemplo, em termos de complexidade da decomposição de portas)?

A função $f$ é simplesmente uma função booleana arbitrária de uma sequência de bits: $f\colon \{0,1\}^n \to \{0,1\}$ . Para aplicativos que quebram criptografia, como [1] , [2] ou [3] , isso não é realmente uma 'pesquisa de banco de dados', o que exigiria o armazenamento de todo o banco de dados como um circuito quântico de alguma forma, mas uma função

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $\operatorname{SHA-256}(x) = y$;} \\ 0, & \text{otherwise,} \end{cases} \end{equation*}$$

para $y$ fixo , que não possui estrutura, podemos explorar para uma pesquisa clássica, diferentemente, digamos, da função

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $2^x \equiv y \pmod{2^{2048} - 1942289}$}, \\ 0, & \text{otherwise}, \end{cases} \end{equation*}$$

que possui uma estrutura que pode ser explorada para invertê-la mais rapidamente, mesmo em um computador clássico.

A questão do custo específico não pode ser respondida em geral porque pode ser qualquer circuito - é apenas uma questão de transformar um circuito quântico em um circuito clássico . Mas, geralmente, como no exemplo acima, a função é muito barata de avaliar em um computador clássico, portanto não deve representar um ônus particularmente oneroso para um computador quântico, para o qual todo o resto do algoritmo de Grover está dentro do seu orçamento.$f$f$f$

O único custo geral na parte superior de é um gate NÃO condicional extra onde é xor e um qubit adicional adicional para ele. Em particular, se tivermos um circuito construído em e no circuito para , se o aplicarmos a junto com um qubit auxiliar inicialmente no estado que$f$

$$C\colon \left|a\right> \left|b\right> \to \left|a\right> \left|a \oplus b\right>$$ $\oplus$ $$F\colon \left|x\right> \left|a\right> \lvert\text{junk}\rangle \mapsto \left|x\right> \left|a \oplus f(x)\right> \lvert\text{junk}'\rangle$$ $C$$f$$\left|x\right>$$\left|-\right> = H\left|1\right> = (1/\sqrt{2})(\left|0\right> - \left|1\right>)$$H$ é um portão Hadamard, então temos

$$\begin{align*} F\left|x\right> \left|-\right> \lvert\text{junk}\rangle &= \frac{1}{\sqrt{2}}\bigl( F\left|x\right> \left|0\right> \lvert\text{junk}\rangle - F\left|x\right> \left|1\right> \lvert\text{junk}\rangle \bigr) \\ &= \frac{1}{\sqrt{2}}\bigl( \left|x\right> \left|f(x)\right> \lvert\text{junk}'\rangle - \left|x\right> \left|1 \oplus f(x)\right> \lvert\text{junk}'\rangle \bigr). \end{align*}$$

Se então , simplificando, obtemos enquanto que se então , então e portanto, em geral$f(x) = 0$$1 \oplus f(x) = 1$

$$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = \left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ $f(x) = 1$$1 \oplus f(x) = 0$ $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = -\left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = (-1)^{f(x)} \left|x\right> \left|-\right> \lvert\text{junk}'\rangle.$$

Bem, o artigo original de Grover, "A mecânica quântica ajuda na busca de uma agulha no palheiro" afirma claramente, pressupõe que C (S) possa ser avaliado em um tempo constante. A pesquisa de Grover não está preocupada com a implementabilidade, mas com a redução polinomial do que é chamado de complexidade de consulta (quantas vezes você consulta o oracle, como um banco de dados clássico)

De fato, Alan Turing propôs o conceito de oráculo na computação para descrever construções para as quais uma descrição em um UTM pode não ser realizável (Wikipedia). Ele é , de alguma mágica sentido.

Mas, é claro, voltando à sua pergunta, como então fazemos o circuito para o algoritmo de pesquisa Grover (ou qualquer outro oracular)? Precisamos saber a resposta com antecedência para pesquisar o resultado? Bem, em certo sentido, você precisa. É exatamente nisso que as melhorias inteligentes na pesquisa Grover tentam trabalhar, de modo que, não precisamos saber a resposta exata com antecedência, mas algumas propriedades dela. Deixe-me ilustrar com um exemplo.

Para o problema de reconhecimento de padrões usando a pesquisa de Grover, se eu tiver 4 padrões em 2 qubits (00, 01, 10, 11) e quiser marcar e amplificar 11, a diagonal do meu oracle unitário deve ser como (1,1,1 , -1) para cuidar da mudança de fase pi da solução. Portanto, para essa implementação simples, para construir a unidade, você precisa conhecer a resposta completa com antecedência.

Uma melhoria inteligente da conclusão de padrões, se fornecida no artigo "Correspondência de padrões quânticos" de Mateas e Omar. Em essência, ele constrói tantos oráculos fixos quanto alfabetos no conjunto. Portanto, para nossa string binária, haverá um oráculo que marca todos os 1s e outro que marca todos os 0s. Os oráculos são invocados condicionalmente com base no que eu quero pesquisar. Se eu quiser pesquisar 11, chamo oracle 1 no LSqubit e oracle 1 novamente no MSqubit. No primeiro oráculo, eu amplificaria os estados (01, 11), ou seja, estados com LSQ como 1, e na segunda chamada, amplificaria (10, 11). Então, como você vê, 11 é o único estado que é amplificado duas vezes, terminando em uma maior probabilidade de medição. Embora o circuito quântico compilado mude com base no meu padrão de pesquisa de entrada, uma descrição de alto nível do algoritmo quântico permanece a mesma. Você pode pensar nos oráculos como chamadas de função com base em uma caixa de opção do conjunto de alfabeto invocado para cada caractere na cadeia de pesquisa.