Problema de Simon

Na teoria da complexidade computacional e na computação quântica, o problema de Simon é um problema computacional que provou ser resolvido exponencialmente mais rápido em um computador quântico do que em um computador clássico (isto é, tradicional). O algoritmo quântico que resolve o problema de Simon, geralmente chamado de algoritmo de Simon, serviu de inspiração para o algoritmo de Shor. Ambos os problemas são casos especiais do problema do subgrupo oculto abeliano, que hoje se sabe possuir algoritmos quânticos eficientes.

O problema está inserido no modelo de complexidade de árvore de decisão ou complexidade de consulta e foi concebido por Daniel R. Simon em 1994. Simon exibiu um algoritmo quântico que resolve o problema de Simon exponencialmente mais rápido, com exponencialmente menos consultas, do que o melhor algoritmo clássico probabilístico (ou determinístico). Em particular, o algoritmo de Simon utiliza um número linear de consultas, enquanto qualquer algoritmo probabilístico clássico deve utilizar um número exponencial de consultas.

Este problema produz uma separação por oráculo entre as classes de complexidade BPP (complexidade de consulta clássica com erro limitado) e BQP (complexidade de consulta quântica com erro limitado). Esta é a mesma separação que o algoritmo de Bernstein–Vazirani alcança, e diferente da separação fornecida pelo algoritmo de Deutsch–Jozsa, que separa P e EQP. Ao contrário do algoritmo de Bernstein–Vazirani, a separação do algoritmo de Simon é exponencial.

Como este problema assume a existência de um oráculo de "caixa preta" altamente estruturado para alcançar sua aceleração, ele possui pouco valor prático. No entanto, sem tal oráculo, acelerações exponenciais não podem ser facilmente provadas, pois isso provaria que P é diferente de PSPACE.

Descrição do problema

O problema de Simon considera o acesso a uma função $f:\{0,1\}^{n}\to \{0,1\}^{m},\;m\geq n$ implementada por uma caixa preta ou um oráculo. É prometido que esta função seja ou uma função injetora (um-para-um), ou uma função dois-para-um; se $f$ for dois-para-um, é prometido, além disso, que duas entradas $x$ e $x'$ avaliam para o mesmo valor se, e somente se, $x$ e $x'$ diferirem em um conjunto fixo de bits. Ou seja:

Se $f$ não for um-para-um, promete-se que existe um $s$ não nulo tal que, para todos os $x\neq x'$, $f(x)=f(x')$ se e somente se $x'=x\oplus s$

onde $\oplus$ denota o OU exclusivo bit a bit. O problema de Simon pergunta, em sua versão de decisão, se $f$ é um-para-um ou dois-para-um. Em sua versão de não-decisão, o problema de Simon pergunta se $f$ é um-para-um ou qual é o valor de $s$ (conforme definido acima). O objetivo é resolver esta tarefa com o menor número de consultas (avaliações) de $f$.

Note que se $x'=x$, então $f(x')=f(x)$ e $x'=x\oplus s$ com $s=0$. Por outro lado (porque $a\oplus b\oplus b=a$ para todos $a$ e $b$), $x'=x\oplus s\iff x'\oplus x=s$. Assim, o problema de Simon pode ser reformulado da seguinte forma:

Dado o acesso de caixa preta ou oráculo a $f$, com a promessa de satisfazer, para algum $s$ e todos $x,x'$, $f(x)=f(x')$ se e somente se $x'\oplus x\in \{0,s\}$, determine se $s\neq 0$ (versão de decisão) ou forneça $s$ (versão de não-decisão).

Note também que a promessa sobre $f$ implica que, se $f$ for dois-para-um, ela será uma função periódica: $f(x)=f(x\oplus s).$

Exemplo

A função a seguir é um exemplo de uma função que satisfaz a propriedade exigida para $n=3$:

$x$	$f(x)$
000	101
001	010
010	000
011	110
100	000
101	110
110	101
111	010

Neste caso, $s=110$ (ou seja, a solução). Cada saída de $f$ ocorre duas vezes, e as duas strings de entrada correspondentes a qualquer saída dada têm o XOR bit a bit igual a $s=110$.

Por exemplo, as strings de entrada $010$ e $100$ são ambas mapeadas (por $f$) para a mesma string de saída $000$. Isto é, $f(010)=000$ e $f(100)=000$. Aplicando XOR a 010 e 100 obtém-se 110, ou seja, $010\oplus 100=110=s.$

$s=110$ também pode ser verificado usando as strings de entrada 001 e 111, que são ambas mapeadas (por f) para a mesma string de saída 010. Aplicando XOR a 001 e 111 obtém-se 110, ou seja, $001\oplus 111=110=s$. Isso fornece a mesma solução $s=110$ de antes.

Neste exemplo, a função f é de fato uma função dois-para-um, onde $s\neq 0^{n}$.

Dificuldade do problema

