El problema del subgrupo oculto ( 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 gráfico 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 cuántico de Shor para la factorización es esencialmente equivalente al 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 G , un subgrupo H ≤ G y un conjunto X , decimos que una función f : G → X oculta el subgrupo H si para todo g 1 , g 2 ∈ G , f ( g 1 ) = f ( g 2 ) si y sólo si g 1 H = g 2 H . De manera equivalente, la función f es constante en las clases laterales de H , mientras que es diferente entre las diferentes clases laterales de H .
Ocultos problema subgrupo : Let G ser un grupo, X un conjunto finito, y f : G → X una función que oculta un subgrupo H ≤ G . La función f se da a través de un oráculo , que usa bits O (log | G | + log | X |). Usando la información obtenida de las evaluaciones de f a través de su oráculo, determinar un grupo electrógeno para H .
Un caso especial es cuando X es un grupo yf es un homomorfismo de grupo, en cuyo caso H corresponde al núcleo de 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 cuántico de Shor para factorización y logaritmo discreto (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 de grafos y ciertos problemas de vector más corto (SVP) en retículas. 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 diedro daría un algoritmo cuántico para el poli ( n ) único SVP. [2]
Algoritmos
Existe un algoritmo cuántico de tiempo polinomial para resolver HSP sobre grupos abelianos finitos . (En el caso de un problema de subgrupo oculto, "un algoritmo de tiempo polinomial" significa un algoritmo cuyo tiempo de ejecución es un polinomio del logaritmo del tamaño del grupo). El algoritmo de Shor aplica un caso particular de este algoritmo cuántico.
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] Este resultado, sin embargo, permite al algoritmo cuántico un tiempo de ejecución exponencial en log | G |. Para diseñar algoritmos eficientes para el isomorfismo de grafos y SVP, se necesita un algoritmo para el cual tanto el número de evaluaciones de oráculo como el tiempo de ejecución sean polinomiales.
La existencia de tal algoritmo para grupos arbitrarios está abierta. Existen algoritmos de tiempo polinomial cuántico para ciertas subclases de grupos, como los productos semidirectos de algunos grupos abelianos .
El enfoque 'estándar' de este problema implica: la creación del estado cuántico , una transformada cuántica de Fourier posterior al registro izquierdo, después de lo cual se muestrea este registro. Se ha demostrado que este enfoque es insuficiente para el problema del subgrupo oculto del grupo simétrico. [4] [5]
Ver también
Referencias
- ^ Mark Ettinger; Peter Høyer. "Un observable cuántico para el problema de isomorfismo de grafos". arXiv : quant-ph / 9901029 .
- ^ Oded Regev. "Problemas de celosía y computación cuántica". arXiv : cs / 0304005 .
- ^ Mark Ettinger; Peter Hoyer; Emanuel Knill. "La complejidad de la consulta cuántica del problema del subgrupo oculto es polinomial". Cartas de procesamiento de información . 91 : 43–48. arXiv : quant-ph / 0401083 . doi : 10.1016 / j.ipl.2004.01.024 .
- ^ Sean Hallgren; Martin Roetteler; Pranab Sen. "Limitaciones de los estados cuánticos de Coset para el isomorfismo gráfico". arXiv : quant-ph / 0511148 .
- ^ Cristopher Moore, Alexander Russell, Leonard J. Schulman . "El grupo simétrico desafía el muestreo de Fourier fuerte: parte I". arXiv : quant-ph / 0501056 .CS1 maint: varios nombres: lista de autores ( enlace )
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