Pular para o conteúdo principal

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 do quantum sobre os algoritmos clássicos (incluindo 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:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m

para inteiros positivos nn e m.m. Poderíamos restringir nossa atenção ao caso m=nm = 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:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m
Promessa: existe uma string s∈Σns\in\Sigma^n tal que [f(x)=f(y)]⇔[(x=y)∨(x⊕s=y)][f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)] para todos x,y∈Σnx,y\in\Sigma^n
Saída: a string ss

Vamos desdobrar a promessa para entender melhor o que ela diz em breve, mas primeiro é importante deixar claro que ela exige que ff 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 tem intenção de 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 ss é a string de zeros 0n,0^n, e o segundo é que ss não é a string de zeros.

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

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

É importante reconhecer que só pode existir uma string ss 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:Σ3→Σ5f:\Sigma^3 \rightarrow \Sigma^5 que satisfaz a promessa para a string s=011.s = 011.

f(000)=10011f(001)=00101f(010)=00101f(011)=10011f(100)=11010f(101)=00001f(110)=00001f(111)=11010\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 88 strings de entrada diferentes e 44 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,011, o que equivale a dizer que uma delas é igual à outra submetida ao XOR com s.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,(10011, 00101,00101, 00001,00001, e 11010)11010) que aparecem como saídas de f.f. Poderíamos substituir essas quatro strings por outras strings diferentes, desde que sejam todas distintas, e a solução correta s=011s = 011 não mudaria.

Descrição do algoritmo​

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

Algoritmo de Simon

Para ser preciso, há nn qubits no topo que são submetidos a portas Hadamard e mm 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 mm qubits inferiores entram todos na porta de consulta no estado ∣0⟩.\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 nn qubits superiores, o estado se torna

12n∑x∈Σn∣0m⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.

Quando UfU_f é aplicado, a saída da função ff é submetida ao XOR no estado todo-zero dos mm qubits inferiores, e o estado se torna

12n∑x∈Σn∣f(x)⟩∣x⟩.\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.

12n∑x∈Σn∑y∈Σn(−1)x⋅y∣f(x)⟩∣y⟩\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∈Σn.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)p(y) de obter a string yy é igual a

p(y)=∥12n∑x∈Σn(−1)x⋅y∣f(x)⟩∥2.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 ff é o conjunto que contém todas as suas strings de saída.

range⁡(f)={f(x):x∈Σn}\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}

Segundo, para cada string z∈range⁡(f),z\in\operatorname{range}(f), podemos expressar o conjunto de todas as strings de entrada que fazem a função avaliar para essa string de saída zz como f−1({z}).f^{-1}(\{z\}).

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

O conjunto f−1({z})f^{-1}(\{z\}) é conhecido como a pré-imagem de {z}\{z\} sob f.f. Podemos definir a pré-imagem sob ff de qualquer conjunto no lugar de {z}\{z\} de forma análoga — é o conjunto de todos os elementos que ff mapeia para aquele conjunto. (Esta notação não deve ser confundida com a inversa da função f,f, que pode não existir. O fato de que o argumento no lado esquerdo é o conjunto {z}\{z\} em vez do elemento zz é 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)=∥12n∑z∈range⁡(f)(∑x∈f−1({z})(−1)x⋅y)∣z⟩∥2.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∈Σnx\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)z = f(x) elas produzem quando avaliamos a função f,f, e então somando separadamente sobre todos os baldes.

Podemos agora avaliar a norma euclidiana ao quadrado para obter

p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2.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

∣∑x∈f−1({z})(−1)x⋅y∣2(1)\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}

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

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

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

∣∑x∈f−1({z})(−1)x⋅y∣2=∣(−1)w⋅y+(−1)(w⊕s)⋅y∣2=∣(−1)w⋅y(1+(−1)s⋅y)∣2=∣1+(−1)y⋅s∣2={4y⋅s=00y⋅s=1\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)(1) é independente da escolha específica de z∈range⁡(f)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=0n.s = 0^n. Neste caso a função ff é injetora, portanto existem 2n2^n strings z∈range⁡(f),z\in\operatorname{range}(f), e obtemos

    p(y)=122n⋅2n=12n.p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.

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

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

    p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2={12n−1y⋅s=00y⋅s=1p(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∈Σn:y⋅s=0},\{y\in\Sigma^n : y \cdot s = 0\}, que contém 2n−12^{n-1} strings. (Como s≠0n,s\neq 0^n, exatamente metade das strings binárias de comprimento nn tem produto escalar binário 11 com ss e a outra metade tem produto escalar binário 00 com s,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 ss?

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,s, e podemos usar essas evidências para encontrar ss com probabilidade muito alta se executarmos o circuito um número suficiente de vezes.

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

Ao executar o circuito kk vezes, obtemos strings y1,...,yk∈Σn.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

y1=yn−11⋯y01y2=yn−12⋯y02    ⋮yk=yn−1k⋯y0k\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 MM com kk linhas e nn colunas tomando os bits dessas strings como entradas de valor binário.

M=(yn−11⋯y01yn−12⋯y02⋮⋱⋮yn−1k⋯y0k)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 é ss neste ponto — nosso objetivo é encontrar essa string. Mas imagine por um momento que sabemos a string s,s, e formamos um vetor coluna vv a partir dos bits da string s=sn−1⋯s0s = s_{n-1} \cdots s_0 da seguinte forma.

v=(sn−1⋮s0)v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}

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

Mv=(y1⋅sy2⋅s⋮yk⋅s)=(00⋮0)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 vv como descrito acima, a string ss sempre será um elemento do espaço nulo da matriz M,M, desde que façamos a aritmética módulo 2.2. Isso vale tanto no caso s=0ns = 0^n quanto no caso s≠0n.s\neq 0^n. Para ser mais preciso, o vetor todo-zero está sempre no espaço nulo de M,M, e é acompanhado pelo vetor cujas entradas são os bits de ss no caso em que s≠0n.s\neq 0^n.

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

Usando álgebra linear, é possível calcular eficientemente uma descrição do espaço nulo de MM módulo 2.2. Especificamente, isso pode ser feito usando eliminação gaussiana, que funciona da mesma forma quando a aritmética é feita módulo 22 como funciona com números reais ou complexos. Desde que os vetores correspondentes a 0n0^n e ss estejam sozinhos no espaço nulo de M,M, o que ocorre com alta probabilidade, podemos deduzir ss 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 2n/2−1−12^{n/2 - 1} - 1 consultas, que é um número de consultas exponencial em n,n, então esse algoritmo falhará em resolver o problema de Simon com probabilidade de pelo menos 1/2.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,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.s. De forma intuitiva, tudo que aprenderemos é que a string oculta ss não é o OU exclusivo de quaisquer duas strings distintas que consultamos. E se consultarmos menos de 2n/2−1−12^{n/2 - 1} - 1 strings, ainda haverá muitas escolhas para ss 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 nn da nossa função, enquanto qualquer algoritmo clássico, mesmo que seja probabilístico, precisa fazer um número de consultas que é exponencial em nn para resolver o problema de Simon com uma probabilidade razoável de sucesso.