Algoritmo de Simon

O algoritmo de Simon é um algoritmo de consulta quântica para um problema conhecido como problema de Simon. Trata-se de um problema de promessa com características semelhantes aos problemas de Deutsch-Jozsa e Bernstein-Vazirani, mas com especificidades diferentes.

O algoritmo de Simon é significativo porque oferece uma vantagem exponencial dos algoritmos quânticos sobre os clássicos (incluindo os probabilísticos), e a técnica que ele utiliza inspirou Peter Shor a descobrir um algoritmo quântico eficiente para a fatoração de inteiros.

Problema de Simon

A função de entrada para o problema de Simon tem a forma

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

para inteiros positivos $n$ e $m$. Poderíamos restringir nossa atenção ao caso $m = n$ em prol da simplicidade, mas há pouco a ganhar fazendo essa suposição — o algoritmo de Simon e sua análise são basicamente os mesmos de qualquer forma.

Problema de Simon

Entrada: uma função $f:\Sigma^n \rightarrow \Sigma^m$
Promessa: existe uma string $s\in\Sigma^n$ tal que $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ para todos $x,y\in\Sigma^n$
Saída: a string $s$

Vamos desdobrar a promessa para entender melhor o que ela diz em breve, mas primeiro é importante deixar claro que ela exige que $f$ tenha uma estrutura muito especial — portanto, a maioria das funções não satisfará essa promessa. Vale também reconhecer que esse problema não pretende ter importância prática. Pelo contrário, é um problema um tanto artificial, criado especificamente para ser fácil para computadores quânticos e difícil para computadores clássicos.

Existem dois casos principais: o primeiro é que $s$ é a string de zeros $0^n$, e o segundo é que $s$ não é a string de zeros.

• Caso 1: $s=0^n.$ Se $s$ é a string de zeros, podemos simplificar a declaração de "se e somente se" na promessa para que ela leia $[f(x) = f(y)] \Leftrightarrow [x = y].$ Isso equivale a $f$ ser uma função injetora (um-para-um).

• Caso 2: $s\neq 0^n.$ Se $s$ não é a string de zeros, então a promessa sendo satisfeita para essa string implica que $f$ é dois-para-um, o que significa que para cada string de saída possível de $f,$ existem exatamente duas strings de entrada que fazem $f$ produzir essa string. Além disso, essas duas strings de entrada devem ter a forma $w$ e $w \oplus s$ para alguma string $w.$

É importante reconhecer que só pode existir uma string $s$ que funcione quando a promessa é satisfeita, portanto sempre há uma resposta correta única para funções que satisfazem a promessa.

Aqui está um exemplo de uma função da forma $f:\Sigma^3 \rightarrow \Sigma^5$ que satisfaz a promessa para a string $s = 011$.

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

Existem $8$ strings de entrada diferentes e $4$ strings de saída diferentes, cada uma ocorrendo duas vezes — portanto, essa é uma função dois-para-um. Além disso, para quaisquer duas strings de entrada diferentes que produzem a mesma string de saída, vemos que o XOR bit a bit dessas duas strings de entrada é igual a $011$, o que equivale a dizer que uma delas é igual à outra submetida ao XOR com $s$.

Observe que a única coisa que importa sobre as strings de saída reais é se elas são iguais ou diferentes para diferentes escolhas de strings de entrada. Por exemplo, no exemplo acima, existem quatro strings $(10011,$ $00101,$ $00001,$ e $11010)$ que aparecem como saídas de $f.$ Poderíamos substituir essas quatro strings por outras strings diferentes, desde que sejam todas distintas, e a solução correta $s = 011$ não mudaria.

Descrição do algoritmo

Aqui está um diagrama de circuito quântico representando o algoritmo de Simon.

Para ser preciso, há $n$ qubits no topo que são submetidos a portas Hadamard e $m$ qubits na parte inferior que entram diretamente na porta de consulta. Parece muito semelhante aos algoritmos que já discutimos na lição, mas desta vez não há kickback de fase; os $m$ qubits inferiores entram todos na porta de consulta no estado $\vert 0\rangle$.

Para resolver o problema de Simon usando esse circuito, na prática serão necessárias várias execuções independentes seguidas de uma etapa de pós-processamento clássico, que será descrita mais adiante após a análise do comportamento do circuito.

Análise

A análise do algoritmo de Simon começa de forma semelhante ao algoritmo de Deutsch-Jozsa. Após a primeira camada de portas Hadamard ser aplicada nos $n$ qubits superiores, o estado se torna

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

Quando $U_f$ é aplicado, a saída da função $f$ é submetida ao XOR no estado todo-zero dos $m$ qubits inferiores, e o estado se torna

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

