problema de subgrupo oculto

La transformada cuántica de Fourier se puede definir en términos de${\displaystyle \mathrm {Z} _ {N}}$, el grupo cíclico aditivo de orden${\displaystyle N}$Presentando al personaje$${\displaystyle \chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},}$$La transformada cuántica de Fourier tiene la definición de$${\displaystyle F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\chi _{j}(k)|k\rangle .}$$Además, definimos${\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }$Cualquier grupo abeliano finito puede escribirse como el producto directo de múltiples grupos cíclicos.${\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}$En una computadora cuántica, esto se representa como el producto tensorial de múltiples registros de dimensiones.${\displaystyle N_{1},N_{2},\ldots ,N_{m}}$respectivamente, y la transformada de Fourier cuántica global es${\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}$.

El conjunto de personajes de${\displaystyle G}$forma un grupo${\displaystyle {\widehat {G}}}$llamado el grupo dual de${\displaystyle G}$También tenemos un subgrupo${\displaystyle H^{\perp }\leq {\widehat {G}}}$de tamaño${\displaystyle |G|/|H|}$definido por$${\displaystyle H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ para todo }}h\in H\}}$$En cada iteración del algoritmo, el circuito cuántico genera un elemento.${\displaystyle g\in G}$correspondiente a un carácter${\displaystyle \chi _{g}\in H^{\perp }}$y desde entonces${\displaystyle \chi _{g}(h)={1}}$a pesar de${\displaystyle h\in H}$, ayuda a determinar qué${\displaystyle H}$es.

El algoritmo es el siguiente:

1. Comencemos con el estado${\displaystyle |0\rangle |0\rangle }$, donde los estados base del registro izquierdo son cada elemento de${\displaystyle G}$y los estados base del registro derecho son cada elemento de${\displaystyle X}$.
2. Crear una superposición entre los estados base de${\displaystyle G}$en el registro izquierdo, saliendo del estado${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _ {g\in G}|g\rangle |0\rangle }$.
3. Consultar la función${\displaystyle f}$El estado posterior es${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _ {g\in G}|g\rangle |f(g)\rangle }$.
4. Mide el registro de salida. Esto da algunos resultados.${\displaystyle f(s)}$para algunos${\displaystyle s\in G}$y colapsa el estado a${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }$porque${\displaystyle f}$tiene el mismo valor para cada elemento de la clase lateral${\displaystyle s+{H}}$. Descartamos el registro de salida para obtener${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }$.
5. Realizar la transformada cuántica de Fourier, obteniendo el estado${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }$.
6. Este estado es igual a${\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }$, que se puede medir para obtener información sobre${\displaystyle H}$.
7. Repita hasta que${\displaystyle H}$(o un conjunto generador para${\displaystyle H}$) se determina.

El estado en el paso 5 es igual al estado en el paso 6 debido a lo siguiente:$${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi _{g}(h)\right)|g\rangle \\&={\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle \end{aligned}}}$$Para la última igualdad, utilizamos la siguiente identidad:

Cada medición del estado final dará como resultado alguna información obtenida sobre${\displaystyle H}$puesto que sabemos que${\displaystyle \chi _{g}(h)=1}$a pesar de${\displaystyle h\in H}$.${\displaystyle H}$o un conjunto generador para${\displaystyle H}$, se encontrará después de un número polinomial de mediciones. El tamaño de un conjunto generador será logarítmicamente pequeño en comparación con el tamaño de${\displaystyle G}$. Dejar${\displaystyle T}$denotamos un conjunto generador para${\displaystyle H}$, significado${\displaystyle \langle T\rangle =H}$. El tamaño del subgrupo generado por${\displaystyle T}$se duplicará como mínimo cuando se agregue un nuevo elemento.${\displaystyle t\notin T}$se le añade, porque${\displaystyle H}$y${\displaystyle t+H}$son disjuntos y porque${\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }$Por lo tanto, el tamaño de un conjunto generador${\displaystyle |T|}$Satisface$${\displaystyle |T|\leq \log |H|\leq \log |G|}$$Por lo tanto, un conjunto generador para${\displaystyle H}$podrá obtenerse en tiempo polinomial incluso si${\displaystyle G}$su tamaño es exponencial.