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.