Problema de Simon

Na teoria da complexidade computacional e em Computação quântica, o problema de Simon nos é dado em uma função (implementada por uma caixa preta) de cordas de n bits a cordas de n bits, $f:\{0,1{\}}^n\to \{0,1{\}}^n$ que é garantida a satisfazer a propriedade de que para alguns $s\in \{0,1{\}}^n$ que tem para todos $y,z\in \{0,1{\}}^n$, $f(y)=f(z)$ se e somente se $y=z$ ou $y\oplus z=s$. Daniel Simon, em 1994, apresentou um algoritmo quântico, normalmente chamado algoritmo de Simon que resolve o problema exponencialmente mais rápido do que qualquer (determinístico ou probabilístico) algoritmo.