Problema de subgrupo oculto

Problema muy general en informática.

El problema de subgrupos ocultos ( HSP ) es un tema de investigación en matemáticas e informática teórica . El marco captura problemas como factorización , logaritmo discreto , isomorfismo de gráficos y el problema del vector más corto . Esto lo hace especialmente importante en la teoría de la computación cuántica porque el algoritmo de Shor para factorizar la computación cuántica es un ejemplo del problema de subgrupos ocultos 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 sólo si . De manera equivalente, es constante en las clases laterales 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 a través de un oráculo , que utiliza bits. Utilizando la información obtenida de las evaluaciones de su oráculo, determine un grupo electrógeno 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 de los subgrupos ocultos 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 HSP para ciertos grupos no abelianos implicaría algoritmos cuánticos eficientes para dos problemas principales: el problema del isomorfismo gráfico 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 del gráfico. ^[1] Un algoritmo cuántico eficiente para el HSP para el grupo diédrico 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 polinomio de tiempo en . Para grupos arbitrarios, se sabe que el problema del subgrupo oculto se puede resolver utilizando un número polinómico 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 de Oracle y el tiempo de ejecución. La existencia de tal algoritmo para grupos arbitrarios está abierta. Existen algoritmos de tiempo polinómico cuántico para ciertas subclases de grupos, como los 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 desde hasta , el grupo lineal general sobre los números complejos . Una representación es irreductible si no puede expresarse como producto directo de dos o más representaciones de . Para un grupo abeliano, todas las representaciones irreductibles son los personajes , que son las representaciones de dimensión uno; No existen representaciones irreductibles de mayor dimensión para los 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 grupo de orden cíclico aditivo . Presentando al personaje ${\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 ${\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 como sigue:

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. Mida el registro de salida. Esto da algunos por algunos y colapsa el estado 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. Realiza 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 se puede medir 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 del paso 5 es igual al estado del 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}}}$$

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: ${\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}}}$$

Dejemos que sea la representación trivial, que asigna todas las entradas a , para obtener ${\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}}}$$

Dado que la suma se realiza de nuevo , ser trivial solo importa si es trivial ; es decir, si . Por lo tanto, sabemos que la suma dará como resultado if y resultará en if . ${\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 eso, ya que lo sabemos para todos . , o un grupo electrógeno para , se encontrará después de un número polinómico de mediciones. El tamaño de un grupo electrógeno será logarítmicamente pequeño en comparación con el tamaño de . Denotemos un conjunto generador para , es decir . El tamaño del subgrupo generado por se duplicará cuando se le agregue un nuevo elemento, porque y son disjuntos y porque . Por tanto, el tamaño de un grupo electrógeno satisface ${\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,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 de los subgrupos ocultos. La siguiente lista describe instancias importantes del HSP y si tienen solución o no.

Ver también

• Problema de turno oculto
• Dualidad de Pontryagin

Referencias

1. Mark Ettinger; Peter Hoyer (1999). "Un observable cuántico para el problema del isomorfismo gráfico". 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 la consulta cuántica del problema de subgrupos ocultos es polinómica". Cartas de procesamiento de información . 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 de los subgrupos ocultos
• Chris Lomont: El problema del subgrupo oculto: problemas de revisión y abiertos
• Problema de subgrupo oculto en arxiv.org
• Implementación completa del algoritmo de Shor para encontrar logaritmos discretos con Classiq