Problema de desplazamiento oculto

En computación cuántica , el problema del desplazamiento oculto es un tipo de problema basado en oráculos . Varias versiones de este problema cuentan con algoritmos cuánticos que pueden ejecutarse mucho más rápido que los métodos no cuánticos conocidos para el mismo problema. En su forma general, es equivalente al problema del subgrupo oculto para el grupo diedral . ^{[ 1 ]} Es un problema abierto importante comprender qué tan bien pueden desempeñarse los algoritmos cuánticos para esta tarea, ya que puede aplicarse para romper la criptografía basada en retículos . ^{[ 2 ] [ 3 ]}

El problema del desplazamiento oculto establece: Dado un oráculo${\displaystyle O}$que codifica dos funciones${\displaystyle f}$y${\displaystyle g}$, hay un${\displaystyle n}$cadena de bits${\displaystyle s}$para qué${\displaystyle g(x)=f(x+s)}$a pesar de${\displaystyle x}$. Encontrar${\displaystyle s}$. ^{[ 4 ]}

Funciones como el símbolo de Legendre y las funciones bent satisfacen estas restricciones. ^{[ 5 ]}

Con un algoritmo cuántico que se define como${\displaystyle |s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle }$, dónde${\displaystyle H}$es la puerta de Hadamard y${\displaystyle {\hat {g}}}$es la transformada de Fourier de${\displaystyle g}$, ciertas instancias de este problema pueden resolverse en un número polinomial de consultas a${\displaystyle O}$mientras se realizan consultas exponenciales con un algoritmo clásico.