Quando a segunda camada de portas Hadamard é aplicada, obtemos o seguinte estado usando a mesma fórmula para a ação de uma camada de portas Hadamard de antes.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

Neste ponto, a análise diverge das análises dos algoritmos anteriores desta lição.

Estamos interessados na probabilidade de as medições resultarem em cada string possível $y\in\Sigma^n$. Pelas regras de análise de medições descritas na lição Sistemas múltiplos do curso Fundamentos de informação quântica, encontramos que a probabilidade $p(y)$ de obter a string $y$ é igual a

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

Para entender melhor essas probabilidades, precisaremos de mais um pouco de notação e terminologia. Primeiro, a imagem da função $f$ é o conjunto que contém todas as suas strings de saída.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

Segundo, para cada string $z\in\operatorname{range}(f)$, podemos expressar o conjunto de todas as strings de entrada para as quais a função assume o valor $z$ como $f^{-1}(\{z\})$.

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

O conjunto $f^{-1}(\{z\})$ é conhecido como a pré-imagem de $\{z\}$ sob $f$. Podemos definir a pré-imagem sob $f$ de qualquer conjunto no lugar de $\{z\}$ de forma análoga — é o conjunto de todos os elementos que $f$ mapeia para aquele conjunto. (Esta notação não deve ser confundida com a inversa da função $f$, que pode não existir. O fato de que o argumento no lado esquerdo é o conjunto $\{z\}$ em vez do elemento $z$ é a pista que nos permite evitar essa confusão.)

Usando esta notação, podemos dividir a soma em nossa expressão para as probabilidades acima para obter

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

Toda string $x\in\Sigma^n$ é representada exatamente uma vez pelas duas somatórias — basicamente estamos colocando essas strings em baldes separados dependendo de qual string de saída $z = f(x)$ elas produzem quando avaliamos a função $f$, e então somando separadamente sobre todos os baldes.

Podemos agora avaliar a norma euclidiana ao quadrado para obter

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

Para simplificar ainda mais essas probabilidades, vamos analisar o valor

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

para uma escolha arbitrária de $z\in\operatorname{range}(f)$.

Se acontece de $s = 0^n$, então $f$ é uma função injetora e sempre há apenas um único elemento $x\in f^{-1}(\{z\})$, para todo $z\in\operatorname{range}(f)$. O valor da expressão $(1)$ é $1$ neste caso.

Se, por outro lado, $s\neq 0^n,$ então existem exatamente duas strings no conjunto $f^{-1}(\{z\}).$ Para ser preciso, se escolhermos $w\in f^{-1}(\{z\})$ como qualquer uma dessas duas strings, então a outra string deve ser $w \oplus s$ pela promessa no problema de Simon. Usando essa observação, podemos simplificar $(1)$ da seguinte forma.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

Assim, o valor $(1)$ é independente da escolha específica de $z\in\operatorname{range}(f)$ em ambos os casos.

Podemos agora concluir a análise examinando os mesmos dois casos de antes separadamente.

• Caso 1: $s = 0^n.$ Neste caso a função $f$ é injetora, portanto existem $2^n$ strings $z\in\operatorname{range}(f),$ e obtemos

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  Em palavras, as medições resultam em uma string $y\in\Sigma^n$ escolhida uniformemente ao acaso.

• Caso 2: $s \neq 0^n.$ Neste caso $f$ é dois-para-um, portanto existem $2^{n-1}$ elementos em $\operatorname{range}(f).$ Usando a fórmula acima, concluímos que a probabilidade de medir cada $y\in\Sigma^n$ é

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  Em palavras, obtemos uma string escolhida uniformemente ao acaso do conjunto $\{y\in\Sigma^n : y \cdot s = 0\}$, que contém $2^{n-1}$ strings. (Como $s\neq 0^n$, exatamente metade das strings binárias de comprimento $n$ tem produto escalar binário $1$ com $s$ e a outra metade tem produto escalar binário $0$ com $s$, como já observamos na análise do algoritmo de Deutsch-Jozsa para o problema de Bernstein-Vazirani.)

Pós-processamento clássico

Agora sabemos quais são as probabilidades para os possíveis resultados de medição quando executamos o circuito quântico do algoritmo de Simon. Isso é suficiente para determinar $s$?

A resposta é sim, desde que estejamos dispostos a repetir o processo várias vezes e aceitar que ele pode falhar com alguma probabilidade, que podemos tornar muito pequena executando o circuito vezes suficientes. A ideia essencial é que cada execução do circuito nos fornece evidências estatísticas sobre $s$, e podemos usar essas evidências para encontrar $s$ com probabilidade muito alta se executarmos o circuito um número suficiente de vezes.

