Algoritmos Quânticos para o Problema do Subgrupo Escondido em Produtos
Semi-diretos de Grupos
Demerson N. Gonçalves, Carlos Magno M. Cosme e Renato Portugal
Laboratório Nacional de Computação Científica, Petrópolis,
email: {dnunes,cmagno,portugal}@lncc.br
Introdução
O Grupo G = Zm
pr ⋊φ Zp
Computadores quânticos prometem resolver certos problemas
assintoticamente mais rápido do que seus equivalentes clássicos. Em particular, Shor descobriu um algoritmo quântico eficiente para fatoração e cálculo de logaritmo discreto. Esse algoritmo permite a quebra dos principais códigos de criptografia
usados atualmente, como RSA, Diffie-Hellman e ElGamal. A
maior parte dos algoritmos quânticos com ganho exponencial
em relação aos seus equivalentes clássicos, tais como, o algoritmo de Shor, pode ser considerada como um caso particular
do chamado Problema do Subgrupo Escondido (PSE). O PSE
consiste em achar os geradores de um subgrupo H de um determinado grupo finito G com uma função oráculo f definida em
G tal que f (a) = f (b) se, e somente se, aH = bH para todo
a, b ∈ G. O PSE em grupos abelianos é resolvido eficientemente
num computador quântico. Uma questão natural é perguntar se
computadores quânticos podem resolver o PSE em grupos não
abelianos. Esta questão tem sido discutida regularmente pela comunidade científica devido a importantes aplicações, como por
exemplo, no problema de isomorfismo de grafos, quando o grupo
em questão é o grupo Simétrico. Além do grupo Simétrico,
Regev [6] mostrou que uma solução eficiente para o PSE no
grupo Diedral implica num algoritmo eficiente para o problema
de determinar o menor vetor em um reticulado, ou pelo menos
para uma classe de reticulados para o qual nenhum algoritmo
clássico é conhecido.
Sejam p um número primo ímpar, r e n inteiros positivos. Considere o homomorfismo de grupos
A Transformada de Fourier
A principal ferramenta usada por algoritmos quânticos em tempo
polinomial para o PSE é a Transformada de Fourier (TF) em grupos. Para grupos não abelianos a TF é descrita em termos das representações irredutíveis do grupo, isto é, homomorfismos ρ de
G no conjunto GL(V ) das matrizes invertíveis sobre V , onde V é
um espaço de dimensão finita qualquer. Assim, dada uma função
f : G → C e uma representação irredutível ρ de G de dimensão
dρ, podemos definir a TF de f na representação ρ como sendo
fb(ρ)
=
s
dρ X
f (g)ρ(g).
|G| g∈G
Para grupos abelianos, as representações irredutíveis são unidimensionais, no entanto, se G é um grupo não abeliano, então
existe pelo menos uma representação irredutível de G com dimensão maior que um. Neste caso, a TF depende da escolha da
base para as representações irredutíveis, dificultando a extensão
do algoritmo quântico abeliano para o cenário não abeliano.
Atacando o PSE não Abeliano
Uma outra forma de encarar o PSE não abeliano é caracterizar
todos os subgrupos de um dado grupo e então determinar um
algoritmo quântico que se aplique a estes subgrupos utilizando
a TF abeliana. Esta estratégia foi primeiramente estudada por
[3] e [4]. Inui e Le Gall [4] apresentaram um algoritmo quântico eficiente para o PSE em grupos da forma Zpr ⋊ Zp com p
primo. Mais tarde, utilizando o método de Inui e Le Gall, Chi
et al.[2] encontraram uma solução para o PSE sobre ZN ⋊ Zp,
onde N é fatorado como N = pr11 pr22 · · · prnn e p um primo ímpar que não divide cada pj − 1. Ainda nesta direção, Bacon et
al.[1] mostraram que para determinar uma solução para PSE sobre grupos da forma A ⋊ Zp, com A abeliano e p um número
primo, basta considerar o PSE para subgrupos de ordem p em
A2 ⋊ Zp, onde A2 é um subgrupo de A dado por A2 := AA1 com
A1 satisfazendo H1 := H ∩ A × {0} := A1 × {0}. Este trabalho
foi uma generalização do trabalho de Ettinger e Høyer [3]. Estes
autores mostraram que para o grupo Diedral, é suficiente considerar os casos onde o subgrupo escondido é trivial ou gerado por
uma reflexão.
Neste trabalho, utilizando as técnicas mencionadas, nós esboçaremos uma solução para o PSE sobre Zm
pr ⋊ Zp com p primo,
r, m inteiros positivos, quando o subgrupo escondido for de ordem p. Não é conhecida na literatura nenhuma solução para o
PSE sobre Zm
pr ⋊φ Zp, em particular, Bacon et al.[1] resolveram o
PSE para grupos da forma Zm
p ⋊ Zp.
†
3. Meça o último registrador
p−1
X
φ : Zp −→
≈ GL(m, Zpr )
1 7−→ φ(1) := φ1 = (pr−1 + 1)Im×m,
4. Aplique a TF abeliana para cada registrador
p−1
X
onde Im×m é a matriz identidade m × m. Dado este homomorfismo, podemos definir o produto semi-direto de grupos
G = Zm
pr ⋊φ Zp.
(a, b).(a′, b′) = (a + φb1a′, b + b′)
= (a + (pr−1 + 1)ba′, b + b′).
Fazendo x1 = (1, 0, . . . , 0, 0), . . . , xm = (0, . . . , 0, 1, 0), y =
(0, . . . , 0, 1), temos que {x1, . . . , xm, y} forma um conjunto gerador para G e este conjunto goza das seguintes propriedades:
•(
•(
a(bpr−1+1)
xi
y
Qm
aj b k
j=1 xij
aj b p
y) =
Qm
k(k−1)bpr−1
aj
2
j=1 xij )
Qm
j=1 xij
r
aj p
Qm
aj k bk
x
y
j=1 ij
Lema 1 Para todo 0 ≤ a1, . . . , am ≤ pr − 1, 0 ≤ b ≤ p − 1 e
d = mdc(a1, . . . , am, pr )
xai11 . . . xaimm y b
r
p
kam kb
1
= {xka
.
.
.
x
− 1}.
i1
im y | 0 ≤ k ≤
d
O teorema que daremos a seguir caracteriza todos os subgrupos
de ordem p de G.
Teorema 1 Os subgrupos cíclicos de
forma
pr−1 t2pr−1
tmpr−1
x1 x2
. . . xm
...,
pr−1
xm
e
,
Zm
pr ⋊φ Zp
de ordem p são da
pr−1 t3pr−1
tmpr−1
x2 x3
. . . xm
t1pr−1 t2pr−1
tmpr−1
x1 x2
. . . xm y
,
,
onde 0 ≤ t1, . . . , tm ≤ p − 1.
Algoritmo Quântico
Aqui, nós apresentaremos um algoritmo quântico para o PSE sobre Zm
pr ⋊φ Zp, quando o subgrupo escondido for de ordem p. Assim, seja G = Zm
pr ⋊φ Zp, H ≤ G e f a função que esconde as
classes laterais de H em G.
faça H ′ := H ∩ x1, . . . , xm
se H ′ 6= {e} então
chame o PSE abeliano e obtenha os geradores de H’
faça H := H ′
senão
se H = {e}
de H
a saída são os geradores
t1pr−1 t2pr−1
tmpr−1
x1 x2
. . . xm y
se H =
encontre t1, . . . , tm
Determinando t1, . . . , tm
Por simplicidade faremos m = 2, mas o resultado segue para
qualquer m ∈ N.
1. Prepare o estado
|ψi =
p−1
X
a′1,a′2,b=0
2. Faça a′i = ai + bti
p−1
X
a1,a2,b=0
|α1i |α2i |di
α1,α2,d=0
α1t1 + α2t2 + d ≡ 0 mod p.
Agora basta resolver o sistema linear de equações modulares e
determinar t1 e t2.
O circuito abaixo corresponde ao estado |ψi do algoritmo. Para
preparar este estado, nós utilizamos os seguintes operadores
unitários
Uf (|gi |hi) = |gi |f (g) + hi e Uy |gi = |ygi .
E
′ r−1
′ r−1
p
p
a
a
|a′1i |a′2i |bi f (x1 1 x2 2 y b)
|bi
|ei
|a′1i
•
|a′2i
onde 0 ≤ a1, . . . , an ≤ p − 1, 0 ≤ b ≤ p − 1, i = 1, . . . , m e
k ∈ N.
Agora nós podemos estabelecer o seguinte lema.
e
|a′1i
j=1 xij y ) = (
Qm
(α1 t′1 +α2 t′2 )b
2πi
p
5. Medindo todos os registradores, obtemos α1, α2 e d tais que
Os elementos em G tem a forma (a, b) onde a ∈ Zm
pr e b ∈ Zp e a
operação do grupo é dada como segue:
=
|a1 + bt1i |a2 + bt2i |bi
b=0
Aut(Zm
pr )
• y bxai
†
RJ
|a′2i
•
•
Uy
|bi
r−1
Uxp2
r−1
Uxp1
Uf
|0i
′ r−1 ′ r−1 E
ap
a1p
x2 2 y b
x 1
E
a′1pr−1 a′2pr−1 b
f (x1
x2
y)
Os detalhes das portas lógicas controladas do circuito acima podem ser encontrados em [5].
Conclusões
Neste trabalho, tratamos produtos semi-diretos de grupos da
forma Zm
pr ⋊φ Zp para um homomorfismo φ específico e exibimos
um algoritmo quântico que resolve o PSE quando o subgrupo escondido possui ordem p. Todavia, não resolvemos o problema
para o caso geral onde H é um subgrupo qualquer de G. De fato,
note que Zm
pr ⋊ Zp é da forma A ⋊ Zp, com A abeliano e p primo,
logo, podemos usar a redução do Bacon et al.[1]. Entretanto,
para este caso, a redução não dá informação sobre o subgrupo
escondido, pois, A2 não possui a mesma estrutura de Zm
pr . Temos
a expectativa que, combinando as idéias até aqui utilizadas com
a estrutura de um novo grupo (Zpr1 × . . . × Zprm ) ⋊φ Zp possamos
resolver o PSE sobre Zm
pr ⋊φ Zp. Estamos trabalhando também
com produtos semi-diretos da forma Zm
2pr ⋊φ Zp e Zpr ⋊φ Zq . Acreditamos que estas classes de produtos semi-diretos são bons candidatos para nos conduzir a uma solução do PSE em produtos
semi-diretos mais genéricos.
Agradecimentos
D.N.G é Bolsista da CAPES. C.M.M.C é Bolsista do CNPq.
Referências
[1] A. M. Childs D. Bacon and W. van Dam. From optimal measurement to efficient quantum
algorithms for the hidden subgroup problem over semidirect product groups. arXiv:quantph/0504083, 2.
[2] J. S. Kim D. P. Chi and S. Lee. Notes on the hidden subgroup problem on some semidirect product groups. arXiv:quant-ph/0604172, 1.
[3] M. Ettinger and P. Høyer. On Quantum Algorithms for Noncommutative Hidden Subgroups. Adv. Appl. Math., 25(3):239–251, 2000.
[4] Y. Inui and F. Le Gall. An efficient quantum algorithm for the hidden subgroup problem
over a class of semi-direct product group. arXiv:quant-ph/0412033, 2.
[5] R. Portugal, C.M.M. Cosme, and D. N. Gonçalves. Algoritmos Quânticos. Trabalho publicado nos anais do 1st WECIQ, Pelotas, Outubro 2006.
[6] O. Regev. Quantum computation and Lattice Problems. 43rd Symposim on Foundations
of Computer Science.
E
a1pr−1 a2pr−1
|a1 + bt1i |a2 + bt2i |bi f (x1
x2
)
Endereço para correspondências: Laboratório Nacional de Computação Científica, Av. Getúlio Vargas, 333, Sala 1a44, Quitandinha, Petrópolis, RJ, 25651-075