Problema del subgrupo oculto

Problema muy general en informática.

El problema del subgrupo oculto ( HSP ) es un tema de investigación en matemáticas y ciencias de la computación teórica . El marco captura problemas como factorización , logaritmo discreto , isomorfismo de grafos y el problema del vector más corto . Esto lo hace especialmente importante en la teoría de la computación cuántica porque los algoritmos de Shor para factorizar y encontrar logaritmos discretos en computación cuántica son instancias del problema del subgrupo oculto para grupos abelianos finitos , mientras que los otros problemas corresponden a grupos finitos que no son abelianos.

Planteamiento del problema

Dado un grupo , un subgrupo y un conjunto , decimos que una función oculta el subgrupo si para todo si y solo si . De manera equivalente, es constante en cada clase lateral de H , mientras que es diferente entre las diferentes clases laterales de H . ${\displaystyle G}$ ${\displaystyle H\leq G}$ ${\displaystyle X}$ ${\displaystyle f:G\to X}$ ${\displaystyle H}$ ${\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})}$ ${\displaystyle g_{1}H=g_{2}H}$ ${\displaystyle f}$

Problema de subgrupo oculto : Sea un grupo, un conjunto finito y una función que oculta un subgrupo . La función se proporciona mediante un oráculo que utiliza bits. Utilizando la información obtenida de las evaluaciones de mediante su oráculo, determine un conjunto generador para . ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle f:G\to X}$ ${\displaystyle H\leq G}$ ${\displaystyle f}$ ${\displaystyle O(\log |G|+\log |X|)}$ ${\displaystyle f}$ ${\displaystyle H}$

Un caso especial es cuando es un grupo y es un homomorfismo de grupo en cuyo caso corresponde al núcleo de . ${\displaystyle X}$ ${\displaystyle f}$ ${\displaystyle H}$ ${\displaystyle f}$

Motivación

El problema del subgrupo oculto es especialmente importante en la teoría de la computación cuántica por las siguientes razones.

• El algoritmo de Shor para factorizar y encontrar logaritmos discretos (así como varias de sus extensiones) se basa en la capacidad de las computadoras cuánticas para resolver el HSP para grupos abelianos finitos .
• La existencia de algoritmos cuánticos eficientes para los HSP para ciertos grupos no abelianos implicaría algoritmos cuánticos eficientes para dos problemas principales: el problema del isomorfismo de grafos y ciertos problemas de vectores más cortos (SVP) en redes. Más precisamente, un algoritmo cuántico eficiente para el HSP para el grupo simétrico daría un algoritmo cuántico para el isomorfismo de grafos. ^[1] Un algoritmo cuántico eficiente para el HSP para el grupo diedro daría un algoritmo cuántico para el SVP único. ^[2] ${\displaystyle \operatorname {poly} (n)}$

Algoritmos

Existe un algoritmo cuántico eficiente para resolver HSP sobre grupos abelianos finitos en tiempo polinomial en . Para grupos arbitrarios, se sabe que el problema del subgrupo oculto se puede resolver utilizando un número polinomial de evaluaciones del oráculo. ^[3] Sin embargo, los circuitos que implementan esto pueden ser exponenciales en , lo que hace que el algoritmo no sea eficiente en general; los algoritmos eficientes deben ser polinomiales en el número de evaluaciones del oráculo y el tiempo de ejecución. La existencia de un algoritmo de este tipo para grupos arbitrarios está abierta. Existen algoritmos cuánticos de tiempo polinomial para ciertas subclases de grupos, como productos semidirectos de algunos grupos abelianos . ${\displaystyle \log |G|}$ ${\displaystyle \log |G|}$

Algoritmo para grupos abelianos

El algoritmo para grupos abelianos utiliza representaciones , es decir homomorfismos de a , el grupo lineal general sobre los números complejos . Una representación es irreducible si no se puede expresar como el producto directo de dos o más representaciones de . Para un grupo abeliano, todas las representaciones irreducibles son los caracteres , que son las representaciones de dimensión uno; no hay representaciones irreducibles de mayor dimensión para grupos abelianos. ${\displaystyle G}$ ${\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}$ ${\displaystyle G}$

Definición de la transformada cuántica de Fourier

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

Procedimiento

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

El algoritmo es el siguiente:

