El problema del cambio oculto dice: Dado un oráculo que codifica dos funciones y , hay una cadena de n bits para cual para todos . Encontrar. [1] Muchas funciones, como el símbolo de Legendre y las funciones dobladas , satisfacen estas limitaciones. [2] Con un algoritmo cuántico que se define como "" dónde es la puerta de Hadamard yes la transformada de Fourier de, este problema se puede resolver en un número polinomial de consultas para mientras se realizan consultas exponenciales con un algoritmo clásico. La diferencia entre el problema del subgrupo oculto y el problema del cambio oculto es que el primero se centra en el grupo subyacente mientras que el segundo se centra en el anillo o campo subyacente . [1]
Referencias
- ^ a b Dam, Wim van; Hallgren, Sean; Ip, Lawrence (2002). "Algoritmos cuánticos para algunos problemas de cambio ocultos". Sociedad de Matemáticas Industriales y Aplicadas . 36 : 763–778. arXiv : quant-ph / 0211140 . doi : 10.1137 / S009753970343141X .
- ^ Rötteler, Martin (2008). "Algoritmos cuánticos para funciones booleanas altamente no lineales". Sociedad de Matemáticas Industriales y Aplicadas . 402 : 448–457. arXiv : 0811.3208 . doi : 10.1137 / 1.9781611973075.37 .