Intuitivamente, este é um problema difícil de resolver de forma "clássica", mesmo se utilizarmos aleatoriedade e aceitarmos uma pequena probabilidade de erro. A intuição por trás da dificuldade é razoavelmente simples: se você quiser resolver o problema de forma clássica, precisa encontrar duas entradas diferentes $x$ e $y$ para as quais $f(x)=f(y)$. Não há necessariamente nenhuma estrutura na função $f$ que nos ajude a encontrar tais entradas: especificamente, só podemos descobrir algo sobre $f$ (ou o que ela faz) quando, para duas entradas diferentes, obtemos a mesma saída. Em qualquer caso, precisaríamos adivinhar $\Omega ({\sqrt {2^{n}}})$ entradas diferentes antes de ter a probabilidade de encontrar um par no qual $f$ produza a mesma saída, conforme o problema do aniversário. Como, classicamente, para encontrar s com 100% de certeza seria necessário verificar $\Theta ({\sqrt {2^{n}}})$ entradas, o problema de Simon busca encontrar s usando menos consultas do que este método clássico.

O algoritmo de Simon

Circuito quântico que representa/implementa o algoritmo de Simon

O algoritmo como um todo utiliza uma sub-rotina para executar os seguintes dois passos:

1. Executar a sub-rotina quântica um número esperado de $O(n)$ vezes para obter uma lista de bitstrings linearmente independentes $y_{1},...,y_{n-1}$.
2. Cada $y_{k}$ satisfaz $y_{k}\cdot s=0$, de modo que podemos resolver o sistema de equações que isso produz para obter $s$.

Sub-rotina quântica

O circuito quântico (veja a imagem) é a implementação da parte quântica do algoritmo de Simon. A sub-rotina quântica do algoritmo faz uso da transformada de Hadamard$$H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle$$ onde $k\cdot j=k_{1}j_{1}\oplus \ldots \oplus k_{n}j_{n}$, onde $\oplus$ denota o XOR.

Primeiro, o algoritmo começa com dois registradores, inicializados como $|0\rangle ^{\otimes n}|0\rangle ^{\otimes n}$. Então, aplicamos a transformada de Hadamard ao primeiro registrador, o que resulta no estado

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |0\rangle ^{\otimes n}.$

Consultamos o oráculo $U_{f}$ para obter o estado

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}|k\rangle |f(k)\rangle$.

Aplicamos outra transformada de Hadamard ao primeiro registrador. Isso produzirá o estado

${\frac {1}{\sqrt {2^{n}}}}\sum _{k=0}^{2^{n}-1}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{j\cdot k}|j\rangle \right]|f(k)\rangle =\sum _{j=0}^{2^{n}-1}|j\rangle \left[{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right].$

Finalmente, medimos o primeiro registrador (o algoritmo também funciona se o segundo registrador for medido antes do primeiro, mas isso é desnecessário). A probabilidade de medir um estado $|j\rangle$ é $$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}$$ Isso se deve ao fato de que obter a magnitude desse vetor e elevá-la ao quadrado soma todas as probabilidades de todas as possíveis medições do segundo registrador que necessariamente teriam o primeiro registrador como $|j\rangle$. Existem dois casos para nossa medição:

1. $s=0^{n}$ e $f$ é injetora (um-para-um).
2. $s\neq 0^{n}$ e $f$ é dois-para-um.

Para o primeiro caso, $$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}={\frac {1}{2^{n}}}$$ já que neste caso, $f$ é um-para-um, implicando que a imagem de $f$ é $\{0,1\}^{n}$, o que significa que o somatório abrange todos os vetores da base. Para o segundo caso, note que existem duas strings, $x_{1}$ e $x_{2}$, tais que $f(x_{1})=f(x_{2})=z$, onde $z\in \mathrm {imagem} (f)$. Assim, $$\left|\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}(-1)^{j\cdot k}|f(k)\rangle \right|\right|^{2}=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {imagem} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}$$ Além disso, como $x_{1}\oplus x_{2}=s$, $x_{2}=x_{1}\oplus s$, temos: $${\begin{aligned}\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {imagem} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{2}})|z\rangle \right|\right|^{2}&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {imagem} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot (x_{1}\oplus s)})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {imagem} (f)}((-1)^{j\cdot x_{1}}+(-1)^{j\cdot x_{1}\oplus j\cdot s})|z\rangle \right|\right|^{2}\\&=\left|\left|{\frac {1}{2^{n}}}\sum _{z\,\in \,\mathrm {imagem} (f)}(-1)^{j\cdot x_{1}}(1+(-1)^{j\cdot s})|z\rangle \right|\right|^{2}\end{aligned}}$$ Esta expressão agora é fácil de avaliar. Lembre-se de que estamos medindo $j$. Quando $j\cdot s=1$, essa expressão será avaliada como $0$, e quando $j\cdot s=0$, a expressão será $2^{-n+1}$.

Portanto, tanto quando $s=0^{n}$ quanto quando $s\neq 0^{n}$, o nosso $j$ medido satisfaz $j\cdot s=0$.

Pós-processamento clássico

Executamos a parte quântica do algoritmo até termos uma lista linearmente independente de bitstrings $y_{1},\ldots ,y_{n-1}$, onde cada $y_{k}$ satisfaz $y_{k}\cdot s=0$. Assim, podemos resolver eficientemente este sistema de equações de forma clássica para encontrar $s$.