Suponhamos que executamos o circuito independentemente $k$ vezes, para $k = n + 10$. Não há nada de especial nesse número específico de iterações — poderíamos tomar $k$ maior (ou menor) dependendo da probabilidade de falha que estamos dispostos a tolerar, como veremos. Escolher $k = n + 10$ garantirá que tenhamos mais de $99,9$% de chance de recuperar $s$.

Ao executar o circuito $k$ vezes, obtemos strings $y^1,...,y^{k} \in \Sigma^n$. Para ser claro, os sobrescritos aqui são parte dos nomes dessas strings, não expoentes ou índices de seus bits, portanto temos

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

Formamos agora uma matriz $M$ com $k$ linhas e $n$ colunas tomando os bits dessas strings como entradas de valor binário.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

Agora, não sabemos o que é $s$ neste ponto — nosso objetivo é encontrar essa string. Mas imagine por um momento que sabemos a string $s$, e formamos um vetor coluna $v$ a partir dos bits da string $s = s_{n-1} \cdots s_0$ da seguinte forma.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

Se realizarmos a multiplicação matriz-vetor $M v$ módulo $2$ — ou seja, realizamos a multiplicação normalmente e depois tomamos o resto das entradas do resultado após dividir por $2$ — obtemos o vetor todo-zero.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

Ou seja, tratada como um vetor coluna $v$ como descrito acima, a string $s$ sempre será um elemento do espaço nulo da matriz $M$, desde que façamos a aritmética módulo $2$. Isso vale tanto no caso $s = 0^n$ quanto no caso $s\neq 0^n$. Para ser mais preciso, o vetor todo-zero está sempre no espaço nulo de $M$, e é acompanhado pelo vetor cujas entradas são os bits de $s$ no caso em que $s\neq 0^n$.

A questão restante é se haverá outros vetores no espaço nulo de $M$ além dos correspondentes a $0^n$ e $s$. A resposta é que isso se torna cada vez mais improvável à medida que $k$ aumenta — e se escolhermos $k = n + 10$, o espaço nulo de $M$ não conterá outros vetores além dos correspondentes a $0^n$ e $s$ com mais de $99,9$% de chance. De forma mais geral, se substituirmos $k = n + 10$ por $k = n + r$ para uma escolha arbitrária de um inteiro positivo $r$, a probabilidade de que os vetores correspondentes a $0^n$ e $s$ estejam sozinhos no espaço nulo de $M$ é de pelo menos $1 - 2^{-r}$.

Usando álgebra linear, é possível calcular eficientemente uma descrição do espaço nulo de $M$ módulo $2$. Especificamente, isso pode ser feito usando eliminação gaussiana, que funciona da mesma forma com aritmética módulo $2$ que com números reais ou complexos. Desde que os vetores correspondentes a $0^n$ e $s$ estejam sozinhos no espaço nulo de $M$, o que ocorre com alta probabilidade, podemos deduzir $s$ a partir dos resultados desse cálculo.

Dificuldade clássica

Quantas consultas um algoritmo de consulta clássico precisa fazer para resolver o problema de Simon? A resposta é: muitas, em geral.

Existem diferentes afirmações precisas que podem ser feitas sobre a dificuldade clássica desse problema, e aqui está apenas uma delas. Se tivermos qualquer algoritmo de consulta probabilístico, e esse algoritmo fizer menos de $2^{n/2 - 1} - 1$ consultas, que é um número de consultas exponencial em $n$, então esse algoritmo falhará em resolver o problema de Simon com probabilidade de pelo menos $1/2$.

Às vezes, provar resultados de impossibilidade como este pode ser muito desafiador, mas este não é muito difícil de provar através de uma análise probabilística elementar. Aqui, porém, examinaremos apenas brevemente a intuição básica por trás disso.

Estamos tentando encontrar a string oculta $s$, mas enquanto não consultarmos a função em duas strings que têm o mesmo valor de saída, obteremos informações muito limitadas sobre $s$. De forma intuitiva, tudo que aprenderemos é que a string oculta $s$ não é o OU exclusivo de quaisquer duas strings distintas que consultamos. E se consultarmos menos de $2^{n/2 - 1} - 1$ strings, ainda haverá muitas escolhas para $s$ que não eliminamos porque não há pares de strings suficientes para isso. Esta não é uma prova formal, é apenas a ideia básica.

Portanto, em resumo, o algoritmo de Simon nos fornece uma vantagem notável do quantum sobre os algoritmos clássicos dentro do modelo de consulta. Em particular, o algoritmo de Simon resolve o problema de Simon com um número de consultas que é linear no número de bits de entrada $n$ da nossa função, enquanto qualquer algoritmo clássico, mesmo que seja probabilístico, precisa fazer um número de consultas que é exponencial em $n$ para resolver o problema de Simon com uma probabilidade razoável de sucesso.