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, que é garantida a satisfazer a propriedade de que para alguns que tem para todos , se e somente se ou . 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.