A probabilidade de que $y_{1},y_{2},\dots ,y_{n-1}$ sejam linearmente independentes é de pelo menos $$\prod _{k=1}^{\infty }\left(1-{\frac {1}{2^{k}}}\right)=0.288788\dots$$ Uma vez que resolvemos o sistema de equações e produzimos uma solução $s'$, podemos testar se $f(0^{n})=f(s')$. Se isso for verdade, então sabemos que $s'=s$, pois $f(0^{n})=f(0^{n}\oplus s)=f(s)$. Se for o caso de $f(0^{n})\neq f(s')$, então isso significa que $s=0^{n}$, e $f(0^{n})\neq f(s')$ porque $f$ é injetora (um-para-um).

Podemos repetir o algoritmo de Simon um número constante de vezes para aumentar arbitrariamente a probabilidade de sucesso, mantendo a mesma complexidade de tempo.

Exemplos explícitos do algoritmo de Simon para poucos qubits

Um qubit

Considere a instância mais simples do algoritmo, com $n=1$. Neste caso, a evolução do estado de entrada através de uma porta Hadamard e o oráculo resulta no estado (salvo renormalização):

$|0\rangle |f(0)\rangle +|1\rangle |f(1)\rangle .$

Se $s=1$, ou seja, $f(0)=f(1)$, então a medição do segundo registrador sempre dá o resultado $|f(0)\rangle$, e sempre faz com que o primeiro registrador colapse no estado (salvo renormalização):

$|0\rangle +|1\rangle .$

Assim, a aplicação de uma Hadamard e a medição do primeiro registrador sempre dão o resultado $|0\rangle$. Por outro lado, se $f$ for injetora, isto é, $s=0$, então medir o primeiro registrador após a segunda Hadamard pode resultar tanto em $|0\rangle$ quanto em $|1\rangle$, com igual probabilidade.

Recuperamos $s$ a partir dos resultados da medição observando se medimos sempre $|0\rangle$, caso em que $s=1$, ou se medimos tanto $|0\rangle$ quanto $|1\rangle$ com igual probabilidade, caso em que inferimos que $s=0$. Esse esquema falhará se $s=0$ mas, não obstante, sempre encontrarmos o resultado $|0\rangle$, contudo a probabilidade deste evento é $2^{-N}$ sendo $N$ o número de medições realizadas, podendo, assim, tornar-se exponencialmente pequena aumentando-se a estatística.

Dois qubits

Considere agora o caso com $n=2$. A parte inicial do algoritmo resulta no estado (salvo renormalização): $$|00\rangle |f(00)\rangle +|01\rangle |f(01)\rangle +|10\rangle |f(10)\rangle +|11\rangle |f(11)\rangle .$$ Se $s=(00)$, significando que $f$ é injetora, então encontrar $|f(x)\rangle$ no segundo registrador sempre colapsa o primeiro registrador para $|x\rangle$, para todo $x\in \{0,1\}^{2}$. Em outras palavras, aplicando as portas Hadamard e medindo o primeiro registrador, os quatro resultados $00,01,10,11$ são encontrados com igual probabilidade.

Suponha, por outro lado, que $s\neq (00)$, por exemplo, $s=(01)$. Então, medir $|f(00)\rangle$ no segundo registrador colapsa o primeiro registrador para o estado $|00\rangle +|10\rangle$. E de forma mais geral, medir $|f(xy)\rangle$ fornece $|x,y\rangle +|x,y\oplus 1\rangle =|x\rangle (|0\rangle +|1\rangle )$ no primeiro registrador. Aplicar portas Hadamard e medir no primeiro registrador pode assim resultar nos resultados $00$ e $10$ com probabilidades iguais.

Um raciocínio semelhante aplica-se aos outros casos: se $s=(10)$, então os resultados possíveis são $00$ e $01$, enquanto se $s=(11)$, os resultados possíveis são $00$ e $11$, compativelmente com a regra $j\cdot s=0$ discutida no caso geral.

Para recuperar $s$, só precisamos diferenciar entre estes quatro casos, recolhendo estatística suficiente para assegurar que a probabilidade de confundir a distribuição de probabilidade de um resultado com a de outro seja suficientemente pequena.

Complexidade

O algoritmo de Simon requer $O(n)$ consultas à caixa preta, ao passo que um algoritmo clássico precisaria de pelo menos $\Omega (2^{n/2})$ consultas. Também se sabe que o algoritmo de Simon é ótimo no sentido de que qualquer algoritmo quântico para resolver este problema requer $\Omega (n)$ consultas.

Implementação do algoritmo de Simon no Qiskit

O circuito quântico mostrado aqui é de um exemplo simples de como o algoritmo de Simon pode ser implementado em Python usando Qiskit, uma estrutura de desenvolvimento de software de computação quântica de código aberto da IBM.

Circuito quântico do algoritmo de Simon

Veja também

• Algoritmo de Deutsch–Jozsa
• Algoritmo de Shor
• Algoritmo de Bernstein–Vazirani
• Modelo de árvore de decisão