1. Comience con el estado , donde los estados base del registro izquierdo son cada elemento de , y los estados base del registro derecho son cada elemento de . ${\displaystyle |0\rangle |0\rangle }$ ${\displaystyle G}$ ${\displaystyle X}$
2. Crea una superposición entre los estados base de en el registro izquierdo, dejando el estado . ${\displaystyle G}$ ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }$
3. Consulta la función . El estado posterior es . ${\displaystyle f}$ ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }$
4. Medimos el registro de salida. Esto nos da algunos para algunos y colapsa el estado a porque tiene el mismo valor para cada elemento de la clase lateral . Descartamos el registro de salida para obtener . ${\displaystyle f(s)}$ ${\displaystyle s\in G}$ ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }$ ${\displaystyle f}$ ${\displaystyle s+{H}}$ ${\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 , que puede medirse para obtener información sobre . ${\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }$ ${\displaystyle H}$
7. Repita hasta que se determine (o un grupo electrógeno para ). ${\displaystyle H}$ ${\displaystyle H}$

El estado en el paso 5 es igual al estado en el paso 6 debido a lo siguiente: Para la última igualdad, utilizamos la siguiente identidad: $${\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}}}$$

Teorema  —  $${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}}$$

Prueba

Esto se puede derivar de la ortogonalidad de los caracteres. Los caracteres de forman una base ortonormal: Dejamos que sea la representación trivial, que asigna todas las entradas a , para obtener Dado que la suma se realiza sobre , también ser trivial solo importa si es trivial sobre ; es decir, si . Por lo tanto, sabemos que la suma dará como resultado si y dará como resultado si . ${\displaystyle G}$ $${\displaystyle {\frac {1}{\vert H\vert }}\sum _{h\in H}\chi _{g}(h)\chi _{g'}(h)={\begin{cases}1&g=g'\\0&g\neq g'\end{cases}}}$$ ${\displaystyle \chi _{g'}}$ ${\displaystyle 1}$ $${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}}$$ ${\displaystyle H}$ ${\displaystyle \chi _{g}}$ ${\displaystyle H}$ ${\displaystyle \chi _{g}\in H^{\perp }}$ ${\displaystyle \vert H\vert }$ ${\displaystyle \chi _{g}\in H^{\perp }}$ ${\displaystyle 0}$ ${\displaystyle \chi _{g}\notin H^{\perp }}$

Cada medición del estado final dará como resultado cierta información obtenida sobre ya que sabemos que para todo . , o un grupo electrógeno para , se encontrará después de un número polinomial de mediciones. El tamaño de un grupo electrógeno será logarítmicamente pequeño en comparación con el tamaño de . Sea un grupo electrógeno para , es decir . El tamaño del subgrupo generado por se duplicará al menos cuando se le agregue un nuevo elemento, porque y son disjuntos y porque . Por lo tanto, el tamaño de un grupo electrógeno satisface Por lo tanto, un grupo electrógeno para se podrá obtener en tiempo polinomial incluso si es exponencial en tamaño. ${\displaystyle H}$ ${\displaystyle \chi _{g}(h)=1}$ ${\displaystyle h\in H}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle H}$ ${\displaystyle \langle T\rangle =H}$ ${\displaystyle T}$ ${\displaystyle t\notin T}$ ${\displaystyle H}$ ${\displaystyle t+H}$ ${\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }$ ${\displaystyle |T|}$ $${\displaystyle |T|\leq \log |H|\leq \log |G|}$$ ${\displaystyle H}$ ${\displaystyle G}$

Instancias

Muchos algoritmos en los que se producen aceleraciones cuánticas en la computación cuántica son ejemplos del problema del subgrupo oculto. La siguiente lista describe ejemplos importantes del problema del subgrupo oculto y si son o no solucionables.

Véase también

• Problema de cambio oculto
• Dualidad de Pontryagin

Referencias

1. Mark Ettinger; Peter Høyer (1999). "Un observable cuántico para el problema del isomorfismo de grafos". arXiv : quant-ph/9901029 .
2. Oded Regev (2003). "Computación cuántica y problemas de red". arXiv : cs/0304005 .
3. Mark Ettinger; Peter Hoyer; Emanuel Knill (2004). "La complejidad de consulta cuántica del problema del subgrupo oculto es polinómica". Information Processing Letters . 91 : 43–48. arXiv : quant-ph/0401083 . Código Bibliográfico :2004quant.ph..1083E. doi :10.1016/j.ipl.2004.01.024. S2CID  5520617.
4. Kitaev, Alexei (20 de noviembre de 1995). "Medidas cuánticas y el problema del estabilizador abeliano". arXiv : quant-ph/9511026 .

Enlaces externos

• Richard Jozsa: Factorización cuántica, logaritmos discretos y el problema del subgrupo oculto
• Chris Lomont: El problema del subgrupo oculto - Revisión y problemas abiertos
• Problema de subgrupo oculto en arxiv.org
• Implementación completa del algoritmo de Shor para encontrar logaritmos discretos con Classiq