Problema de Simon

En álgebra abstracta y computación cuántica, el problema planteado por Daniel R. Simon (conocido como problema de Simon) es un caso particular del problema del subgrupo oculto (Hidden Subgroup Problem, HSP), el cual ha sido útil para el planteamiento de algoritmos cuánticos que son eficientes, a diferencia de sus homólogos clásicos, permitiendo resolver problemas teóricos propuestos en las últimas décadas cuyas soluciones son de vital importancia en el campo de la computación cuántica. Para resolver el problema de Simon se han desarrollado algoritmos clásicos que utilizan fuerza bruta, de los cuales se sabe que su complejidad es exponencial. Para encontrar una solución eficiente se ha recurrido a algoritmos cuánticos, como el propuesto por el mismo Simon, cuya complejidad es polinomial, reduciendo así el tiempo de cómputo de forma significativa. Se han desarrollado algoritmos cuánticos para otros casos particulares del problema del subgrupo oculto, pero solo son eficientes aquellos que trabajan sobre grupos abelianos (como el de Simon). Para los grupos no abelianos aún no se han encontrado algoritmos cuánticos eficientes, de hecho estos no llegan a tener mejor desempeño que las soluciones clásicas.