ads:
Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica
Programa de P´os Gradua¸c˜ao em Modelagem Computacional
Algoritmos Quˆanticos para o Problema do Isomorfismo
de Grafos
Por
Edinel¸co Dalcumune
PETR
´
OPOLIS, RJ - BRASIL
MAR¸CO DE 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ALGORITMOS QU
ˆ
ANTICOS PARA O PROBLEMA DO
ISOMORFISMO DE GRAFOS
Edinel¸co Dalcumune
DISSERTA¸C
˜
AO SUBMETIDA AO CORPO DOCENTE DO LABORAT
´
ORIO
NACIONAL DE COMPUTA¸C
˜
AO CIENT
´
IFICA COMO PARTE DOS REQUI-
SITOS NECESS
´
ARIOS PARA A OBTEN ¸C
˜
AO DO GRAU DE MESTRE EM
MODELAGEM COMPUTACIONAL
Aprovada por:
Prof. Renato Portugal, D.Sc
(Presidente)
Prof. Gilson Antˆonio Giraldi, D.Sc.
Prof. Celina Miraglia Herrera de Figueiredo, D.Sc.
PETR
´
OPOLIS, RJ - BRASIL
MAR¸CO DE 2008
ads:
Dalcumune, Edinel¸co
D138a Algoritmos quˆanticos para o problema do isomorfismo de grafos /
Edinel¸co Dalcumune. Petr´opolis, RJ. : Laborat´orio Nacional de Computa¸c˜ao
Cient´ıfica, 2008.
xiii, 75 p. : il.; 29 cm
Orientador: Renato Portugal
Disserta¸c˜ao (M.Sc.) – Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica,
2008.
1. Computa¸c˜ao Quˆantica. 2. Isomorfismo de Grafos. 3. Interse¸c˜ao de
Grupos. 4. Algoritmos Quˆanticos. I. Portugal, Renato. II. LNCC/MCT.
III. T´ıtulo.
CDD 004.1
“S´abio ´e aquele que conhece os limites da
pr´opria ignorˆancia.” (S´ocrates)
iv
Para meus pais e irm˜aos.
v
Agradecimentos
Agrade¸co ...
A meus pais e irm˜aos pelo apoio.
A todos os professores que ao longo da minha vida tˆem contribu´ıdo para
minha forma¸c˜ao, em especial o professor Renato Portugal pela orienta¸c˜ao e amizade.
Aos colegas do grupo de computa¸c˜ao quˆantica do LNCC.
Ao LNCC, a seus professores e funcion´arios.
A todos os colegas de gradua¸c˜ao e `as amizades que o mestrado tornou pos-
s´ıveis.
A FAPERJ pelo apoio financeiro.
vi
Resumo da Disserta¸c˜ao apresentada ao LNCC/MCT como parte dos requisitos
necess´arios para a obten¸c˜ao do grau de Mestre em Ciˆencias (M.Sc.)
ALGORITMOS QU
ˆ
ANTICOS PARA O PROBLEMA DO
ISOMORFISMO DE GRAFOS
Edinel¸co Dalcumune
Mar¸co, 2008
Orientador: Renato Portugal, D.Sc
O problema do isomorfismo de grafos possui aplica¸c˜oes em diversas ´areas da
ciˆencia. Tal problema n˜ao possui uma solu¸c˜ao eficiente para o seu caso geral. No
presente trabalho, apresentamos os conceitos b´asicos em teoria de grupos, teoria
dos grafos e mecˆanica quˆantica. Apresentamos o problema do subgrup o oculto e
uma conhecida redu¸c˜ao polinomial do problema do isomorfismo de grafos no seu
caso geral para o problema do subgrupo oculto sobre o grupo sim´etrico. Utilizamos
um m´etodo que reduz o problema do isomorfismo de grafos para o problema de
interse¸c˜ao de grupos. Este m´etodo utiliza resultados da computa¸c˜ao quˆantica e da
teoria dos grupos sol´uveis, nos permitindo obter uma solu¸c˜ao eficiente atrav´es de
um algoritmo quˆantico para o problema do isomorfismo de grafos para uma classe
particular de grafos.
vii
Abstract of Dissertation presented to LNCC/MCT as a partial fulfillment of the
requirements for the degree of Master of Sciences (M.Sc.)
QUANTUM ALGORITHMS FOR THE GRAPH ISOMORPHISM
PROBLEM
Edinel¸co Dalcumune
March, 2008.
Advisor: Renato Portugal, D.Sc
The graph isomorphism problem has applications in several areas of science.
This problem has not an efficient solution to its general case. In this work, we
present the basic concepts of group theory, graph theory and quantum mechanics.
We introduce the hidden subgroup problem and a known polynomial reduction of
the graph isomorphism problem in its general case to the hidden subgroup prob-
lem on the symmetric group. We use a method that reduces the graph isomor-
phism problem to the group intersection problem. This method combines results
from quantum computing and solvable group theory providing a efficient solution
through a quantum algorithm to the graph isomorphism problem for the particular
class of graphs.
viii
Sum´ario
1 Introdu¸c˜ao 1
2 Teoria de Grupos 5
2.1 Teoria B´asica de Grupos . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 O Grupo Sim´etrico . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Grupos Sol´uveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Teoria dos Grafos 15
3.1 No¸c˜oes B´asicas de Grafos . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2 Problema do Isomorfismo de Grafos . . . . . . . . . . . . . . . . . . 18
3.3 Problema do Automorfismo de Grafos . . . . . . . . . . . . . . . . . 20
3.4 Rela¸c˜oes entre Isomorfismos e Automorfismos de Grafos . . . . . . . 21
4 Descri¸c˜ao Matem´atica do Problema do Isomorfismo de Grafos 25
4.1 Isomorfismos de Grafos e Interse¸c˜ao de Grupos . . . . . . . . . . . . 25
4.2 Grafos com grupo de automorfismos sol´uvel . . . . . . . . . . . . . 29
4.3 Problemas de Reconhecimento de Linguagens e Classes de Comple-
xidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.4 Algoritmos Cl´assicos . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.4.1 Algoritmos Cl´assicos para certas classes de grafos . . . . . . 36
5 Computa¸c˜ao Quˆantica 38
5.1 Mecˆanica Quˆantica . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
ix
5.2 Operadores Unit´arios . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3 Problema do Subgrupo Oculto . . . . . . . . . . . . . . . . . . . . . 43
5.3.1 Problema do Subgrupo Oculto Abeliano . . . . . . . . . . . 44
5.3.2 Problema do Subgrupo Oculto N˜ao Abeliano . . . . . . . . . 48
6 Aplica¸c˜oes da Computa¸c˜ao Quˆantica ao Problema do Isomorfismo de Grafos 51
6.1 Redu¸c˜ao do Problema do Isomorfismo de Grafos para o Problema
do Subgrupo Oculto . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6.2 Grupos Or´aculo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.3 Problemas relacionados com o Problema do Subgrupo Oculto . . . . 55
6.4 Algoritmo Quˆantico . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
6.5 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
7 Conclus˜ao 64
Referˆencias Bibliogr´aficas 66
Apˆendice
A Os Postulados da Mecˆanica Quˆantica 74
x
Lista de Figuras
Figura
3.1 As gravuras ilustrando o documento de Euler de 1736 sobre as pontes
de K
¨
onigsberg. Fonte: Alexanderson (2006) . . . . . . . . . . . . . 16
3.2 Grafo do Problema das Sete Pontes de K
¨
onigsberg. . . . . . . . . . 16
3.3 Par de Grafos com 4 isomorfismos. . . . . . . . . . . . . . . . . . . 19
3.4 Par de grafos n˜ao isomorfos. . . . . . . . . . . . . . . . . . . . . . . 19
3.5 Grafos isomorfos para ilustrar o Teorema 8 e seus corol´arios. . . . . 23
4.1 grafo Γ = (V, E) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 Exemplo de um grafo da classe A
n
, com n = 3. . . . . . . . . . . . . 30
4.3 Este diagrama ilustra as conhecidas rela¸c˜oes entre algumas das mais
importantes classes de complexidades. Atualmente, nenhuma das
inclus˜oes s˜ao sabidas serem estritas. Por exemplo, atualmente n˜ao
existe qualquer prova de que P = PESPA ¸CO. . . . . . . . . . . . 34
6.1 Grafo Γ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6.2 Grafo σΓ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
xi
Lista de Siglas e Abreviaturas
• g
1
, . . . , g
k
: Conjunto gerado por g
1
, . . . , g
k
• (G : H): ´ındice de H em G
• G/H: Grupo quo ciente de G por H
• [H : K]: Comutador dos subgrupos H e K
• P(S): Conjunto das bije¸c˜oes de S em S
• S
n
: Grupo Sim´etrico de grau n
• H
⊥
: Subgrupo ortogonal de G
• ω
t
: Raiz complexa t-´esima da unidade, ω
t
= e
2πi
t
• log: Logaritmo na base 2
• O(·): Complexidade Computacional no pior caso; diz-se f(x) = O(g(x)) se ∃ C, x
0
tal
que |f(x)| < Cg(x), ∀ x > x
0
• Iso(Γ
1
, Γ
2
): Conjunto de isomorfismos entre um grafo Γ
1
e um grafo Γ
2
• Aut(Γ): Grupo de automorfismos de um grafo Γ
• P
1
∝
p
P
2
: O problema P
1
´e redut´ıvel polinomialmente a um problema P
2
• PIG: Problema do Isomorfismo de Grafos
• PAG: Problema do Automorfismos de Grafos
• ·: Maior n´umero inteiro que seja menor ou igual a ·
• ·: Menor n´umero inteiro que seja maior ou igual a ·
• (·)
∗
: Complexo conjugado
• (·)
T
: Transposto
• (·)
†
: Transposto conjugado
• |ψ: Vetor (em nota¸c˜ao de Dirac), tamb´em chamado ket
xii
• ψ|: Vetor dual (em nota¸c˜ao de Dirac), tamb´em chamado bra
• ϕ|ψ: Produto escalar entre |ϕ e |ψ
• |ϕ ⊗|ψ: Produto tensorial entre |ϕ e |ψ
• |ϕψ|: Produto tensorial entre |ϕ e |ψ
• V ⊗ W : Produto tensorial entre V e W
• |ψ
⊗k
: Produto tensorial de |ψ por ele mesmo k vezes
• PSO: Problema do Subgrupo Oculto
xiii
Cap´ıtulo 1
Introdu¸c˜ao
Estruturas qu´ımicas po dem ser descritas em termos da teoria de grafos; ´ato-
mos s˜ao interpretados como v´ertices e as liga¸c˜oes s˜ao interpretadas como arestas. O
problema de isomorfismo de grafos tem atra´ıdo muitos pesquisadores devido a in´u-
meras aplica¸c˜oes pr´aticas em v´arias ´areas da ciˆencia, como por exemplo, qu´ımica
[Liu e Klein (1991), Raymond e Willett (2002), Valiente (2002)], biologia com-
putacional [Valiente (2002), Gan et al. (2003)], entre outras [K
¨
obler et al. (1993),
Fortin (1996)]. Al´em, ´e claro, da computa¸c˜ao te´orica, sendo assim um grande de-
safio matem´atico. Este problema pertence `a classe dos problemas NP, mas n˜ao se
sabe se est´a nas classes P ou NP-Completa [Papadimitriou (1994), Kaye et al.
(2007)]. Existem fortes evidˆencias de que n˜ao perten¸ca a classe NP-Completa.
O Problema de isomorfismo de grafos pode ser visto da seguinte forma: Sejam
Γ
1
e Γ
2
dois grafos n˜ao-orientados sobre os v´ertices V = {v
1
, . . . , v
n
}. S˜ao Γ
1
e Γ
2
isomorfos? Ou seja, existe uma fun¸c˜ao bijetora ϕ : V → V tal que a aresta (v
i
, v
j
)
estar´a contida em Γ
1
se e somente se (ϕ(v
i
), ϕ(v
j
)) estiver contida em Γ
2
?
N˜ao ´e conhecido na literatura um algoritmo cl´assico eficiente para o problema
do isomorfismo de grafos para o caso geral. O melhor algoritmo conhecido para tal
problema “roda”em tempo e
O(
√
n log n)
[Babai (1980), Babai e Luks (1983), Zemly-
achenko et al. (1985)]. Dizemos que tal algoritmo ´e subexponencial no n´umero de
v´ertices dos grafos de entrada. Existem algoritmos cl´assicos eficientes para algu-
mas classes de grafos, ou seja, algoritmos polinomiais no n´umero de v´ertices dos
1
grafos de entrada. Contudo, o problema geral continua desafiando a comunidade
cient´ıfica.
A Computa¸c˜ao Quˆantica [Nielsen e Chuang (2000), Kaye et al. (2007)] ´e
uma ´area de pesquisa recente que utiliza elementos de trˆes ´areas importantes:
Matem´atica, F´ısica e Computa¸c˜ao. O objetivo da Computa¸c˜ao Quˆantica ´e estudar
m´etodos para processar, transmitir e armazenar informa¸c˜oes contidas em esta-
dos quˆanticos. Os seguintes questionamentos nos motivam a estudar Computa¸c˜ao
Quˆantica: Existem problemas que os computadores quˆanticos podem resolver mais
rapidamente do que os cl´assicos? O que faz os computadores quˆanticos serem mais
eficientes do que os cl´assicos?
A Computa¸c˜ao Quˆantica nasce no in´ıcio da d´ecada de 1980 quando Feyn-
man apontou a existˆencia de grandes dificuldades para simular sistemas quˆanticos
em computadores cl´assicos, sugerindo que a constru¸c˜ao de computadores baseados
nos princ´ıpios da Mecˆanica Quˆantica evitaria tais dificuldades [Feynman (1982)].
Os argumentos de Feynman estimularam David Deutsch a generalizar o modelo
mais fundamental da Computa¸c˜ao Cl´assica, a saber, a m´aquina de Turing, para o
seu equivalente quˆantico num trabalho hist´orico [Deutsch (1985)]. Posteriormente,
generalizou tamb´em o modelo de circuitos baseados em portas l´ogicas. Oper-
adores unit´arios tomaram o lugar das usuais portas l´ogicas AND, OR e NOT. Em
1994, [Shor (1994)] construiu com base nos trabalhos de [Deutsch (1985)] e [Simon
(1994)] um algoritmo quˆantico que pode fatorar inteiros grandes exponencialmente
mais r´apido do que qualquer m´etodo cl´assico conhecido. Esse algoritmo permite a
quebra dos principais c´odigos de criptografia usados atualmente, como RSA, Diffie-
Hellman e ElGamal [Koblitz (1998)], caso um computador quˆantico de tamanho
razo´avel esteja dispon´ıvel.
A maioria dos algoritmos quˆanticos com ganho exponencial em rela¸c˜ao aos
seus equivalentes cl´assicos, tais como, o algoritmo de Shor, pode ser considerada
como um caso particular do chamado Problema do Subgrupo Oculto (PSO). O
PSO consiste em achar os geradores de um subgrupo H de um determinado grupo
2
finito G com uma fun¸c˜ao or´aculo f definida de G para um conjunto finito X tal
que f(a) = f(b) se, e somente se, aH = bH para todo a,b ∈ G.
No presente trabalho, veremos que o Problema do Isomorfismo de Grafos
pode ser visto como um Problema do Subgrupo Oculto n˜ao abeliano sobre o grupo
sim´etrico S
n
, como foi mostrado p or [Beals (1997), Ettinger e Høyer (1999), Jozsa
(2000), Ahn (2002), Lomont (2004)], onde devemos encontrar um conjunto de ge-
radores para o grupo de automorfismos do grafo, que ´e um subgrupo do grupo
sim´etrico S
n
. Utilizaremos o Problema de Interse¸c˜ao de Grup os de permuta¸c˜oes
[Hoffman (1979), Fenner e Zhang (2005)], juntamente com resultados da Com-
puta¸c˜ao Quˆantica para determinar, dado o est´agio atual de desenvolvimento da
Computa¸c˜ao Quˆantica a existˆencia de algoritmos quˆanticos eficientes para o Pro-
blema do Isomorfismo de Grafos em muitas classes de grafos ou n˜ao. Mostraremos
que para a classe de grafos A
n
esse m´etodo empregado produz um algoritmo quˆan-
tico eficiente, com algumas restri¸c˜oes. Mostrando assim, aplica¸c˜oes da Computa¸c˜ao
Quˆantica ao Problema do Isomorfismo de Grafos.
No cap´ıtulo 2, apresentaremos uma revis˜ao de t´opicos de teoria de grupos
necess´arios ao entendimento do restante da disserta¸c˜ao. Inclui-se nessa revis˜ao
conceitos sobre o grupo sim´etrico e grupos sol´uveis. No cap´ıtulo 3, daremos as
no¸c˜oes b´asicas sobre teoria dos grafos. Ainda no cap´ıtulo 3, enunciaremos os pro-
blemas do isomorfismo e automorfismo de grafos, bem como, rela¸c˜oes entre os dois
problemas. No cap´ıtulo 4, apresentaremos uma descri¸c˜ao matem´atica do problema
do isomorfismo de grafos. Definiremos o problema de interse¸c˜ao de grup os e sua
rela¸c˜ao com o problema do isomorfismo de grafos. Daremos exemplos de grafos, in-
cluindo classes onde o problema do isomorfismo de grafos ´e resolvido eficientemente
num computador cl´assico. Ainda no cap´ıtulo 4, mostraremos a complexidade de
tal problema. No cap´ıtulo 5, faremos uma revis˜ao sobre mecˆanica quˆantica. Apre-
sentaremos tamb´em o problema do subgrupo oculto e o algoritmo quˆantico para
o caso abeliano. Finalmente, no cap´ıtulo 6, apresentaremos aplica¸c˜oes da com-
puta¸c˜ao quˆantica para o problema do isomorfismo de grafos, incluindo uma vis˜ao
3
do problema do isomorfismo de grafos como um problema do subgrupo oculto.
Ainda neste cap´ıtulo, daremos um algoritmo quˆantico eficiente usando o problema
de interse¸c˜ao de grupos para resolver o problema do isomorfismo de grafos para
uma classe particular de grafos, como foi dito no par´agrafo anterior.
4
Cap´ıtulo 2
Teoria de Grupos
Neste cap´ıtulo, apresentamos uma revis˜ao de t´opicos de Teoria de Grup os
necess´arios ao entendimento do restante da disserta¸c˜ao. Seguimos a linguagem
cl´assica de
´
Algebra [Herstein (1986), Garcia e Lequain (2001)].
2.1 Teoria B´asica de Grupos
Nesta se¸c˜ao veremos algumas defini¸c˜oes b´asicas e exemplos da Teoria de
Grupos que ser˜ao necess´arios para o entendimento do restante do trabalho.
Defini¸c˜ao 1 Um conjunto n˜ao-vazio G ´e dito um grupo se em G existe uma
opera¸c˜ao (∗) definida tal que:
(i) a, b ∈ G implica que a ∗ b ∈ G.
(ii) Dados a, b, c ∈ G, ent˜ao a ∗ (b ∗ c) = (a ∗ b) ∗ c.
(iii) ∃ e ∈ G; a ∗ e = e ∗ a = a, ∀ a ∈ G.
(iv) ∀ a ∈ G, ∃ b ∈ G; a ∗ b = b ∗ a = e (b = a
−1
).
Por simplicidade denotaremos a ∗ b por ab para todo a, b ∈ G.
Defini¸c˜ao 2 Se G ´e um grupo tal que ab = ba, ∀ a, b ∈ G, n´os dizemos que G ´e
um grupo abeliano.
5
Defini¸c˜ao 3 Seja G um grupo. Um subconjunto n˜ao-vazio H de G ´e um sub-
grupo de G (denotamos H ≤ G) quando, com a opera¸c˜ao de G, o conjunto H ´e
um grupo.
Proposi¸c˜ao 1 Seja H um subconjunto n˜ao-vazio do grupo G. Ent˜ao H ´e um
subgrup o de G se e somente se as duas condi¸c˜oes seguintes s˜ao satisfeitas:
1) h
1
h
2
∈ H, ∀ h
1
, h
2
∈ H.
2) h
−1
∈ H, ∀ h ∈ H.
Lema 1 Seja G um grupo e H um subconjunto finito n˜ao-vazio de G fechado sobre
a opera¸c˜ao em G. Ent˜ao H ´e um subgrupo de G.
Demonstra¸c˜ao: Vide [Herstein (1986)].
Corol´ario 1 Se G ´e um grupo finito e H ´e um subconjunto n˜ao-vazio de G fechado
sobre a opera¸c˜ao em G, ent˜ao H ´e um subgrupo de G.
Defini¸c˜ao 4 Seja G um grupo.
(i) A ordem de G (denotamos |G|) ´e a cardinalidade do conjunto G.
(ii) Se a ∈ G, ent˜ao a ordem do elemento a (denotamos |a| ou o(a)) ´e o menor
inteiro positivo n tal que a
n
= e (Se n n˜ao existir, dizemos que o(a) = ∞).
(iii) O expoente de G, exp(G) ´e o menor inteiro positivo m tal que a
m
= e para
todo a ∈ G (Se m n˜ao existir, dizemos que exp(G) = ∞).
Dizemos que um conjunto de elementos g
1
, ..., g
k
gera um grupo G se cada
elemento de G puder ser escrito como um produto de elementos (e seus inversos)
da lista g
1
, ..., g
k
e denota-se G = g
1
, ..., g
k
.
O seguinte teorema ´e importante pois tem implica¸c˜oes em algoritmos quˆan-
ticos.
6
Teorema 1 Todo grupo G de ordem finita |G| > 1 admite um conjunto gerador
de tamanho no m´aximo log
2
|G|.
Demonstra¸c˜ao: Vide [Hoffman (1979)].
Defini¸c˜ao 5 Um grupo G ´e dito c´ıclico se existe algum elemento g ∈ G tal que
g = G. Neste caso, g ´e dito gerador de G.
O grupo Z com a op era¸c˜ao de adi¸c˜ao ´e c´ıclico. Os grupos Z
n
com a opera¸c˜ao
de adi¸c˜ao m´odulo n s˜ao c´ıclicos. Note que se G ´e c´ıclico, ent˜ao G ´e abeliano.
Sendo (G
1
, ∗
1
) e (G
2
, ∗
2
) dois grupos. No conjunto G
1
×G
2
defina a opera¸c˜ao
(g
1
, g
2
) · (g
1
, g
2
) = (g
1
∗
1
g
1
, g
2
∗
2
g
2
)
Logo, (G
1
× G
2
, ·) ´e um grupo chamado produto direto de G
1
com G
2
. Mais
geralmente, dados grupos (G
1
, ∗
1
), . . . , (G
n
, ∗
n
), defina a no¸c˜ao de produto direto
G
1
× G
2
× . . . × G
n
.
Outro importante teorema que tem implica¸c˜oes em algoritmos quˆanticos ´e o
seguinte.
Teorema 2 (Teorema Fundamental sobre Grupos Abelianos Finitos) Um
grupo abeliano finito ´e o produto direto de grupos c´ıclicos.
Demonstra¸c˜ao: Vide [Herstein (1986)].
Seja G um grup o e H um subgrupo de G. Sendo x ∈ G, definimos uma
classe lateral `a esquerda de H em G como sendo o conjunto xH = {xh|h ∈ H}.
Em particular, H ´e uma classe lateral do elemento e `a esquerda. Analogamente,
definimos uma classe lateral `a direita de H em G como sendo o conjunto Hx =
{hx|h ∈ H}.
Duas classes laterais `a esquerda (direita) de H em G s˜ao disjuntas ou s˜ao
iguais. Portanto, podemos escrever G como uma uni˜ao disjunta de classes laterais,
ou seja, G = H ∪ x
1
H ∪ x
2
H ∪ ... ∪ x
r
H.
7
Defini¸c˜ao 6 A cardinalidade do conjunto das classes laterais `a esquerda (direita)
´e o ´ındice de H em G; ele ser´a denotado por (G : H).
Tomando um conjunto de representantes das classes laterais `a esquerda de
H em G (um elemento de cada classe lateral) vemos que a cardinalidade deste
conjunto ´e igual a (G : H).
Proposi¸c˜ao 2 Todas as classes laterais de H em G tˆem a mesma cardinalidade,
igual `a cardinalidade de H.
Teorema 3 (Teorema de Lagrange) Sejam G um grupo finito e H um sub-
grupo de G. Ent˜ao |G| = |H|(G : H); em particular, a ordem e o ´ındice de H
dividem a ordem de G.
Suponha que G ´e um grupo. Dois elementos a e b de G s˜ao chamados
conjugados se existe um elemento g ∈ G com gag
−1
= b. Al´em disso, dado
qualquer subconjunto S de G (S n˜ao necessariamente um subgrupo), definimos
um subconjunto T de G como conjugado a S se e somente se existe algum g ∈ G
tal que T = gSg
−1
.
Seja G um grupo e seja H um subgrupo de G. A opera¸c˜ao de G induz de
maneira natural uma opera¸c˜ao sobre o conjunto de classes laterais `a esquerda de
H em G, isto ´e, a opera¸c˜ao
(xH, yH) → xyH
´e bem definida, no sentido de n˜ao depender da escolha dos representantes x e y.
Defini¸c˜ao 7 Um subgrupo N de G ´e um subgrupo normal de G se g
−1
Ng = N
para todo g ∈ G. Denotamos por N ✁ G. Neste caso, as classes laterais `a esquerda
de N s˜ao iguais `as classes laterais `a direita de N; vamos cham´a-las de classes
laterais de N.
Os grupos {e}, G s˜ao subgrup os normais de G. Dados dois grupos G e H,
se (G : H) = 2, ent˜ao H ✁ G.
8
Teorema 4 Sejam G um grupo e H um subgrupo normal de G. Ent˜ao o conjunto
das classes laterais, com a opera¸c˜ao induzida de G, ´e um grupo.
Defini¸c˜ao 8 Sejam G um grupo e H um subgrupo normal de G. O grupo de suas
classes laterais com a opera¸c˜ao induzida de G ´e o grupo quociente de G por H;
ele ser´a denotado por G/H ou por
G
H
.
Seja D
n
o grupo n˜ao-abeliano chamado grupo diedral ou grupo de simetrias
do pol´ıgono regular de n v´ertices, que ´e formado pelas rota¸c˜oes e reflex˜oes do plano
que preservam o pol´ıgono. Formalmente, temos
Defini¸c˜ao 9 Se denotarmos por ρ uma rota¸c˜ao do ˆangulo 2π/n e por σ uma
reflex˜ao em rela¸c˜ao a um eixo de simetria do pol´ıgono, ent˜ao o grupo diedral ´e
dado por
D
n
= ρ, σ = {e, ρ, ..., ρ
n−1
, σ, σρ, ..., σρ
n−1
}.
Este grupo possui uma apresenta¸c˜ao com geradores ρ e σ que est˜ao relaciona-
dos como a seguir
ρ
n
= σ
2
= e, ρσ = σρ
−1
.
O conjunto formado pelas rota¸c˜oes formam um subgrupo abeliano de D
n
que
denotaremos por C
n
.
2.2 O Grupo Sim´etrico
Defini¸c˜ao 10 Seja S um conjunto qualquer. Considere o conjunto P(S) = {f :
S → S|f ´e uma bije¸c˜ao}. O conjunto P(S) com a opera¸c˜ao composi¸c˜ao de fun¸c˜oes
´e um grupo, n˜ao-abeliano em geral. Quando S tem um n´umero finito de elemen-
tos, digamos n, ent˜ao P(S) tem um nome especial. Ele ser´a chamado o grupo
sim´etrico de grau n ou grupo das permuta¸c˜oes de n letras e ser´a denotado
por S
n
. Temos ainda que a ordem de S
n
´e n!.
9
´
E muito importante estudar os grupos S
n
e seus subgrupos devido ao teorema
abaixo.
Teorema 5 (Teorema de Cayley) Seja G um grupo finito de ordem n. Ent˜ao
G ´e isomorfo a um subgrupo de S
n
.
Se uma fun¸c˜ao f : S → S ´e uma bije¸c˜ao, ent˜ao f pode ser representada
por uma permuta¸c˜ao do conjunto S. Vamos usar a nota¸c˜ao de produtos de ciclos
para permuta¸c˜oes, como definimos abaixo. Composi¸c˜oes de permuta¸c˜oes s˜ao lidas
a partir da direita para a esquerda, isto ´e, se π, τ ∈ S
n
, ent˜ao πτ ´e a permuta¸c˜ao
que primeiro aplica τ e ent˜ao π.
Defini¸c˜ao 11 Uma permuta¸c˜ao σ ∈ S
n
´e chamada de r-ciclo se existem elementos
distintos i
1
, i
2
, ..., i
r
∈ {1, 2, ..., n} tais que σ(i
1
) = i
2
, σ(i
2
) = i
3
, ..., σ(i
r−1
) =
i
r
, σ(i
r
) = i
1
, e tais que σ(i
j
) = i
j
, ∀ j ∈ {1, 2, ..., n}\{i
1
, i
2
, ..., i
r
}; tal r-ciclo ser´a
denotado por (i
1
...i
r
); o n´umero r ´e chamado o comprimento do ciclo. Os 2-ciclos
s˜ao tamb´em chamados de transposi¸c˜oes.
Sendo σ ∈ S
n
um r-ciclo e τ ∈ S
n
um s-ciclo, dizemos que as permuta¸c˜oes σ
e τ s˜ao disjuntas se nenhum elemento de {1, 2, ..., n} ´e movido simultaneamente
por ambas, isto ´e, ∀ a ∈ {1, 2, ..., n}, se σ(a) = a ent˜ao τ(a) = a e vice-versa, se
τ(a) = a ent˜ao σ(a) = a.
Lema 2 Toda permuta¸c˜ao em S
n
´e o produto de ciclos disjuntos.
N˜ao ´e dif´ıcil ver que, se σ, τ ∈ S
n
s˜ao ciclos disjuntos, ent˜ao στ = τσ.
Tamb´em pode-se mostrar que a ordem de um r-ciclo τ ∈ S
n
´e igual a r. Al´em disso,
sendo σ
1
, . . . , σ
k
∈ S
n
ciclos disjuntos de comprimentos r
1
, . . . , r
k
, respectivamente,
ent˜ao o produto σ
1
...σ
k
tem ordem igual a mmc(r
1
, . . . , r
k
).
Temos a seguinte proposi¸c˜ao,
Proposi¸c˜ao 3
(i) Todo elemento de S
n
´e um produto de transposi¸c˜oes, isto ´e, S
n
={transp osi¸c˜oes}.
10
(ii) S
n
=(12), (13), . . . , (1n).
(iii) S
n
=(12), (23), . . . , (n − 1n).
Demonstra¸c˜ao: Vide [Garcia e Lequain (2001)].
Como consequˆencia, temos que as permuta¸c˜oes (12) e (12 . . . n) geram o
grupo sim´etrico S
n
, ou seja, S
n
=(12), (12 . . . n).
2.3 Grupos Sol´uveis
Informalmente, pode-se pensar nos grupos sol´uveis como “aproximadamente
abelianos”. Por exemplo, podemos considerar que um grupo G est´a “perto” de ser
abeliano se ele cont´em um subgrupo normal H tal que tanto H quanto o quociente
G/H s˜ao abelianos (um tal grupo diz-se metabeliano). Generalizaremos esta
id´eia.
Primeiramente, vamos dar algumas defini¸c˜oes.
Defini¸c˜ao 12 Seja G um grupo. Uma s´erie subnormal de G ´e uma cadeia de
subgrup os
G = G
0
✄ G
1
✄ G
2
✄ . . . ✄ G
n
= {e} (2.1)
onde G
i+1
´e um subgrupo normal de G
i
, para i = 0, 1, . . . , n − 1.
Os grupos quocientes da s´erie (2.1) s˜ao grupos G
i
/G
i+1
, para i = 0, 1, . . . , n−
1.
O refinamento da s´erie subnormal (2.1) ´e uma s´erie subnormal obtida a
partir de (2.1) pela inser¸c˜ao de alguns (possivelmente nenhum) subgrupos. O
refinamento ´e pr´oprio se algum subgrupo distinto dos j´a existentes ´e inserido na
s´erie.
A s´erie subnormal (2.1) ´e uma s´erie de composi¸c˜ao se ela n˜ao admite um
refinamento pr´oprio.
11
Defini¸c˜ao 13 Seja G um grupo. O comutador de dois elementos h, k ∈ G ´e
definido como [h, k] := hkh
−1
k
−1
. O comutador de dois subgrupos H, K ≤ G ´e
definido como o subgrupo de G gerado por todos os comutadores [h, k] onde h ∈ H
e k ∈ K, isto ´e,
[H, K] := hkh
−1
k
−1
|h ∈ H, k ∈ K.
Em particular, o grupo de comutadores G
´e igual a [G, G].
Defini¸c˜ao 14 Seja G um grupo. A s´erie de comutadores (s´erie derivada)
G ≥ G
≥ G
≥ G
≥ ... ≥ G
i
≥ ...
de G ´e definida indutivamente por
G
0
:= G, G
i+1
:= [G
i
, G
i
].
Isto ´e, G
i+1
´e o subgrupo dos comutadores do grupo G
i
, para cada i =
0, 1, 2, . . ..
Proposi¸c˜ao 4 Seja G um grupo. As seguintes condi¸c˜oes s˜ao equivalentes:
(i) O grupo G possui uma s´erie subnormal cujos grupos quocientes s˜ao abelianos.
(ii) Existe um inteiro n tal que G
n
= {e}.
No caso de G ser finito, elas s˜ao tamb´em equivalentes a:
(iii) O grupo G possui uma s´erie de composi¸c˜ao cujos grupos quocientes s˜ao
abelianos (e portanto, s˜ao c´ıclicos de ordem prima).
Defini¸c˜ao 15 Um grupo G ´e dito sol´uvel se ele satisfaz as condi¸c˜oes equivalentes
da proposi¸c˜ao 4.
Defini¸c˜ao 16 Uma s´erie de subgrupos de um grupo G
G = G
0
> G
1
> G
2
> . . . > G
r
= {e} (2.2)
12
´e dita uma s´erie normal de G se temos G
i
✁ G, para cada i = 0, 1, . . . , r. Em
particular, uma s´erie normal de G ´e uma s´erie subnormal de G.
Pode-se provar que todo grupo abeliano, todo p-grupo finito e todo grupo
finito de ordem ´ımpar s˜ao sol´uveis. No entanto, se n ≥ 5, ent˜ao o grupo sim´etrico
S
n
n˜ao ´e sol´uvel.
O grupo diedral (defini¸c˜ao 9) ´e sol´uvel, de fato,
Teorema 6 Seja D
n
o grupo diedral de ordem 2n. Ent˜ao D
n
´e sol´uvel.
Demonstra¸c˜ao: Seja C
n
o grupo das rota¸c˜oes do pol´ıgono. Ent˜ao o grupo D
n
possui a seguinte s´erie subnormal com grupos quocientes abelianos
{1} ✁ C
n
✁ D
n
(2.3)
De fato, primeiramente vemos que {1} ✁ C
n
e como |D
n
|/|C
n
| = 2, ou seja, (D
n
:
C
n
) = 2, temos que C
n
✁ D
n
. Al´em disso, C
n
/{1} ´e abeliano e D
n
/C
n
tem ordem
p = 2, portanto ´e abeliano.
Teorema 7 Seja G um grupo.
1) Seja H um subgrupo de G. Se G ´e sol´uvel, ent˜ao H ´e sol´uvel.
2) Seja H um subgrupo normal de G. Ent˜ao, o grupo G ´e sol´uvel se e somente se
os grupos H e G/H s˜ao sol´uveis.
Demonstra¸c˜ao: Vide [Garcia e Lequain (2001)].
N´os dizemos que uma fam´ılia de grupos abelianos ´e suavemente abeliano
se cada grupo na fam´ılia pode ser expressado como produto direto de um subgrupo
cujo expoente (veja Defini¸c˜ao 4) ´e limitado por uma constante e um subgrupo de
tamanho polilogar´ıtmico na ordem do grupo.
13
Uma fam´ılia de grupos sol´uveis ´e suavemente sol´uvel se o comprimento
de cada s´erie derivada ´e limitada por uma constante e a fam´ılia de todos os gru-
pos quocientes G
i
/G
i+1
´e suavemente abeliano. O termo suavemente sol´uvel foi
introduzido por [Friedl et al. (2003)].
14
Cap´ıtulo 3
Teoria dos Grafos
Ser˜ao descritos neste cap´ıtulo alguns conceitos b´asicos da Teoria dos Grafos,
bem como a defini¸c˜ao do Problema do Isomorfismo de Grafos e o Problema do
Automorfismo de Grafos, al´em de algumas rela¸c˜oes entre os dois problemas. A
apresenta¸c˜ao cobre o necess´ario para a compreens˜ao dos problemas e algoritmos
discutidos nos pr´oximos cap´ıtulos. Tamb´em introduziremos aqui a terminologia
e nota¸c˜ao sobre grafos utilizados no restante da disserta¸c˜ao [Szwarcfiter (1984),
Harary (1969)].
3.1 No¸c˜oes B´asicas de Grafos
Acredita-se que a Teoria dos Grafos teve in´ıcio quando o famoso matem´atico
sui¸co Leonhard Euler publicou um artigo sobre o problema das “Sete Pontes de
K
¨
onigsberg”em 1736. Na cidade de K
¨
onigsberg (atualmente Kaliningrado, R´ussia)
havia um conjunto de sete pontes que cruzavam o rio Pregel (ver Figura 3.1). Elas
conectavam duas ilhas entre si e as ilhas com as margens. Durante muito tempo
os habitantes daquela cidade perguntavam-se se era poss´ıvel cruzar as sete pontes
numa caminhada cont´ınua sem passar duas vezes por qualquer uma delas. Euler
mostrou que a travessia proposta n˜ao era poss´ıvel [Euler (1741), Alexanderson
(2006)]. Mas, n˜ao se restringiu a resolver apenas este problema. Sua solu¸c˜ao foi
constru´ıda pensando o problema de forma mais abrangente, inaugurando assim a
Teoria de Grafos. A Figura 3.2 mostra um grafo para o problema.
15
Figura 3.1: As gravuras ilustrando o documento de Euler de 1736 sobre as pontes
de K
¨
onigsberg. Fonte: Alexanderson (2006)
Figura 3.2: Grafo do Problema das Sete Pontes de K
¨
onigsberg.
Um grafo (n˜ao-orientado) Γ ´e uma estrutura (V, E), onde V ´e um conjunto
finito n˜ao-vazio e E ´e uma rela¸c˜ao E ⊆ V ×V do grafo. Os elementos de V s˜ao os
v´ertices e os de E s˜ao as arestas de Γ, respectivamente. Cada aresta e ∈ E ser´a
denotada pelo par de v´ertices e = (v, w) que a forma. Neste caso, os v´ertices v, w
s˜ao os extremos (ou extremidades) da aresta e, sendo denominados adjacentes.
A aresta e ´e dita incidente a ambos v, w. O n´umero de arestas incidentes no
v´ertice v ´e chamado o grau de v. Duas arestas que possuem um extremo comum
16
s˜ao chamadas de arestas adjacentes.
Dizemos que um grafo D = (V, A) ´e um grafo orientado (d´ıgrafo) se V ´e um
conjunto de v´ertices e A um conjunto de pares ordenados de v´ertices, comumente
chamados de arcos ou arestas direcionadas.
Dizemos que Γ
= (V
, E
) ´e um subgrafo do grafo Γ = (V, E) se Γ
´e um
grafo e V
⊆ V , E
⊆ E.
Uma sequˆencia de v´ertices v
1
, . . . , v
k
tal que (v
j
, v
j+1
) ∈ E, 1 ≤ j < k − 1, ´e
denominada um caminho. Um caminho de k v´ertices ´e formado por k −1 arestas
que definem o comprimento do caminho. Se todos os v´ertices em um caminho s˜ao
distintos, o caminho recebe o nome de simples ou elementar.
Um ciclo ´e um caminho v
1
, . . . , v
k
, v
k+1
, onde v
1
= v
k+1
, k ≥ 3. Se o caminho
v
1
, . . . , v
k
for simples o ciclo tamb´em ´e dito simples. O grafo que n˜ao possui ciclos
´e dito ac´ıclico.
Um grafo ´e dito conexo quando existe um caminho ligando cada par de
v´ertices distintos, caso contr´ario o grafo ´e dito desconexo.
Seja S um conjunto e S
⊆ S. Diz-se que S
´e maximal em rela¸c˜ao a uma
certa propriedade P , quando S
satisfaz a propriedade P e n˜ao existe sub conjunto
S
⊃ S
, que tamb´em satisfaz P . Ou seja, S
n˜ao est´a propriamente contido em
nenhum subconjunto de S que satisfa¸ca P.
Denominam-se componentes conexas de um grafo Γ aos subgrafos maxi-
mais de Γ que sejam conexos. A propriedade P , neste caso, ´e equivalente a ser
conexo.
Assumiremos que o conjunto de v´ertices seja dado por V = {1, . . . , n}.
Permuta¸c˜oes dos v´ertices s˜ao ent˜ao dadas por permuta¸c˜oes no grupo sim´etrico
S
n
. Seja π ∈ S
n
uma permuta¸c˜ao, escreveremos πΓ para o grafo que ´e obtido
pela permuta¸c˜ao dos v´ertices de Γ com π, isto ´e, πΓ = π(V, E) = (V, πE) =
(V, {(π(i), π(j))|(i, j) ∈ E}).
Um grafo pode ser visualizado atrav´es de uma representa¸c˜ao geom´etrica,
na qual seus v´ertices correspondem a pontos distintos do plano em posi¸c˜oes arbi-
17
tr´arias, enquanto que a cada aresta (v, w) ´e associada uma linha arbitr´aria unindo
os pontos correspondentes a v, w. Para maior facilidade de exposi¸c˜ao, ´e usual iden-
tificar um grafo com a sua representa¸c˜ao geom´etrica. Isto ´e, no decorrer do texto
ser´a utilizado o termo grafo, significando tamb´em a sua representa¸c˜ao geom´etrica.
3.2 Problema do Isomorfismo de Grafos
A partir do que j´a foi dito ´e poss´ıvel formular o seguinte problema. Dadas
duas representa¸c˜oes geom´etricas, correspondem elas a um mesmo grafo? Em outras
palavras, ´e poss´ıvel fazer coincidir, respectivamente, os pontos de duas represen-
ta¸c˜oes geom´etricas, de modo a preservar adjacˆencia (ou seja, de modo a fazer
tamb´em coincidir as arestas)? Responderemos estas perguntas logo abaixo. Mas
primeiro, definiremos o que ´e isomorfismo de grafos.
Defini¸c˜ao 17 (Isomorfismo de Grafos) Dois grafos (orientados ou n˜ao-orien-
tados) Γ
1
= (V
1
, E
1
), Γ
2
= (V
2
, E
2
) s˜ao chamados isomorfos se existe uma per-
muta¸c˜ao τ tal que τΓ
1
= Γ
2
, ou seja, tal que (τ(u), τ (v)) ∈ E
2
⇔ (u, v) ∈ E
1
.
Neste caso, escrevemos Γ
1
Γ
2
e τ ´e chamado um isomorfismo de grafos entre Γ
1
e Γ
2
. O conjunto de isomorfismos entre um grafo Γ
1
e um grafo Γ
2
´e denotado por
Iso(Γ
1
, Γ
2
).
Exemplo 1 Os grafos Γ
1
= (V
1
, E
1
) e Γ
2
= (V
2
, E
2
), onde E
1
= {(1, 2), (1, 4), (2, 5),
(2, 6), (3, 5), (4, 5)} e E
2
= {(1, 5), (2, 3), (2, 4), (2, 5), (3, 6), (5, 6)} s˜ao isomorfos via
a permuta¸c˜ao τ = (1, 3)(4, 6), ou seja, temos que τ E
1
= E
2
.
Exemplo 2 Podemos obter mais do que um isomorfismo para um par de grafos
isomorfos, como podemos ver na Figura 3.3. Neste caso, n´os temos |Iso(Γ
1
, Γ
2
)| =
4, onde os isomorfismos s˜ao dados pelas permuta¸c˜oes τ
1
= (2, 5), τ
2
= (1, 6)(3, 4),
τ
3
= (1, 4)(3, 6) e τ
4
= (1, 3)(2, 5)(4, 6).
Formalmente, o problema pode ser enunciado da seguinte maneira.
18
Figura 3.3: Par de Grafos com 4 isomorfismos.
Problema 1 (Problema do Isomorfismo de Grafos) Dados dois grafos Γ
1
e
Γ
2
com n v´ertices cada, determinar se eles s˜ao isomorfos.
N˜ao existe atualmente um algoritmo eficiente para resolver este problema no
caso geral. Poder´ıamos tentar todas as permuta¸c˜oes poss´ıveis, mas isso resultaria
em um algoritmo de complexidade O(n!). Para que dois grafos sejam isomorfos,
no m´ınimo as seguintes condi¸c˜oes tˆem que ser respeitadas (condi¸c˜oes necess´arias):
1- Ter o mesmo n´umero de v´ertices.
2- Ter o mesmo n´umero de arestas.
3- Ter o mesmo n´umero de v´ertices de grau n, para qualquer valor n entre 0
e o n´umero de v´ertices que o grafo cont´em.
Note que isso n˜ao ´e suficiente para que sejam isomorfos. Por exemplo, os
grafos da Figura 3.4 respeitam essas condi¸c˜oes e n˜ao s˜ao isomorfos.
Figura 3.4: Par de grafos n˜ao isomorfos.
19
Mais detalhes sobre o Problema do Isomorfismo de Grafos pode ser encon-
trado em [K
¨
obler et al. (1993)].
3.3 Problema do Automorfismo de Grafos
Um caso especial importante de isomorfismos de grafos s˜ao os automorfismos
de grafos.
Defini¸c˜ao 18 (Automorfismo de Grafos) Seja Γ = (V, E) um grafo, onde V =
{1, . . . , n}. Uma permuta¸c˜ao π ∈ S
n
´e um automorfismo de Γ se (π(u), π(v)) ∈ E
sempre que (u, v) ∈ E. O conjunto de automorfismos de um grafo Γ ´e denotado
por Aut(Γ).
Em outras palavras, um automorfismo ´e uma permuta¸c˜ao de v´ertices que
preserva a rela¸c˜ao de adjacˆencia bem como a de n˜ao-adjacˆencia. Claramente, cada
grafo tem a permuta¸c˜ao trivial como um automorfismo. Al´em disso, temos:
Proposi¸c˜ao 5 O conjunto Aut(Γ) ´e um subgrupo do grupo sim´etrico S
n
: Aut(Γ) <
S
n
.
Demonstra¸c˜ao: Claramente Aut(Γ) ⊂ S
n
, uma vez que Aut(Γ) consiste de bi-
je¸c˜oes de um conjunto de n elementos sobre si mesmo. Como S
n
´e finito, basta
mostrarmos que Aut(Γ) ´e fechado com respeito a opera¸c˜ao de composi¸c˜ao em S
n
.
De fato, tomemos φ, ψ ∈ Aut(Γ) e sejam u, v ∈ V (conjunto de v´ertices), ent˜ao
ψ leva a aresta (u, v) para a aresta (ψ(u), ψ(v)), da mesma forma φ leva a aresta
(ψ(u), ψ(v)) para a aresta (φ(ψ(u)), φ(ψ(v))) = (φψ(u), φψ(v)). Portanto, φψ leva
aresta em aresta, ou seja, φψ ∈ Aut(Γ).
Este ´e chamado o grupo de automorfismos do grafo. Um grafo ´e chamado
r´ıgido se a permuta¸c˜ao trivial ´e seu ´unico automorfismo, isto ´e, se seu grupo de
automorfismos ´e o grupo trivial.
Temos ent˜ao o seguinte problema,
20
Problema 2 (Problema do Automorfismo de Grafos) Dado um grafo Γ, o
Problema do Automorfismo de Grafos consiste em encontrar um conjunto de ge-
radores para Aut(Γ).
Dizemos que um problema P
1
´e redut´ıvel polinomialmente a um problema
P
2
, P
1
∝
p
P
2
, se a existˆencia de um algoritmo polinomial para P
2
implica na
existˆencia de um algoritmo polinomial para P
1
. Dois problemas s˜ao equivalentes
polinomialmente se cada um ´e redut´ıvel polinomialmente para o outro.
3.4 Rela¸c˜oes entre Isomorfismos e Automorfismos de Grafos
A partir deste ponto denotaremos o Problema do Isomorfismo de Grafos e o
Problema do Automorfismo de Grafos por PIG e PAG, respectivamente. Seguem
algumas propriedades b´asicas de isomorfismos e automorfismos de grafos e rela¸c˜oes
importantes entre os dois conceitos.
Primeiramente, temos por defini¸c˜ao que, dado um grafo Γ ent˜ao Aut(Γ) =
Iso(Γ, Γ). Segundo, temos o seguinte resultado.
Teorema 8 Sejam Γ
1
e Γ
2
dois grafos isomorfos com o mesmo conjunto de v´er-
tices V = {1, . . . , n}. Ent˜ao, Iso(Γ
1
, Γ
2
) = τ Aut(Γ
1
) =Aut(Γ
2
)τ para cada τ ∈
Iso(Γ
1
, Γ
2
).
Demonstra¸c˜ao: Sejam Γ
1
= (V, E
1
) e Γ
2
= (V, E
2
) dois grafos e sejam φ e ψ
isomorfismos de Γ
1
para Γ
2
, note que eles s˜ao permuta¸c˜oes em S
n
. Da defini¸c˜ao,
temos
(v, w) ∈ E
1
⇔ (φ(v), φ(w)), (ψ(v), ψ(w)) ∈ E
2
.
Por isso, ψ
−1
φ ´e um automorfismo de Γ
1
. Assim, φ e ψ est˜ao na mesma
classe lateral `a esquerda de Aut(Γ
1
). De fato,
ψ ∈ ψAut(Γ
1
) e φ = ψψ
−1
φ ∈ ψψ
−1
φAut(Γ
1
) = ψAut(Γ
1
).
21
Reciprocamente, sejam φ um isomorfismo de Γ
1
para Γ
2
e ρ um automorfismo
de Γ
1
. Ent˜ao φρ ´e novamente um isomorfismo de Γ
1
para Γ
2
. Assim, a classe lateral
`a esquerda φAut(Γ
1
) ´e o conjunto de todos os isomorfismos de Γ
1
para Γ
2
.
Analogamente, mostra-se que Iso(Γ
1
, Γ
2
) =Aut(Γ
2
)φ.
Corol´ario 2 Sejam Γ
1
e Γ
2
grafos isomorfos. Ent˜ao o n´umero de isomorfismos de
Γ
1
para Γ
2
´e igual a ordem de Aut(Γ
1
) e igual a ordem de Aut(Γ
2
).
Corol´ario 3 Sejam Γ
1
e Γ
2
grafos isomorfos. Ent˜ao Aut(Γ
1
) e Aut(Γ
2
) s˜ao con-
jugados em P(V ), onde V ´e o conjunto de v´ertices de Γ
1
e Γ
2
.
Demonstra¸c˜ao: Seja φ ∈ Iso(Γ
1
, Γ
2
), ρ ∈ Aut(Γ
1
), τ ∈ Aut(Γ
2
). Ent˜ao φρφ
−1
∈
Aut(Γ
2
) e φ
−1
τφ ∈ Aut(Γ
1
).
Notemos que a volta do Corol´ario 3 n˜ao ´e verdade. Antes de dar um exemplo,
considere a seguinte defini¸c˜ao.
Defini¸c˜ao 19 Seja Γ = (V, E) um grafo. O grafo complementar Γ de Γ ´e o
grafo (V, E), onde (v, w) ∈ E se (v, w) /∈ E. Podemos tamb´em escrever Γ =
(V, V × V − E).
Exemplo 3 O grafo completo K
n
´e um grafo com v´ertices V = {1, . . . , n} tais
que todos dois v´ertices distintos s˜ao adjacentes. O grafo complementar K
n
de K
n
´e um grafo que tem V = {1, . . . , n} como conjunto de v´ertices e nenhuma aresta.
Claramente, S
n
=Aut(K
n
) =Aut(K
n
), mas K
n
e K
n
n˜ao s˜ao isomorfos para n > 1.
Vamos ilustrar o Teorema 8 e seus corol´arios a seguir:
Exemplo 4 Sejam Γ
1
= (V, E
1
) e Γ
2
= (V, E
2
), onde V = {1, . . . , 5}, E
1
=
{(1, 2), (1, 4), (2, 3), (3, 4), (3, 5)} e E
2
= {(1, 4), (1, 5), (2, 3), (3, 4), (3, 5)}. Os grafos
Γ
1
e Γ
2
s˜ao isomorfos (ver Figura 3.5). Existem dois isomorfismos de Γ
1
para Γ
2
,
a saber, π
1
= (2, 4, 5) e π
2
= (2, 5). Portanto, Iso(Γ
1
, Γ
2
) = {(2, 4, 5), (2, 5)}. Al´em
disso, verifica-se que Aut(Γ
1
) = {( ), (2, 4)} e Aut(Γ
2
) = {( ), (4, 5)}.
22
Tomando π
1
= (2, 4, 5), temos
π
1
Aut(Γ
1
) = {(2, 4, 5), (2, 4, 5)(2, 4)} = {(2, 4, 5), (2, 5)}
Aut(Γ
2
)π
1
= {(2, 4, 5), (4, 5)(2, 4, 5)} = {(2, 4, 5), (2, 5)}
Analogamente, tomando π
2
= (2, 5), temos
π
2
Aut(Γ
1
) = {(2, 5), (2, 5)(2, 4)} = {(2, 5), (2, 4, 5)}
Aut(Γ
2
)π
2
= {(2, 5), (4, 5)(2, 5)} = {(2, 5), (2, 4, 5)}
Portanto, Iso(Γ
1
, Γ
2
) = πAut(Γ
1
) =Aut(Γ
2
)π para cada π ∈ Iso(Γ
1
, Γ
2
).
Note ainda que, (4, 5) = (2, 5)
−1
(2, 4)(2, 5), ou seja, (4, 5) e (2, 4) pertencem
a mesma classe de conjuga¸c˜ao. Portanto, Aut(Γ
2
) = (2, 5)Aut(Γ
1
).
Figura 3.5: Grafos isomorfos para ilustrar o Teorema 8 e seus corol´arios.
Agora, daremos uma rela¸c˜ao ainda mais importante entre os dois problemas.
Um algoritmo eficiente para resolver o PIG implica num algoritmo eficiente para
resolver o PAG.
Teorema 9 O Problema do Automorfismos de Grafos ´e redut´ıvel polinomialmente
para o Problema do Isomorfismos de Grafos, PAG ∝
p
PIG.
Demonstra¸c˜ao: Vide [Mathon (1979)].
23
Para cada permuta¸c˜ao π ∈ S
n
temos que πΓ = πΓ. De fato, πΓ = π(V, V ×
V − E) = (V, V × V − πE). Por outro lado, temos que πΓ = (V, πE) = (V, V ×
V −πE). Uma consequˆencia imediata disto ´e que se π ´e um isomorfismo entre Γ
1
e
Γ
2
, ent˜ao π ´e tamb´em um isomorfismo entre Γ
1
e Γ
2
: πΓ
1
= πΓ
1
= Γ
2
. Em outras
palavras,
Iso(Γ
1
, Γ
2
) = Iso(Γ
1
, Γ
2
) (3.1)
Se o grafo Γ n˜ao ´e conexo, ent˜ao seu grafo complementar Γ o ser´a. Por-
tanto, sempre que considerarmos isomorfismos entre grafos, podemos assumir que
no m´ınimo um dos grafos ´e conexo. Al´em disso, se um dos grafos ´e conexo e o
outro n˜ao ´e, ent˜ao sabemos que eles n˜ao s˜ao isomorfos. Logo, podemos sempre
assumir que ambos os grafos s˜ao conexos.
Outra imp ortante “transforma¸c˜ao de grafos” ´e a uni˜ao disjunta de grafos
dada pela seguinte defini¸c˜ao,
Defini¸c˜ao 20 Dados dois grafos Γ
1
= (V
1
, E
1
) e Γ
2
= (V
2
, E
2
) com conjuntos
disjuntos de v´ertices V
1
e V
2
(e portanto, conjuntos disjuntos de arestas), sua
uni˜ao disjunta ´e dada por Γ
1
∪ Γ
2
= (V
1
∪ V
2
, E
1
∪ E
2
), ou seja, ´e o grafo obtido
pela uni˜ao dos conjuntos de v´ertices e uni˜ao dos conjuntos de arestas dos grafos.
Exemplo 5 O grupo de automorfismos do ciclo de comprimento n ´e o grupo
Diedral D
n
de ordem 2n. Al´em disso, o grupo de automorfismos do ciclo orientado
de comprimento n ´e o grupo c´ıclico Z
n
de ordem n.
No entanto, um caminho de comprimento ≥ 1 tem apenas 2 automorfismos.
24
Cap´ıtulo 4
Descri¸c˜ao Matem´atica do Problema do
Isomorfismo de Grafos
4.1 Isomorfismos de Grafos e Interse¸c˜ao de Grupos
Neste cap´ıtulo, mostraremos que o Problema do Isomorfismo de Grafos pode
ser reduzido para o problema de encontrar o conjunto de geradores para a interse¸c˜ao
de dois grupos de permuta¸c˜oes, ou seja, um algoritmo de tempo polinomial para
o problema de interse¸c˜ao de grupos de permuta¸c˜oes implica na existˆencia de um
algoritmo de tempo polinomial para o problema do isomorfismo de grafos [Hoffman
(1979)]. Para isso, mostraremos que o grupo de automorfismos de todo grafo ´e
isomorfo a interse¸c˜ao de dois grupos de permuta¸c˜oes para os quais os conjuntos
geradores s˜ao conhecidos.
Definimos ent˜ao o Problema de Interse¸c˜ao de Grupos para grupos de permu-
ta¸c˜oes:
Problema 3 (Problema de Interse¸c˜ao de Grupos) Dados conjuntos de ger-
adores para dois grupos de permuta¸c˜oes A < S
n
e B < S
n
para algum n, determinar
um conjunto gerador para C = A ∩ B.
N˜ao existe algoritmo cl´assico eficiente para tal problema.
Para todo grup o G, existe um grafo cujo grupo de automorfismos ´e isomorfo
a G [Frucht (1939)]. O grupo de automorfismos de um grafo caracteriza suas
simetrias, e al´em disso, ´e muito usado na determina¸c˜ao de certas propriedades.
25
Teorema 10 Todo grupo ´e um grupo de automorfismos de algum grafo. Al´em
disso, se o grupo ´e finito, ent˜ao o grafo pode ser tomado como finito.
Demonstra¸c˜ao: Vide [Frucht (1939)].
Subsequentemente, [Frucht (1949)] mostrou que todo grupo ´e o grupo de
automorfismo de um grafo de grau 3, e isto tem inspirado um grande n´umero de
resultados similares.
Seja Γ = (V, E) um grafo com conjunto de v´ertices V = {1, . . . , n}. Cons-
truiremos uma nova representa¸c˜ao para S
n
fazendo o grupo atuar no conjunto de
todos os pares n˜ao-ordenados (i, j), 1 ≤ i, j ≤ n, i = j, ou seja, o conjunto de
arestas e n˜ao-arestas, E ∪ E. Repare que |E ∪ E| =
n(n−1)
2
. A nova representa¸c˜ao
´e obtida atrav´es da asso cia¸c˜ao de π em S
n
com uma permuta¸c˜ao ψ ∈ S
n(n−1)/2
agindo sobre os pares n˜ao-ordenados (i, j) da seguinte maneira:
ψ(i, j) = (π(i), π(j)). (4.1)
Vamos denotar por S
n
essa nova representa¸c˜ao para S
n
. Ent˜ao, temos que
S
n
atua no conjunto {1, . . . , n} enquanto S
n
atua no conjunto E ∪E = {(i, j), 1 ≤
i, j ≤ n, i = j}. Podemos dizer ainda que {1, . . . , n} s˜ao os pontos de S
n
e que os
elementos de E ∪ E s˜ao os pontos de S
n
. Temos ent˜ao o seguinte resultado,
Proposi¸c˜ao 6 Seja S
n
definido como acima e seja a fun¸c˜ao
φ : S
n
→ S
n
π → ψ
π
tal que ψ
π
(i, j) = (π(i), π(j)), onde 1 ≤ i, j ≤ n, i = j. Ent˜ao a fun¸c˜ao φ ´e um
isomorfismo.
26
Demonstra¸c˜ao: Sejam π, τ ∈ S
n
. Ent˜ao,
φ(πτ)(i, j) = ψ
πτ
(i, j) = (πτ (i), πτ(j))
= (π(τ (i)), π(τ(j))) = ψ
π
(τ(i), τ (j))
= ψ
π
(ψ
τ
(i, j)) = ψ
π
ψ
τ
(i, j)
= φ(π)φ(τ )(i, j)
Portanto φ ´e um homomorfismo. Al´em disso, por defini¸c˜ao, temos que φ ´e
uma bije¸c˜ao.
Note que S
n
pode ser gerado por duas permuta¸c˜oes, por exemplo por π
1
=
(1, 2) e π
2
= (1, . . . , n) (consequˆencia da Proposi¸c˜ao 3). Portanto, S
n
tamb´em
pode ser gerado por duas permuta¸c˜oes, a saber, ψ
π
1
e ψ
π
2
. Seja E o conjunto de
n˜ao-arestas de Γ. Seja T = P(E) ×P(E), o produto direto de P(E) e P(E). Pelo
que acabamos de ver, sabemos que T ´e gerado por quatro permuta¸c˜oes que n´os
conhecemos. Ent˜ao, afirmamos o seguinte:
Teorema 11 Seja Γ = (V, E) um grafo com conjunto de v´ertices V = {1, . . . , n}.
Ent˜ao, Aut(Γ) S
n
∩ T .
Demonstra¸c˜ao: Seja A =Aut(Γ) < S
n
, o grupo de automorfismos de Γ. Seja
A
o conjunto de elementos em S
n
correspondentes aos elementos de A, obtidos
atrav´es do isomorfismo φ : S
n
→ S
n
(ver proposi¸c˜ao 6), de modo que tenhamos
A A
. Mostraremos ent˜ao que A
= S
n
∩ T .
Seja π ∈ A um automorfismo de Γ e seja ψ
π
o elemento correspondente em
A
. Ent˜ao, ψ
π
´e um elemento de S
n
. Al´em disso, como π leva arestas em arestas e
n˜ao-arestas em n˜ao-arestas, ψ
π
est´a tamb´em em T pela defini¸c˜ao de tal conjunto.
Reciprocamente, seja ψ
π
em S
n
∩ T . Uma vez que ψ
π
∈ S
n
, existe uma
permuta¸c˜ao de v´ertices associada π em S
n
, al´em disso, como ψ
π
∈ T , a permuta¸c˜ao
de v´ertices π correspondente leva arestas em arestas e n˜ao-arestas para n˜ao-arestas,
logo π ´e um automorfismo, ou seja, π ∈ A =Aut(Γ), da´ı ψ
π
∈ A
.
27
Portanto, A
= S
n
∩T . Mas, como A A
, temos que A S
n
∩T , conforme
quer´ıamos demonstrar.
Notemos que a interse¸c˜ao acima faz sentido porque T ´e isomorfo a um sub-
grupo de S
n(n−1)/2
.
Corol´ario 4 Se o problema de interse¸c˜ao de grupos est´a em P (ver se¸c˜ao 4.3),
ent˜ao segue que o problema de isomorfismo de grafos tamb´em est´a em P.
´
E uma quest˜ao em aberto se a volta do Corol´ario 4 ´e verdadeira.
Vamos ilustrar o Teorema 11 com um exemplo.
Exemplo 6 Seja Γ = (V, E) um grafo tal que V = {1, 2, 3, 4} e E = {(1, 2), (1, 3),
(2, 3), (3, 4)}. Na Figura 4.1 temos uma representa¸c˜ao para tal grafo.
Figura 4.1: grafo Γ = (V, E)
Primeiramente, vemos que E = {(1, 4), (2, 4)}, logo, temos que E ∪ E =
{(1, 2), (1, 3), (2, 3), (3, 4), (1, 4), (2, 4)}.
´
E f´acil ver, neste caso, que Aut(Γ) =
{( ), (1, 2)}, por´em vamos achar esse resultado atrav´es do Teorema 11.
Vamos reescrever o conjunto E de tal forma que 1 represente a aresta (1, 2),
2 represente a aresta (1, 3), 3 represente a aresta (2, 3) e 4 represente a aresta
(3, 4). Da mesma forma vamos representar a n˜ao-aresta (1, 4) por 5 e a n˜ao-aresta
(2, 4) por 6, portanto o conjunto E ∪ E ser´a dado nessa nova representa¸c˜ao por
E ∪ E = {1, 2, 3, 4, 5, 6}.
28
Logo, usando essa nova representa¸c˜ao temos tamb´em os seguintes conjuntos
P(E) = {( ), (5, 6)}
P(E) = {( ), (1, 2), (1, 3), (1, 4), . . .} = S
4
Definimos agora o conjunto T = P(E) × P(E) = {(π, τ); π ∈ P(E), τ ∈
P(E)}, produto direto de P(E) e P(E).
Obtemos tamb´em o grupo S
4
a partir de S
4
, pelo isomorfismo (conforme
Proposi¸c˜ao 6) definido por ψ
π
(i, j) = (π(i), π(j)), onde π ∈ S
4
, ψ
π
∈ S
4
, 1 ≤ i, j ≤
4, i = j. Por exemplo, se π = (1, 2) ent˜ao ψ
π
= (2, 3)(5, 6). Note que ψ
π
∈ T . Por
outro lado, se π = (3, 4) ent˜ao ψ
π
= (2, 5)(3, 6). Note que nesse caso ψ
π
/∈ T .
Repare que S
4
< S
6
e T ´e isomorfo a um subgrupo de S
6
. Portanto podemos
fazer a interse¸c˜ao de tais grupos, que neste caso ser´a igual a:
A
= S
4
∩ T = {( ), (2, 3)(5, 6)}.
Portanto, pelo Teorema 11, temos que A
A =Aut(Γ). Usando o isomor-
fismo citado acima e sabendo que A
= {( ), (2, 3)(5, 6)}, temos que a permuta¸c˜ao
(2, 3)(5, 6) em A
= S
4
∩ T equivale a permuta¸c˜ao (1, 2) em A =Aut(Γ), portanto
A =Aut(Γ) = {( ), (1, 2)}, confirmando o que j´a sab´ıamos.
4.2 Grafos com grupo de automorfismos sol´uvel
Dado um grafo Γ com n v´ertices, vimos pela Prop osi¸c˜ao 5 que seu grupo de
automorfismos Aut(Γ) ´e subgrupo do grupo sim´etrico S
n
. Al´em disso, pelo Teo-
rema 11, vimos que Aut(Γ) S
n
∩T , onde S
n
e T foram definidos anteriormente.
Seja a classe de grafos A
n
= (V
A
n
, E
A
n
), onde V
A
n
= {a
i
, b
i
, c
i
: 0 ≤ i < n}
e E
A
n
= {(a
i
, a
i+1
), (a
i
, b
i
), (a
i
, c
i
), (b
i
, c
i
), (c
i
, a
i+1
) : 0 ≤ i < n}, onde todos os
´ındices s˜ao lidos m´odulo n, isto ´e, A
n
´e composto de um n-ciclo (a
0
, . . . , a
n−1
) com
um retˆangulo desenhado sobre cada lado mais uma diagonal em cada retˆangulo.
Veja a Figura 4.2.
29
´
E f´acil ver que |V
A
n
| = 3n. Podemos tamb´em verificar que, Aut(A
n
) = C
n
[Harary (1969)], onde C
n
´e o grupo c´ıclico de ordem n. Rota¸c˜oes por 2π/n geram
um subgrupo isomorfo a C
n
, o grupo c´ıclico de ordem n. Portanto, temos que
Aut(A
n
) < S
3n
.
Vejamos um exemplo,
Exemplo 7 Seja o grafo A
3
= (V
A
3
, E
A
3
), onde V
A
3
= {a
i
, b
i
, c
i
: 0 ≤ i < 3} e
E
A
3
= {(a
i
, a
i+1
), (a
i
, b
i
), (a
i
, c
i
), (b
i
, c
i
), (c
i
, a
i+1
) : 0 ≤ i < 3}, descrito na Figura
4.2. Este ´e o menor grafo cujo grupo de automorfismos ´e o C
3
[Harary e Palmer
(1966/1972)].
c
2
b
2
a
2
c
1
b
1
c
0
a
1
b
0
a
0
A
3
Figura 4.2: Exemplo de um grafo da classe A
n
, com n = 3.
Renomeando os elementos do conjunto V
A
3
, chamando a
0
de 1, a
1
de 2 at´e c
2
de 9, ent˜ao teremos V
A
3
= {1, 2, . . . , 9} e portanto, E
A
3
= {(1, 2), (2, 3), (1, 3), (1, 4),
(2, 5), (3, 6), (1, 7), (2, 8), (3, 9), (4, 7), (5, 8), (6, 9), (2, 7), (3, 8), (1, 9)}. Temos ent˜ao
que, E
A
3
= E(K
9
) − E
A
3
(onde K
9
´e o grafo completo, definido no exemplo 3).
Definiremos agora o conjunto T como sendo o produto direto de P(E
A
3
) com
P(E
A
3
), ou seja, T = P(E
A
3
) × P(E
A
3
). Como |E(K
9
)| = 36, temos que |E
A
3
| =
21, a saber, E
A
3
= {(1, 5), (1, 6), (1, 8), (2, 4), (2, 6), (2, 9), (3, 4), (3, 5), (3, 7), (4, 5),
(4, 6), (4, 8), (4, 9), (5, 6), (5, 7), (5, 9), (6, 7), (6, 8), (7, 8), (7, 9), (8, 9)}.
Por outro lado, construiremos tamb´em o conjunto S
9
a partir de S
9
, usando
30
o seguinte homomorfismo, conforme Proposi¸c˜ao 6.
ψ
π
(i, j) = (π(i), π(j)), π ∈ S
9
, 1 ≤ i, j ≤ 9, i = j.
Logo,
S
9
= {ψ
π
; ψ
π
(i, j) = (π(i), π(j)), π ∈ S
9
, 1 ≤ i, j ≤ 9, i = j} < S
36
Assim, pelo teorema 11 temos que Aut(A
3
) S
9
∩T . Por outro lado, temos
que Aut(A
3
) = C
3
(o grupo c´ıclico C
3
). Mas, C
3
✁ D
3
.
Em geral, temos que o grupo de automorfismos Aut(A
n
) = C
n
✁ D
n
. Al´em
disso, vimos no Teorema 6 que o grupo D
n
´e sol´uvel.
4.3 Problemas de Reconhecimento de Linguagens e Classes de
Complexidade
Nesta se¸c˜ao vamos fazer uma breve revis˜ao das classes de complexidade cl´as-
sica e quˆantica.
A fim de computar, precisamos de uma maneira razo´avel para representar
informa¸c˜ao. Codifica¸c˜ao un´aria (ou seja, que representam o n´umero j por uma se-
q
¨
uˆencia de 1s de comprimento j) ´e exponencialmente menos eficaz do que usar se-
q
¨
uˆencias de s´ımbolos a partir de qualquer alfabeto fixado de tamanho, pelo menos,
2. Passar de um alfabeto de tamanho 2 para um alfabeto maior de tamanho fixo
s´o muda o tamanho da representa¸c˜ao do problema por um fator constante. Ent˜ao,
vamos simplesmente utilizar o alfabeto Σ = {0, 1}. O conjunto Σ
∗
denota todas as
seq
¨
uˆencias (strings) de comprimento finito sobre este alfabeto. Uma linguagem L ´e
um subconjunto de Σ
∗
. Em particular, usualmente L ´e um conjunto de seq
¨
uˆencias
com alguma propriedade de interesse.
Um algoritmo ‘resolve o problema de reconhecimento de linguagem para L’
se ele aceita toda seq
¨
uˆencia x ∈ L e rejeita toda seq
¨
uˆencia x /∈ L.
Por exemplo, o problema de decidir se um inteiro n (representado como uma
31
seq
¨
uˆencia de bits) ´e primo ´e refeito como o problema de reconhecer se a seq
¨
uˆencia
representando n est´a na linguagem PRIME = {10, 11, 010, 011, 101, 111, . . .} (que
consiste no conjunto de todas as seq
¨
uˆencias que representam n´umeros primos, de
acordo com alguma codifica¸c˜ao razo´avel, o que neste caso ´e a codifica¸c˜ao bin´aria
‘padr˜ao’).
Agora que mostramos como expressar problemas de decis˜ao em termos de re-
conhecer os elementos de uma linguagem, podemos definir diferentes classes de lin-
guagens. Por exemplo, definimos formalmente P (‘tempo polinomial’) como sendo
a classe de linguagens L para as quais existe um algoritmo cl´assico determin´ıstico A
executando no pior caso em tempo polinomial, isto ´e, existe um polinˆomio p(n) tal
que A executa por tempo no m´aximo p(n) instru¸c˜oes elementares sobre entradas
de comprimento n de tal forma que, para uma eventual entrada x ∈ Σ
∗
o algoritmo
A sobre a entrada x, produz ‘aceitar’ se e somente se x ∈ L. Note que nesta classe
n˜ao ´e poss´ıvel capturar as vantagens da utiliza¸c˜ao da aleatoriedade para resolver
problemas.
A classe BPP (‘tempo polinomial probabil´ıstico com erro limitado’) ´e com-
posta por todas as linguagens L para as quais existem um algoritmo cl´assico
randˆomico A executando com pior caso tempo polinomial tal que, para qualquer
entrada x ∈ Σ
∗
temos
• Se x ∈ L ent˜ao a probabilidade de A aceitar x ´e no m´ınimo
2
3
• Se x /∈ L ent˜ao a probabilidade de A aceitar x ´e no m´aximo
1
3
.
´
E importante notar que quando nos referimos ao ‘a probabilidade de A
aceitar’, estamos nos referindo `a probabilidade sobre escolhas aleat´orias de ca-
minhos da computa¸c˜ao sobre a entrada fixada x ∈ L.
´
E tamb´em importante notar
que n˜ao h´a nada de especial a respeito da constante
2
3
. Qualquer constante
1
2
+ δ
funcionar´a [Papadimitriou (1994), Kaye et al. (2007)].
A classe BQP (‘tempo polinomial quˆantico com erro limitado’) ´e composta
por todas as linguagens L para as quais existe um algoritmo quˆantico A executando
com pior caso tempo polinomial tal que, para qualquer entrada x ∈ Σ
∗
temos
32
• Se x ∈ L ent˜ao a probabilidade de A aceitar x ´e no m´ınimo
2
3
• Se x /∈ L ent˜ao a probabilidade de A aceitar x ´e no m´aximo
1
3
.
Tratamos algoritmos com complexidade polinomial como ‘eficientes’ e pro-
blemas que podem ser resolvidos com complexidade polinomial como ‘trat´aveis’, e
problemas sem solu¸c˜ao polinomial como ‘intrat´aveis’.
A classe NP (‘tempo polinomial n˜ao-determin´ıstico’) consiste de todas as
linguagens L para as quais existe um algoritmo cl´assico de tempo polinomial A(a, b)
tal que para qualquer entrada x ∈ Σ
∗
temos
• Se x ∈ L ent˜ao existe uma entrada y tal que A(x, y) produz ‘aceitar’
• Se x /∈ L ent˜ao A(x, y) produz ‘rejeitar’ para todo y
e o comprimento de y ´e limitado por um polinˆomio no comprimento de x.
O problema de decis˜ao da fatora¸c˜ao de inteiros ´e um exemplo de problema da
classe NP. Tal problema consiste no seguinte, dado um n´umero inteiro composto
m, e l < m, teria m algum fator n˜ao-trivial menor do que l? O que caracteriza
os problemas NP ´e o fato de que os casos “sim” (aceitar) de um problema podem
facilmente ser verificados uma vez que se tenha uma evidˆencia apropriada. Existe
uma assimetria interessante na defini¸c˜ao de NP. Embora devamos ser capazes de
testar rapidamente se uma poss´ıvel evidˆencia para x ∈ L ´e de fato uma evidˆencia,
tal necessidade n˜ao existe para x /∈ L. Por exemplo, no caso do problema da
fatora¸c˜ao existe uma maneira simples de demonstrarmos se um dado n´umero possui
um fator menor do que m, mas apresentar uma prova para mostrar que um n´umero
n˜ao possui fatores menores do que m ´e mais dif´ıcil.
Os problemas da classe NP considerados mais dif´ıceis formam uma sub-
classe chamada ‘NP-Completa’. Qualquer problema dessa classe ´e t˜ao dif´ıcil
quanto qualquer outro problema da classe NP, em outras palavras, um algoritmo
que resolva um problema da classe NP-Completa pode ser adaptado para resolver
qualquer outro problema da classe NP, com pequeno custo [Papadimitriou (1994)].
33
Os problemas de fatora¸c˜ao de inteiros e isomorfismo de grafos est˜ao na classe NP,
mas n˜ao acredita-se que estejam na classe NP-Completa.
A classe PESPA ¸CO consiste em todas as linguagens L para as quais exis-
te um algoritmo cl´assico A usando no pior caso espa¸co polinomial tal que para
qualquer entrada x ∈ Σ
∗
o algoritmo A aceita x se e somente se x ∈ L. Ou seja, os
problemas em PESPA¸CO podem ser resolvidos em uma m´aquina de Turing com
n´umero polinomial de bits, sem limite de tempo.
NP
P
BPP
BQP
PESPAÇO
Figura 4.3: Este diagrama ilustra as conhecidas rela¸c˜oes entre algumas das mais
importantes classes de complexidades. Atualmente, nenhuma das inclus˜oes s˜ao
sabidas serem estritas. Por exemplo, atualmente n˜ao existe qualquer prova de que
P = PESPA¸CO.
A figura 4.3 (adaptada de [Kaye et al. (2007)], p´agina 185) ilustra as rela¸c˜oes
conhecidas entre as classes de complexidade que acabamos de definir. Por exemplo,
claramente P ⊆ BPP ⊆ BQP ⊆ PESPA¸CO e P ⊆ NP ⊆ PESPA ¸CO. Infe-
lizmente, embora se acredite que cada uma dessas inclus˜oes seja estrita, nenhuma
jamais foi demonstrada. Mas acredita-se que P=NP e que NP=PESPA ¸CO.
Esperamos tamb´em que BPP=BQP.
Sabemos que P ´e subconjunto de NP, pois a capacidade de se resolver um
problema implica a verifica¸c˜ao de suas solu¸c˜oes, no entanto, n˜ao se sabe se existem
problemas de NP que n˜ao pertencem a P. O problema em aberto mais famoso em
ciˆencia da computa¸c˜ao ´e determinar se existem ou n˜ao problemas em NP que n˜ao
34
perten¸cam a P, abreviado como “problema P=NP”. A maioria dos cientistas da
computa¸c˜ao acredita que P=NP, no entanto, ap´os d´ecadas de trabalho ningu´em
demonstrou tal fato, e a possibilidade P=NP permanece.
O problema do isomorfismo de grafos ocupa uma importante posi¸c˜ao no
mundo da an´alise de complexidade. Ele ´e um dos problemas que est´a na classe NP
mas n˜ao se sabe se est´a nas classes P ou NP-Completa. Supondo P=NP, ´e pos-
s´ıvel provar que existe uma classe n˜ao-vazia de problemas NPI (NP intermedi´aria)
que n˜ao s˜ao solucion´aveis com recursos polinomiais, nem NP-Completos.
´
E
claro que n˜ao se conhece nenhum problema de NPI, pois, caso contr´ario, ter´ıamos
P=NP, mas existem problemas considerados candidatos. Uma das hip´oteses mais
aceitas ´e que o problema do isomorfismo de grafos perten¸ca a tal classe de proble-
mas.
O maior desafio da ´area de algoritmos quˆanticos ´e encontrar problemas que
est˜ao em BQP mas n˜ao em BPP, isto ´e, encontrar problemas que sejam resolvi-
dos de forma eficiente em um computador quˆantico, mas n˜ao em um computador
cl´assico. O estudo dessas classes de complexidade e as rela¸c˜oes entre elas pode ser
´util para compreender a dificuldade destes problemas.
4.4 Algoritmos Cl´assicos
N˜ao ´e conhecido na literatura um algoritmo cl´assico eficiente para o problema
do isomorfismo de grafos para o caso geral. O melhor algoritmo conhecido para tal
problema “roda” em tempo e
O(
√
n log n)
[Babai (1980), Babai e Luks (1983), Zemly-
achenko et al. (1985)]. Dizemos que tal algoritmo ´e subexponencial no n´umero
de v´ertices dos grafos de entrada. No entanto, devido a grande dificuldade de
se tratar o caso geral do problema e da necessidade de algoritmos que resolvam
o problema para grafos em situa¸c˜oes pr´aticas, pesquisadores tˆem adotado outros
caminhos para resolver o problema.
Uma das estrat´egias adotadas foi desenvolver algoritmos heur´ısticos que re-
solvam o problema de forma satisfat´oria. Este ´e o caso do algoritmo desenvolvido
35
por Mckay, que encontra geradores para o grupo de automorfismos do grafo [McKay
(1981), McKay (1990)]. Tal algoritmo utiliza informa¸c˜oes `a respeito da vizinhan¸ca
imediata de cada v´ertice e realiza assim um refinamento, classificando seus v´er-
tices, que juntamente com t´ecnicas da teoria de grup os reduz o n´umero de pos-
s´ıveis solu¸c˜oes a serem analisadas. Este algoritmo ´e considerado mais poderoso do
que qualquer outro algoritmo publicado para a solu¸c˜ao pr´atica do caso geral do
problema de isomorfismo de grafos. No entanto, possui pior caso exponencial.
Uma outra estrat´egia usada consiste em tentar desenvolver algoritmos poli-
nomiais para classes restritas de grafos.
4.4.1 Algoritmos Cl´assicos para certas classes de grafos
Existem algoritmos cl´assicos polinomiais para determinadas classes de grafos
[Fortin (1996)]. Temos ent˜ao uma vers˜ao restrita do Problema de Isomorfismo de
Grafos, onde os grafos de entrada pertencem a uma classe C ⊆ G, onde G denota
todos os grafos conexos e n˜ao-orientados.
O primeiro grande resultado neste campo foi um artigo de Luks para a classe
de grafos que tem grau limitado por uma constante (isto ´e, grau m´aximo ≤ alguma
constante k) [Luks (1982)]. Ele mostrou que para tais grafos existe um algoritmo
em tempo polinomial para checar isomorfismos. O algoritmo apresentado no artigo
tem complexidade O(n
ck log k
), onde c > 1 ´e uma constante e k ´e o grau m´aximo.
No entanto, mesmo o grau m´aximo sendo apenas 10, esta t´ecnica n˜ao produz um
algoritmo pr´atico.
Foi mostrado por [Hopcroft e Wong (1974)] que grafos planares poderiam ser
checados por isomorfismos em tempo linear, embora o seu algoritmo possua uma
grande constante, o que tamb´em o torna impr´oprio na pr´atica. Outra grande classe
de grafos sobre os quais isomorfismo de grafos pode ser eficientemente resolvido
s˜ao os grafos arco-circulares. [Hsu (1995)] mostrou que existe um algoritmo O(mn)
para testar isomorfismos destes grafos, onde m ´e o n´umero de arestas, e n ´e o
n´umero de v´ertices. Este resultado ´e interessante na medida em que n˜ao exige
36
alguns parˆametros expl´ıcitos para ser constante, e parece aplicar-se a um grande
grupo de grafos pr´aticos.
Existem diversas outras classes de grafos restritas para as quais isomorfis-
mos de grafos podem ser resolvidos em tempo polinomial. Por exemplo, [Cogis
e Guinaldo (1995)] mostraram que isomorfismo de grafos conceituais pode ser re-
solvido em tempo polinomial. Isto ´e de particular interesse para a comunidade de
inteligˆencia artificial. Outras classes de grafos como as ´arvores [Aho et al. (1974)],
grafos de permuta¸c˜ao [Colbourn (1981)], grafos intervalo [Lueker e Booth (1979)],
grafos de intervalo pr´oprio [de Figueiredo et al. (1995)], partial k-trees [Bodlaender
(1990)] tˆem problemas de isomorfismo que est˜ao em P.
37
Cap´ıtulo 5
Computa¸c˜ao Quˆantica
A Computa¸c˜ao Quˆantica (CQ) ´e uma ´area de pesquisa recente que utiliza
elementos de trˆes ´areas importantes: Matem´atica, F´ısica e Computa¸c˜ao. O obje-
tivo da CQ ´e estudar m´etodos para processar, transmitir e armazenar informa¸c˜oes
contidas em estados quˆanticos. Os seguintes questionamentos nos motivam a estu-
dar CQ: Existem problemas que os computadores quˆanticos podem resolver mais
rapidamente do que os cl´assicos? O que faz os computadores quˆanticos serem mais
eficientes do que os cl´assicos?
5.1 Mecˆanica Quˆantica
Nesta se¸c˜ao apresentaremos uma breve revis˜ao de Mecˆanica Quˆantica uti-
lizando a nota¸c˜ao adotada para o estudo da Computa¸c˜ao Quˆantica [Nielsen e
Chuang (2000), Kaye et al. (2007), Lomont (2004)].
Defini¸c˜ao 21 (Q-bit) Um q-bit (bit quˆantico) ´e um vetor unit´ario em C
2
.
Defini¸c˜ao 22 (Estado) O estado de um sistema quˆantico ´e um vetor (coluna)
em algum espa¸co vetorial, escrevemos |ψ.
Estados quˆanticos com n > 1 q-bits s˜ao freq
¨
uentemente chamados de regis-
tradores quˆanticos.
Na computa¸c˜ao cl´assica temos o bit como conceito fundamental. Analoga-
mente, na computa¸c˜ao quˆantica temos como conceito fundamental o bit quˆantico
38
ou q-bit, abreviadamente. Um bit pode assumir somente os valores 0 ou 1. Na
computa¸c˜ao quˆantica, os valores 0 e 1 s˜ao substitu´ıdos pelos vetores |0 e |1. Esta
nota¸c˜ao para vetores ´e chamada nota¸c˜ao de Dirac e ´e padr˜ao na Mecˆanica Quˆan-
tica. A diferen¸ca entre bits e q-bits ´e que um q-bit |ψ pode tamb´em estar em uma
combina¸c˜ao linear dos vetores |0 e |1,
|ψ = α |0 + β |1, (5.1)
onde α e β s˜ao n´umeros complexos. Dizemos que |ψ ´e uma superposi¸c˜ao dos
estados |0 e |1 com amplitudes α e β, que satisfazem a |α|
2
+ |β|
2
= 1. A
interpreta¸c˜ao f´ısica de |ψ ´e a co-existˆencia do q-bit nestes dois estados. Assim,
|ψ ´e um vetor em um espa¸co vetorial complexo de dimens˜ao 2, onde {|0, |1}
forma uma base ortonormal, chamada base computacional. O estado |0 n˜ao ´e o
vetor zero, mas simplesmente o primeiro vetor da base. As matrizes representando
os vetores |0 e |1 s˜ao dadas por
|0 =
1
0
e |1 =
0
1
.
O estado |ψ pode guardar uma enorme quantidade de informa¸c˜ao em seus
coeficientes α e β, mas essa informa¸c˜ao mora num n´ıvel quˆantico. Para trazer
essa informa¸c˜ao quˆantica para o n´ıvel cl´assico devemos medir (ver Apˆendice A) o
q-bit. A Mecˆanica Quˆantica nos diz que o processo de medida causa um dist´urbio
no estado quˆantico, projetando o estado |ψ nos subespa¸cos gerados por |0 e |1,
produzindo o estado |0 com probabilidade |α|
2
e o estado |1 com probabilidade
|β|
2
.
As leis da Mecˆanica Quˆantica determinam que se o computador estiver iso-
lado, a dire¸c˜ao de |ψ po de mudar mas n˜ao a sua norma. Na
´
Algebra Linear isso
´e descrito pela a¸c˜ao de um operador unit´ario U, que ´e uma matriz complexa 2 ×2
satisfazendo
UU
†
= I, (5.2)
39
onde U
†
= (U
∗
)
T
(∗ indica complexo conjugado e T indica a opera¸c˜ao transposta)
e I ´e a matriz identidade 2 × 2.
O produto tensorial ´e uma forma de se juntar espa¸cos vetoriais para formar
espa¸cos vetoriais maiores.
´
E necess´ario introduzir tal conceito para considerarmos
casos de m´ultiplos q-bits.
Suponha que V e W sejam espa¸cos vetoriais de dimens˜oes m e n, respecti-
vamente. Portanto, V ⊗W ´e um espa¸co vetorial com dimens˜ao mn. Os elementos
de V ⊗W s˜ao combina¸c˜oes lineares de pro dutos tensoriais |v⊗|w dos elementos
|v de V e |w de W . Em particular, se |i e |j s˜ao bases ortonormais de V e W ,
ent˜ao |i⊗|j ´e uma base de V ⊗ W . Freq
¨
uentemente se usa a nota¸c˜ao abreviada
|v|w, |v, w ou ainda |vw para o produto tensorial |v ⊗ |w.
Por defini¸c˜ao, o produto tensorial satisfaz as seguintes propriedades:
1. Para um escalar z arbitr´ario, e elementos |v de V e |w de W ,
z(|v ⊗ |w) = (z |v) ⊗ |w = |v ⊗ (z |w) (5.3)
2. Para |v
1
e |v
2
arbitr´arios em V e |w em W ,
(|v
1
+ |v
2
) ⊗ |w = |v
1
⊗ |w + |v
2
⊗ |w (5.4)
3. Para |v arbitr´ario em V e |w
1
e |w
2
em W ,
|v ⊗ (|w
1
+ |w
2
) = |v ⊗ |w
1
+ |v ⊗ |w
2
(5.5)
Mencionaremos a nota¸c˜ao |ψ
⊗k
para denotar o produto tensorial de |ψ por
ele mesmo k vezes.
Como exemplo, se n´os temos um computador quˆantico com 2 q-bits e o
primeiro q-bit est´a no estado |0 e o segundo est´a no estado |1, ent˜ao o computador
40
quˆantico est´a no estado |0 ⊗ |1, dado por
|0 ⊗ |1 = |01 =
1
0
⊗
0
1
=
0
1
0
0
(5.6)
O vetor resultante est´a no espa¸co vetorial 4-dimensional. O estado geral |ψ
de um computador quˆantico com 2 q-bits ´e uma superposi¸c˜ao dos estados |00,
|01, |10 e |11 (costuma-se representar tais estados na nota¸c˜ao decimal como |0,
|1, |2 e |3 respectivamente),
|ψ = α |00 + β |01 + γ |10 + δ |11, (5.7)
satisfazendo a |α|
2
+ |β|
2
+ |γ|
2
+ |δ|
2
= 1.
Em geral, o estado |ψ de um computador quˆantico com n q-bits est´a numa
superp osi¸c˜ao dos 2
n
estados |0, |1,. . ., |2
n
− 1,
|ψ =
2
n
−1
i=0
α
i
|i, (5.8)
com as amplitudes α
i
satisfazendo a
2
n
−1
i=0
|α
i
|
2
= 1. (5.9)
Note que a base ortonormal {|0, . . . , |2
n
− 1} ´e a base computacional na
nota¸c˜ao decimal. O estado de um computador quˆantico com n q-bits ´e um vetor
no espa¸co vetorial complexo 2
n
-dimensional.
Um espa¸co vetorial complexo V ´e um espa¸co de Hilbert se existe um produto
interno, escrevemos na forma ϕ|ψ, definido pelas seguintes regras (a, b ∈ C e |ϕ,
|ψ, |u, |v ∈ V ):
1. ψ|ϕ = ϕ|ψ
∗
,
41
2. ϕ|(a |u + b |v) = aϕ|u + bϕ|v,
3. ϕ|ϕ > 0 se |ϕ = 0.
onde ϕ| ´e o vetor dual (transposto conjugado) de |ϕ.
5.2 Operadores Unit´arios
Opera¸c˜oes sobre q-bits devem preservar a norma, e portanto s˜ao descritas
por matrizes unit´arias. Algumas das mais importantes (considerando um q-bit)
s˜ao as matrizes de Pauli, reproduzidas abaixo:
X ≡
0 1
1 0
; Y ≡
0 −i
i 0
; Z ≡
1 0
0 −1
(5.10)
A matriz X ´e a representa¸c˜ao da porta quˆantica NOT.
Outros operadores quˆanticos importantes s˜ao descritos a seguir, a porta de
Hadamard (denotada por H), a porta de fase (denotada por S) e a porta π/8
(denotada por T ):
H =
1
√
2
1 1
1 −1
; S =
1 0
0 i
; T =
1 0
0 exp (iπ/4)
(5.11)
A porta Hadamard ´e uma das portas quˆanticas mais ´uteis. Esta porta ´e
algumas vezes denominada de “raiz quadrada de NOT”, e transforma |0 em (|0+
|1)/
√
2 (primeira coluna de H), “meio caminho” entre |0 e |1, e transforma |1
em (|0 − |1)/
√
2 (segunda coluna de H), tamb´em “meio caminho” entre |0 e
|1. Note, contudo, que H
2
n˜ao ´e uma porta NOT; ´e f´acil mostrar que H
2
= I, e
portanto, aplicando H duas vezes, n˜ao altera o estado.
Mais detalhes sobre Computa¸c˜ao Quˆantica pode ser encontrado em [Nielsen
e Chuang (2000), Kaye et al. (2007), de Abreu (2004), Marquezino (2006), Lavor
et al. (2003), Lomont (2004)].
42
5.3 Problema do Subgrupo Oculto
Uma motiva¸c˜ao para estudar o Problema do Subgrupo Oculto (abreviaremos
por PSO) ´e que a maioria dos algoritmos quˆanticos encontrados, que s˜ao exponen-
cialmente mais r´apidos do que seus equivalentes cl´assicos s˜ao casos particulares de
algoritmos quˆanticos para a solu¸c˜ao do Problema do Subgrupo Oculto. Como ex-
emplo, citamos o Algoritmo de Simon [Simon (1994), Simon (1997)] e o Algoritmo
de Shor [Shor (1994), Shor (1997), Lavor et al. (2003)] para fatora¸c˜ao de inteiros
grandes. Os pesquisadores dessa ´area est˜ao interessados em estender a fam´ılia de
grupos para os quais o PSO pode ser resolvido eficientemente, e assim, desenvolver
algoritmos quˆanticos eficientes para problemas onde n˜ao existam algoritmos cl´assi-
cos eficientes, tais como determinar isomorfismos de grafos [Beals (1997), Ettinger
e Høyer (1999), Jozsa (2000), Ahn (2002), Lomont (2004)] ou encontrar o menor
vetor em um reticulado [Regev (2002), Regev (2004)].
Em 1994, [Shor (1994)] construiu com base nos trabalhos de [Deutsch (1985)]
e [Simon (1994)] um algoritmo quˆantico que pode fatorar inteiros grandes exponen-
cialmente mais r´apido do que qualquer m´etodo cl´assico conhecido, e assim abriu
as portas para a pesquisa sobre computa¸c˜ao quˆantica. Esse algoritmo permite a
quebra dos principais c´odigos de criptografia usados atualmente, como RSA, Diffie-
Hellman e ElGamal [Koblitz (1998)] caso um computador quˆantico de tamanho
razo´avel esteja dispon´ıvel. Shor tamb´em deu um algoritmo que resolve o problema
de logaritmo discreto, que ´e usado em diversos outros criptosistemas. Kitaev [Ki-
taev (1996)] notou que esses algoritmos, assim como outros, enquadram-se num
mesmo conjunto de problemas que consiste em encontrar geradores de um sub-
grupo a partir do grupo usando uma fun¸c˜ao que “oculta” o subgrupo, e assim o
PSO estava nascendo.
Defini¸c˜ao 23 Dada uma fun¸c˜ao eficientemente comput´avel f : G → X, de um
grupo finito G para um conjunto X, que ´e constante nas classes laterais (`a esquerda)
de algum subgrupo H de G e que toma valores distintos nas distintas classes laterais
de H em G, o problema do subgrupo oculto ´e achar um conjunto gerador para H.
43
Dizemos que o subgrupo H ´e “oculto” por f e a fun¸c˜ao f ´e chamada fun¸c˜ao
separadora de classes laterais.
N˜ao ´e conhecido nenhum algoritmo cl´assico eficiente para a solu¸c˜ao do PSO.
No entanto, atrav´es de algoritmos quˆanticos, tem se conseguido resolver, eficiente-
mente, o problema para v´arias classes de grupos.
Para maiores detalhes sobre o Problema do Subgrup o Oculto, consultar as
seguintes referˆencias, [Lomont (2004), Mosca e Ekert (1999), Gon¸calves (2005)].
5.3.1 Problema do Subgrupo Oculto Abeliano
Seja G um grup o abeliano finito. Sabemos do Teorema Fundamental para
grupos abelianos finitos (Teorema 2) que G ´e isomorfo ao produto direto de grupos
c´ıclicos, de ordens t
1
, t
2
, ..., t
n
. Ou seja,
G Z
t
1
× Z
t
2
× ... × Z
t
n
. (5.12)
Por simplicidade assumiremos que G ´e igual a este produto direto. Seja H
o espa¸co de Hilbert com base ortonormal {|g : g ∈ G} indexada pelos elementos
de G. Suponhamos um computador quˆantico atuando em H (sabemos que se o
n´umero de q-bits aumenta linearmente ent˜ao dim H aumenta exponencialmente).
Portanto, para implementarmos isto fisicamente precisamos de n = log
2
|G| q-
bits. O estado de um computador quˆantico com n q-bits ´e um vetor num espa¸co
vetorial complexo de dimens˜ao 2
n
.
Defini¸c˜ao 24 Um car´ater de um grupo G ´e um homomorfismo de grupo de G
para o grupo multiplicativo de n´umeros complexos diferentes de zero C
∗
. Ou seja,
´e uma fun¸c˜ao de conjuntos χ : G → C
∗
tal que χ(g
1
+ g
2
) = χ(g
1
)χ(g
2
).
Supondo G = Z
t
, temos para cada elemento g ∈ Z
t
,
χ
g
(h) = e
2πi
t
gh
= ω
gh
t
(5.13)
onde ω
t
= e
2πi
t
´e a raiz complexa t-´esima da unidade.
44
Veja que g e h podem ser pensados como inteiros entre 0 e t − 1. Para um
caso mais geral, G = Z
t
1
×Z
t
2
×... ×Z
t
n
, podemos pensar nos elementos g, h como
g = (g
1
, g
2
, ..., g
n
) e h = (h
1
, h
2
, ..., h
n
). Neste caso, definimos
χ
g
(h) =
n
i=1
ω
g
i
h
i
t
i
(5.14)
Algumas propriedades dos car´ateres.
Lema 3 Para qualquer g, h ∈ G, χ
g
(h) = χ
h
(g).
Demonstra¸c˜ao: Trivial, G ´e abeliano.
Lema 4 Considere |G| vetores de valor complexo
|v
g
=
1
|G|
χ
g
(h
1
)
χ
g
(h
2
)
.
.
.
χ
g
(h
|G|
)
(5.15)
Um vetor para cada g ∈ G, onde h
1
, ..., h
|G|
´e uma lista completa de elementos de
G. Esses vetores s˜ao unit´arios e s˜ao ortogonais dois a dois. Em particular, n´os
temos para algum g = 0 que
i
χ
g
(h
i
) = 0.
Demonstra¸c˜ao: Ver [Damgard (2004)].
Construiremos uma matriz |G|×|G|, cujas colunas s˜ao os vetores |v
g
definidos
acima (Equa¸c˜ao 5.15).
F
G
=
1
|G|
χ
g
1
(h
1
) χ
g
2
(h
1
) . . . χ
g
|G|
(h
1
)
χ
g
1
(h
2
) χ
g
2
(h
2
) . . . χ
g
|G|
(h
2
)
.
.
.
.
.
.
.
.
.
.
.
.
χ
g
1
(h
|G|
) χ
g
2
(h
|G|
) . . . χ
g
|G|
(h
|G|
)
(5.16)
45
Segue das rela¸c˜oes de ortogonalidade de car´ateres [Serre (1977)] que esta matriz ´e
unit´aria. Logo o operador definido por esta matriz, chamado F
G
´e unit´ario. Dize-
mos ent˜ao que F
G
´e a Transformada de Fourier em grupos abelianos. Podemos
tamb´em defin´ı-la por sua atua¸c˜ao nos vetores da base como:
F
G
|g =
1
|G|
h∈G
χ
g
(h) |h (5.17)
A sa´ıda de F
G
´e o estado quˆantico correspondente ao vetor |v
g
, que tem a
forma acima quando escrito na nota¸c˜ao usual para um estado. J´a que o operador
´e unit´ario ele pode ser implementado num computador quˆantico.
Se G = Z
2
× Z
2
× ... × Z
2
´e o grupo com a opera¸c˜ao XOR (adi¸c˜ao m´odulo
2), temos que ω
t
= ω
2
= −1. Ent˜ao n´os podemos pensar nos elementos g, h ∈ G
como n−uplas g = (g
1
, ..., g
n
), h = (h
1
, ..., h
n
) onde g
i
, h
i
assumem os valores 0 ou
1. Consequentemente n´os temos χ
g
(h) =
n
i=1
(−1)
g
i
h
i
. Usando isso na defini¸c˜ao
de F
G
acima (Equa¸c˜ao 5.17), n´os temos:
F
G
|g =
1
|G|
h∈G
χ
g
(h) |h
=
1
|G|
h∈G
(
n
i=1
(−1)
g
i
h
i
) |h
=
1
|G|
h∈G
(−1)
g·h
|h,
onde g · h ´e o produto interno usual. Em outras palavras, a transformada de
Hadamard, F
G
= H
⊗n
.
Defini¸c˜ao 25 (O Subgrupo Ortogonal) Para qualquer subgrupo H de um grupo
finito G, definimos o subgrupo ortogonal H
⊥
, como
H
⊥
= {g ∈ G | χ
g
(h) = 1, ∀h ∈ H} (5.18)
Como G ´e finito e χ
g
+g
= χ
g
χ
g
, ou seja, H
⊥
´e fechado, temos que H
⊥
´e
realmente um subgrupo de G [Damgard (2004)].
46
O teorema abaixo mostra uma importante rela¸c˜ao entre H
⊥
e H.
Teorema 12 Temos H
⊥
G/H, em particular |H
⊥
| = |G|/|H|.
Demonstra¸c˜ao: Ver [Lomont (2004)].
Mostraremos agora que para um grupo abeliano gen´erico (finito) G, F
G
pro-
duz uma superposi¸c˜ao sobre os elementos em H
⊥
, qualquer que seja H < G.
Lema 5 Para qualquer classe lateral H
i
de H em G, temos
F
G
1
|H|
g∈H
i
|g
=
1
|H
⊥
|
h∈H
⊥
χ
h
(g
i
) |h (5.19)
onde g
i
´e um elemento fixo representante da classe lateral H
i
.
Demonstra¸c˜ao: Ver [Damgard (2004), Gon¸calves (2005)].
Apresentaremos agora um algoritmo eficiente (m´etodo padr˜ao de solu¸c˜ao
para grupos c´ıclicos) para o PSO, isto ´e, um algoritmo que rode em tempo polino-
mial em log
2
|G| [Damgard (2004), Lomont (2004)].
Assumiremos que temos dois registradores: um registrador com n = log
2
|G|
q-bits e o segundo registrador com m q-bits, onde n ≥ m. O algoritmo usa a
seguinte subrotina:
Passo 1. Inicialize o computador quˆantico no estado |0
G
|0
m
, onde |0
G
´e o
estado da base correspondente ao elemento neutro de G. Depois aplique F
G
no
primeiro registrador para obter
1
|G|
g∈G
|g|0
m
.
Passo 2. Aplicando U
f
no estado anterior, obtemos
1
|G|
g∈G
|g|f(g).
47
Repare, que como U
f
´e linear, ele atua em todos os |g|0
m
para |G| valores de
g, ent˜ao isto gera todos os f (g) simultaneamente. Este ´e o chamado paralelismo
quˆantico.
Passo 3. Me¸ca o segundo registrador do estado anterior. A medida, segundo um
postulado da mecˆanica quˆantica, provoca um dist´urbio no estado original. Este
estado por sua vez ´e levado em
1
|H|
g
0
∈H
i
|g
0
|f(g
0
).
onde H
i
´e alguma classe lateral de H. A constante foi renormalizada j´a que so-
braram apenas |H| elementos na soma. Estes elementos s˜ao aqueles cuja imagem
´e f(g
0
).
Passo 4. Aplique F
G
no primeiro registrador e obtenha ent˜ao uma superposi¸c˜ao
sobre H
⊥
. Pelo Lema 5, temos
1
|H
⊥
|
h∈H
⊥
χ
h
(g
i
) |h|f(g
0
).
onde g
i
´e um elemento fixo representante da classe lateral H
i
.
Passo 5. Me¸ca agora o primeiro registrador. A medida produz um elemento
randˆomico em H
⊥
.
Passo 6. Segue do Teorema 1 que se este procedimento for repetido um n´umero de
vezes logaritmico em |G| (logo polinomial em n) obtemos um conjunto de geradores
para H
⊥
. Usando as rela¸c˜oes entre H e H
⊥
podemos calcular um conjunto de
geradores para H com probabilidade pr´oxima de 1.
5.3.2 Problema do Subgrupo Oculto N˜ao Abeliano
Porque n´os queremos encontrar os subgrupos ocultos de grupos n˜ao-abelianos?
J´a vimos que um algoritmo eficiente para o PSO abeliano produz um algoritmo
48
de fatora¸c˜ao de inteiros que ´e exponencialmente mais r´apido do que qualquer al-
goritmo cl´assico conhecido. Similarmente, encontrar algoritmos eficientes para o
PSO sobre certos grupos n˜ao-abelianos poderia produzir algoritmos mais r´apidos
do que qualquer algoritmo cl´assico para diversos problemas importantes.
Uma das principais raz˜oes que levam muitos pesquisadores a estudar o PSO
para grupos n˜ao-abelianos ´e o desejo em encontrar um algoritmo eficiente para o
problema de isomorfismos de grafos. Uma redu¸c˜ao (ver Se¸c˜ao 6.1) mostra que se
o PSO puder ser resolvido eficientemente para o grupo sim´etrico S
n
, ent˜ao n´os
ter´ıamos um algoritmo em tempo polinomial para o problema de isomorfismo de
grafos [Beals (1997), Ettinger e Høyer (1999), Jozsa (2000), Ahn (2002), Lomont
(2004)].
Outra raz˜ao ´e que um algoritmo quˆantico eficiente para resolver o PSO para
o grupo diedral D
n
produz um algoritmo r´apido para encontrar o menor vetor num
reticulado, primeiro mostrado por [Regev (2002)]. Isso poderia produzir outro al-
goritmo cuja a contrapartida cl´assica ´e menos eficiente do que a vers˜ao quˆantica.
Encontrar o menor vetor num reticulado tem muitas aplica¸c˜oes, incluindo apli-
ca¸c˜oes para a criptografia. Foi desenvolvido p or [Kuperberg (2005)] um algoritmo
quˆantico subexponencial no tamanho da entrada. Posteriormente, [Regev (2004)]
apresentou uma vers˜ao melhorada do algoritmo de Kuperberg, onde o tempo de
processamento do algoritmo ainda ´e subexponencial, mas a quantidade de mem´oria
utilizada ´e polinomial no tamanho da entrada.
Embora grande esfor¸co esteja sendo empregado, estes dois casos do PSO n˜ao
abeliano, continuam em aberto e desafiando a comunidade cient´ıfica. Mas, alguns
sucessos em grupos n˜ao abelianos foram conseguidos. Por exemplo,[Hallgren et al.
(2000)] demonstraram que existe um algoritmo quˆantico eficiente para a solu¸c˜ao
do PSO em um grupo qualquer desde que a Transformada de Fourier Quˆantica
seja eficientemente implement´avel no grupo e que o subgrupo oculto seja normal.
Foi mostrado [Ivanyos et al. (2003)] ser poss´ıvel resolver eficientemente o PSO
em grupos n˜ao abelianos onde a ordem do subgrupo de comutadores seja pequena
49
em rela¸c˜ao `a ordem do grupo, no sentido de que |G
| seja O(log |G|).
Como o grupo diedral pode ser escrito como o produto semidireto Z
n
Z
2
,
um caminho natural foi estudar novos algoritmos quˆanticos para o PSO para gru-
pos n˜ao abelianos que se escrevem como o produto semidireto de grupos c´ıclicos.
Em [Inui e Le Gall (2005)], os autores apresentaram uma solu¸c˜ao para o PSO no
grupo Z
p
r
Z
p
, p inteiro primo e r um inteiro positivo. Neste trabalho os autores
utilizaram a Transformada de Fourier Quˆantica no grupo abeliano. Seguindo esta
linha, [Cosme e Portugal (2007)] apresentaram um algoritmo quˆantico eficiente
para o PSO, no produto semidireto de grupos c´ıclicos Z
p
r
φ
Z
p
2
, onde p ´e qual-
quer n´umero primo e r ´e um inteiro qualquer tal que r > 4. Tamb´em foi abordado
o PSO no grupo Z
N
φ
Z
p
2
, onde N ´e um n´umero inteiro com uma fatora¸c˜ao
prima especial. Estes algoritmos quˆanticos s˜ao exp onencialmente mais r´apido do
que qualquer algoritmo cl´assico para o mesmo fim. Tamb´em nesta dire¸c˜ao, [Cosme
(2008)] apresentou um algoritmo quˆantico eficiente para o PSO no produto semidi-
reto Z
p
r
φ
Z
p
s
, onde p ´e qualquer n´umero primo ´ımpar, r e s s˜ao inteiros positivos
e o homomorfismo φ est´a em fun¸c˜ao de p, r e s. Como consequˆencia, pode-se re-
solver eficientemente o PSO tamb´em no grupo Z
N
φ
Z
p
s
, onde o inteiro N possui
uma fatora¸c˜ao prima especial.
Foi dado por [Ivanyos et al. (2007a)] um algoritmo quˆantico eficiente para
a classe dos grupos extra-especiais. Num trabalho posterior, os mesmos autores
resolveram o problema do PSO para a classe de grupos nilpotentes de classe 2
[Ivanyos et al. (2007b)]. Para uma leitura mais detalhada sobre este ´ultimo pro-
blema podemos tamb´em consultar [Fernandes (2008)].
Para mais detalhes sobre o PSO n˜ao abeliano, podemos consultar [Ivanyos
et al. (2003), Inui e Le Gall (2005), Ivanyos et al. (2007a), Cosme (2008)].
50
Cap´ıtulo 6
Aplica¸c˜oes da Computa¸c˜ao Quˆantica ao
Problema do Isomorfismo de Grafos
Nesse cap´ıtulo, vamos mostrar que uma solu¸c˜ao eficiente do PSO no grupo
sim´etrico S
n
implicar´a num algoritmo de tempo polinomial para decidir se dois
grafos s˜ao isomorfos ou n˜ao [Ahn (2002)]. Utilizaremos o Problema de Interse¸c˜ao
de Grupos de permuta¸c˜oes [Hoffman (1979), Fenner e Zhang (2005)] para encontrar
um algoritmo quˆantico para o Problema do Isomorfismo de Grafos para a classe
de grafos A
n
(definida na Se¸c˜ao 4.2), mostrando assim o poder da Computa¸c˜ao
Quˆantica.
6.1 Redu¸c˜ao do Problema do Isomorfismo de Grafos para o Pro-
blema do Subgrupo Oculto
Existem algumas maneiras de reduzir o PIG para o PSO [Beals (1997), Et-
tinger e Høyer (1999), Jozsa (2000), Ahn (2002), Lomont (2004)]. Nesta se¸c˜ao
vamos apresentar o modelo descrito por [Ahn (2002)]. A redu¸c˜ao possui dois pas-
sos: No primeiro passo, o PAG ´e reduzido para o PSO no grupo sim´etrico S
n
e
ent˜ao, no segundo passo, o PIG ´e reduzido para o PAG.
Podemos pensar em S
n
agindo num grafo Γ de ordem n como a seguir: Cada
elemento σ ∈ S
n
´e uma permuta¸c˜ao (ou reordena¸c˜ao) dos n ´umeros {1, 2, . . . , n};
podemos pensar em σΓ como uma reclassifica¸c˜ao (nova rotula¸c˜ao) dos n v´ertices
de Γ. Por exemplo, se σ ´e a permuta¸c˜ao que leva {1, 2, 3, 4} para {4, 3, 2, 1} e Γ ´e
51
como na Figura 6.1, ent˜ao σΓ ´e como na Figura 6.2.
1
2
4
3
Γ
Figura 6.1: Grafo Γ
Uma boa maneira de visualizar um automorfismo de Γ ´e pensar a respeito
da a¸c˜ao de S
n
em Γ. Elementos de S
n
renomeiam os v´ertices de Γ: Come¸camos
com um grafo Γ (como na Figura 6.1) e ent˜ao, sem mover nenhuma aresta, n´os
simplesmente renomeamos os v´ertices; o resultado deste processo ´e mostrado no
lado esquerdo da Figura 6.2 para a permuta¸c˜ao σ = (1, 4)(2, 3). Ap´os isso, pode-
mos mover os v´ertices para suas posi¸c˜oes originais; o resultado desse movimento
´e mostrado no lado direito da Figura 6.2. Um automorfismo de um grafo ´e um
elemento de S
n
para o qual os grafos inicial e final deste processo coincidem perfeita-
mente. Portanto σ = (1, 4)(2, 3) n˜ao ´e um automorfismo. Denotamos p or fix(σΓ)
a representa¸c˜ao do grafo que resulta deste processo (assim, em nosso exemplo, a
representa¸c˜ao do lado direito da Figura 6.2 ´e fix(σΓ). Com esta nota¸c˜ao, σ ´e um
automorfismo se e s´o se fix(σΓ) =fix(eΓ), onde e ´e a permuta¸c˜ao identidade de S
n
.
1
2
4
3
=
1
4
2
3
Figura 6.2: Grafo σΓ
Vamos denotar por R o conjunto de todas as representa¸c˜oes dos grafos
fix(σΓ) para todo σ ∈ S
n
.
52
Mostraremos agora que o PAG pode ser visto como um PSO, PAG ∝
p
PSO
(PAG ´e redut´ıvel polinomialmente para o PSO, ou seja, resolver eficientemente
o PSO implica resolver eficientemente o PAG). De fato, seja Γ um grafo com n
v´ertices, consideremos V = {1, . . . , n}. Seja f
Γ
uma fun¸c˜ao de S
n
que leva cada
elemento (permuta¸c˜ao) σ para fix(σΓ). A saber,
f
Γ
: S
n
→ R
σ →fix(σΓ)
Sejam σ
1
Aut(Γ), σ
2
Aut(Γ), . . . , σ
k
Aut(Γ) classes laterais de Aut(Γ). Sabe-
mos que um grupo finito pode ser escrito como a uni˜ao disjunta de suas classes
laterais (ver Se¸c˜ao 2.1), ou seja, S
n
= σ
1
Aut(Γ) ∪ σ
2
Aut(Γ) ∪ . . . ∪ σ
k
Aut(Γ),
σ
i
∈ S
n
, σ
i
= σ
j
. Segue ent˜ao que f
Γ
´e constante nas classes laterais de Aut(Γ) e
distinta em cada classe lateral. Portanto, PAG ´e um PSO, onde G = S
n
, X = R,
H =Aut(Γ) e f
Γ
´e a fun¸c˜ao que esconde o subgrupo Aut(Γ), de acordo com a
Defini¸c˜ao 23.
Agora, mostraremos o ´ultimo passo, ou seja, um algoritmo eficiente para re-
solver o PAG implica num algoritmo eficiente para resolver o PIG [Mathon (1979)].
Teorema 13 O Problema do Isomorfismos de Grafos ´e redut´ıvel polinomialmente
para o Problema do Automorfismos de Grafos, PIG ∝
p
PAG.
Demonstra¸c˜ao: Sejam Γ
1
= (V
1
, E
1
) e Γ
2
= (V
2
, E
2
) dois grafos conexos com n
v´ertices cada e seja Γ
3
= Γ
1
∪ Γ
2
a uni˜ao disjunta de Γ
1
e Γ
2
(ver Defini¸c˜ao 20).
Suponhamos que exista um algoritmo eficiente para resolver o PAG. Aplicamos
ent˜ao tal algoritmo em Γ
3
= Γ
1
∪ Γ
2
. Se ∃ σ ∈ Aut(Γ
3
) tal que σ(v) = u, para
algum v ∈ V
1
, u ∈ V
2
ent˜ao para qualquer v
∈ V
1
teremos σ(v
) = u
, u
∈ V
2
,
pois os conjuntos V
1
e V
2
s˜ao disjuntos e σ leva aresta em aresta. Ent˜ao teremos
σ(V
1
) = V
2
, portanto Γ
1
Γ
2
. Caso contr´ario, ou seja, se σ ∈ Aut(Γ
3
) com tal
propriedade ent˜ao Γ
1
/ Γ
2
.
53
J´a t´ınhamos do Teorema 9 que resolver eficientemente o PIG implica em
resolver eficientemente o PAG. Portanto os dois problemas s˜ao equivalentes poli-
nomialmente. Na verdade, temos um conjunto de problemas equivalentes polino-
mialmente [Mathon (1979)]. Os Problemas 1 e 2 s˜ao tamb´em equivalentes aos
seguintes problemas: Construir explicitamente um isomorfismo entre grafos; deter-
minar o n´umero de isomorfismos entre grafos e determinar a ordem do grupo de
automorfismos do grafo.
6.2 Grupos Or´aculo
O modelo de grupos Or´aculo foi introduzido por [Babai e Szemer´edi (1984)]
como uma estrutura geral para estudos de problemas algor´ıtmicos para grupos fini-
tos e desde ent˜ao tˆem sido estudados extensivamente. Temos a seguinte defini¸c˜ao:
Defini¸c˜ao 26 Seja um grupo G tal que:
(i) Cada elemento de G pode ser codificado como uma palavra bin´aria de
mesmo comprimento, isto ´e, n´umero de bits. Este n´umero ´e chamado
comprimento da codifica¸c˜ao;
(ii) H´a um or´aculo (Caixa Preta) que realiza a opera¸c˜ao do grupo nesta
codifica¸c˜ao com custo unit´ario;
(iii) Caso a codifica¸c˜ao n˜ao seja ´unica, isto ´e, um elemento em G possuir mais
de uma palavra o representando, ent˜ao um segundo or´aculo ´e requerido
para testar identidade na codifica¸c˜ao de G.
Se o grupo G ´e dado por um conjunto de palavras representando geradores para o
mesmo, ent˜ao, ele ´e chamado um grupo or´aculo.
Assim, um grup o or´aculo com comprimento de codifica¸c˜ao n tem ordem
limitada por 2
n
, o n´umero de palavras bin´arias de comprimento n, portanto todo
grupo or´aculo ´e finito. Note que nem toda palavra bin´aria de comprimento n
necessariamente corresp onde a um elemento do grupo. Sendo assim, podemos
54
imaginar que nosso grupo or´aculo tenha algum comportamento arbitr´ario dadas
codifica¸c˜oes inv´alidas. Logo, n˜ao o acessaremos com um elemento inv´alido do
grupo. Se dissermos que um grupo particular ou subgrupo or´aculo ´e dado (para
algum algoritmo), queremos dizer com isso que um conjunto de palavras que geram
o grupo ou subgrupo ´e dado.
Admitiremos que os grupos or´aculo aqui tratados tˆem codifica¸c˜ao ´unica, fato
este que evita a exigˆencia do segundo or´aculo (Caixa Preta) da Defini¸c˜ao 26. Dado
um grupo or´aculo G de comprimento de codifica¸c˜ao n, teremos associado uma
porta quˆantica (transforma¸c˜ao unit´aria) U
G
agindo sobre 2n q-bits como segue:
U
G
|g|h = |g|gh. (6.1)
Aqui, como j´a foi dito, assumimos que g e h s˜ao dados como codifica¸c˜oes
v´alidas do grupo. A inversa de U
G
´e
U
−1
G
|g|h = |g
g
−1
h
. (6.2)
As portas U
G
e U
−1
G
s˜ao os or´aculos do grupo. S˜ao elas que efetuam a
opera¸c˜ao do grupo na codifica¸c˜ao especificada.
Para saber como implementar grupos or´aculo na forma de circuitos quˆanticos,
ver [Watrous (2001)].
6.3 Problemas relacionados com o Problema do Subgrupo Oculto
Em [Friedl et al. (2003)] foram introduzidos diversos problemas que est˜ao in-
timamente relacionados com o Problema do Subgrupo Oculto. Em particular, eles
introduziram o Problema Estabilizador que generaliza o Problema do Subgrupo
Oculto. De fato, a ´unica diferen¸ca entre Problema Estabilizador e o Problema do
Subgrupo Oculto ´e que na defini¸c˜ao do Problema Estabilizador a fun¸c˜ao f pode
ser uma fun¸c˜ao quˆantica que leva elementos do grupo para estados quˆanticos mu-
tuamente ortogonais com norma unit´aria.
55
Seja G um grupo finito. Seja ∆ um conjunto de estados quˆanticos mutua-
mente ortogonais. Seja α : G × ∆ → ∆ uma a¸c˜ao de grupo de G sobre ∆, isto
´e, para todo x ∈ G a fun¸c˜ao α
x
: |φ → |α(x, |φ) ´e uma permuta¸c˜ao sobre ∆
e a fun¸c˜ao h de G para o grupo sim´etrico sobre ∆ definida por h(x) = α
x
´e um
isomorfismo.
Usaremos a nota¸c˜ao |x · φ para o estado |α(x, |φ), quando α ´e claro no
contexto. Seja G(|φ) denotando o conjunto {|x · φ = |φ}, e seja G
|φ
denotando
o subgrupo Estabilizador de |φ em G, isto ´e, {x ∈ G; |x · φ = |φ}. Dado um
inteiro positivo t, seja α
t
a a¸c˜ao do grupo G sobre ∆
t
= {|φ
⊗t
; |φ ∈ ∆} definido
por α
t
(x, |φ
⊗t
) = |x · φ
⊗t
. N´os precisamos de α
t
porque as superposi¸c˜oes de
entrada n˜ao podem ser clonadas em geral (Teorema da N˜ao-Clonagem).
Agora, definiremos o chamado Problema Estabilizador, que consiste em en-
contrar O(log |G|) geradores para o subgrupo G
|φ
.
Problema 4 Seja G um grupo finito e ∆ um conjunto de estados quˆanticos mu-
tuamente ortogonais. Fixamos a a¸c˜ao de grupo α : G × ∆ → ∆. Ent˜ao, dados
geradores para G e estados quˆanticos |φ ∈ ∆, o Problema Estabilizador consiste
em encontrar um conjunto gerador para o subgrupo G
|φ
= {x ∈ G; |x · φ = |φ}.
Para grupos abelianos finitos, o Problema Estabilizador ´e resolvido eficien-
temente por um algoritmo quˆantico com erro [Kitaev (1996)]. Al´em disso, os
problemas de fatora¸c˜ao e do logaritmo discreto podem ser reduzidos para o Pro-
blema Estabilizador Abeliano.
Se o grupo G for sol´uvel tal problema pode ser resolvido em tempo polinomial
quˆantico sobre certos crit´erios de solubilidade fortes. De fato, temos o seguinte
teorema devido a [Friedl et al. (2003)].
Teorema 14 Seja G um grupo sol´uvel finito que tem um subgrupo comutador
suavemente sol´uvel e seja α uma a¸c˜ao de grupo de G. Quando t = (log
Ω(1)
|G|)×
log(1/), o Problema Estabilizador pode ser resolvido em G para α
t
em tempo
poli(log |G|)log(1/) quˆantico com erro .
56
Foram descritas por [Fenner e Zhang (2005)] redu¸c˜oes quˆanticas para v´arios
problemas. Algoritmos quˆanticos para esses problemas freq
¨
uentemente requerem
diversas c´opias idˆenticas de um estado quˆantico ou porta unit´aria para trabalhar
com uma precis˜ao desejada. Consequentemente, vamos assumir implicitamente que
tais redu¸c˜oes podem ser repetidas t vezes, onde t ´e algum parˆametro polinomial
apropriado no tamanho da entrada e logar´ıtmico no tamanho do erro desejado.
6.4 Algoritmo Quˆantico
Relataremos progressos conseguidos por [Fenner e Zhang (2005)] em encon-
trar algoritmos quˆanticos para Interse¸c˜ao de Grupos. Mostraremos que se um
dos grupos em quest˜ao for sol´uvel, existe um algoritmo quˆantico eficiente para o
Problema de Interse¸c˜ao de Grupos se tal grupo possui um subgrupo comutador
suavemente sol´uvel. Al´em disso, segue como corol´ario que se ambos os grupos
forem sol´uveis existe um algoritmo quˆantico eficiente para o Problema de Inter-
se¸c˜ao de Grupos se um dos grupos em quest˜ao possui um subgrup o comutador
suavemente sol´uvel.
Antes disso, um algoritmo quˆantico eficiente para computar a ordem de um
grupo sol´uvel foi dado por [Watrous (2001)], al´em disso, ele obteve um m´etodo para
construir (aproximadamente) superposi¸c˜oes quˆanticas uniformes sobre elementos
deste grupo sol´uvel. Conforme vemos no teorema abaixo.
Teorema 15 (Watrous (2001)) No modelo de grupos Or´aculo com codifica¸c˜ao
´unica, existe um algoritmo quˆantico operando da seguinte forma (relativo a um
grupo or´aculo arbitr´ario). Dados geradores g
1
, . . . , g
m
tais que G = g
1
, . . . , g
m
´e
sol´uvel, a sa´ıda do algoritmo ´e a ordem de G com probabilidade de erro limitado
por em tempo polinomial em mn+log(1/)(onde n ´e o comprimento das palavras
que representam os geradores). Al´em disso, o algoritmo produz um estado quˆantico
ρ que aproxima o estado |G = |G|
−1/2
Σ
g∈G
|g com precis˜ao (no tra¸co da norma
m´etrica).
Agora, podemos enunciar um teorema que relaciona o Problema de Interse¸c˜ao
57
de Grupos com o Problema Estabilizador. Na verdade, o primeiro problema reduz-
se para o segundo, tendo como hip´otese adicional um dos grupos em quest˜ao ser
sol´uvel.
Teorema 16 O Problema de Interse¸c˜ao de Grupos reduz-se para o Problema Es-
tabilizador em tempo polinomial quˆantico com erro limitado se um dos grupos em
quest˜ao for sol´uvel.
Demonstra¸c˜ao: Dada uma entrada (A, B, n) para o Problema de Interse¸c˜ao de
Grupos, sem perda de generalidade, suponha que G = A ´e um grupo finito
arbitr´ario e H = B ´e sol´uvel. Pelo Teorema 15 n´os podemos construir (apro-
ximadamente) uma superposi¸c˜ao uniforme |H = |H|
−1/2
Σ
h∈H
|h. Para qualquer
g ∈ G, seja |gH denotando a superp osi¸c˜ao uniforme sobre classes laterais gH,
isto ´e, |gH = |H|
−1/2
Σ
h∈gH
|h. Seja ∆ = {|gH; g ∈ G}. Note que os estados
quˆanticos em ∆ s˜ao (aproximadamente) ortogonais dois a dois. Definimos a a¸c˜ao
de grupo como α : G × ∆ → ∆ para cada g ∈ G e cada |φ ∈ ∆, α(g, |φ) = |gφ.
Ent˜ao a interse¸c˜ao de G e H ´e exatamente o subgrupo de G que estabiliza o estado
quˆantico |H, a saber, G
|H
= {g ∈ G; |g · H = |H}.
Corol´ario 5 O Problema de Interse¸c˜ao de Grupos sobre grupos sol´uveis pode ser
resolvido com erro por um algoritmo quˆantico que corre em tempo polinomial em
m + log(1/), onde m ´e o tamanho da entrada, dado que um dos grupos sol´uveis
em quest˜ao tenha um subgrupo comutador suavemente sol´uvel.
Demonstra¸c˜ao: Segue diretamente dos Teoremas 16 e 14.
6.5 Exemplo
A classe de grupos sol´uveis ´e a maior classe para a qual existe algoritmos
quˆanticos eficientes at´e o presente momento, por exemplo o c´alculo da ordem do
grupo. No entanto, o m´etodo descrito no Teorema 11 requer algoritmos quˆanticos
58
eficientes para os grupos S
n
e T que n˜ao s˜ao sol´uveis. Se o grupo de automorfismos
do grafo for sol´uvel, podemos usar uma estrat´egia de tentativa e erro com grupos
sol´uveis que sejam subgrupos de S
n
e T . Se o grupo de automorfismos de um grafo
estiver na interse¸c˜ao desses grupos sol´uveis, os geradores de Aut(Γ) podem ser
encontrados eficientemente, desde que um dos grupos sol´uveis possua um subgrupo
comutador suavemente sol´uvel. Essa restri¸c˜ao adicional ´e exigida no Corol´ario 5.
A seguir vamos dar um exemplo onde essa estrat´egia funcione.
Exemplo 8 Considere a classe de grafos A
n
= (V
A
n
, E
A
n
), onde V
A
n
= {a
i
, b
i
, c
i
:
0 ≤ i < n} e E
A
n
= {(a
i
, a
i+1
), (a
i
, b
i
), (a
i
, c
i
), (b
i
, c
i
), (c
i
, a
i+1
) : 0 ≤ i < n}, como
descrito na Se¸c˜ao 4.2. Se n = 3 temos o grafo da Figura 4.2.
As n˜ao-arestas de A
n
s˜ao dadas pelo seguinte conjunto
E
A
n
= {(a
i
, a
j
) : i = j, j = i ± 1; (a
i
, b
j
) : i = j; (a
i
, c
j
) : i = j, j = i − 1;
(b
i
, b
j
) : i = j; (b
i
, c
j
) : i = j; (c
i
, c
j
) : i = j; 0 ≤ i, j < n}.
Sabemos que |E
A
n
| = 5n e que |E
A
n
| + |E
A
n
| = |K
3n
|. Portanto,
|E
A
n
| = 3n(3n − 1)/2 − 5n = (9n
2
− 13n)/2. (6.3)
Agora, reescreveremos o conjunto E
A
n
de tal forma que 1 represente (a
0
, a
1
),
2 represente (a
1
, a
2
), assim por diante, at´e n representando (a
n−1
, a
0
). Da mesma
forma n + 1 representa (a
0
, b
0
), n + 2 representa (a
1
, b
1
), assim por diante, at´e 2n
representando (a
n−1
, b
n−1
). Continuando, 2n + 1 representa (b
0
, c
0
), 2n + 2 repre-
senta (b
1
, c
1
), assim por diante, at´e 3n representando (b
n−1
, c
n−1
). Prosseguindo,
3n+ 1 representa (a
0
, c
0
), 3n +2 representa (a
1
, c
1
), assim por diante, at´e 4n repre-
sentando (a
n−1
, c
n−1
). Finalmente 4n + 1 representando (a
1
, c
0
), 4n + 2 representa
(a
2
, c
1
), assim por diante, at´e 5n representando (a
n
, c
n−1
). Da mesma forma, para
o conjunto E
A
n
, vamos representar (b
0
, a
1
) por 5n + 1, (b
1
, a
2
) por 5n + 2, assim
por diante, at´e (b
n−1
, a
0
) sendo representado por 6n. N˜ao identificaremos as outras
n˜ao-arestas, pois elas n˜ao ser˜ao referidas posteriormente.
59
Definiremos agora o conjunto T como sendo o produto direto de P(E
A
n
)
com P(E
A
n
), ou seja, T = P(E
A
n
) × P(E
A
n
). Notemos que |P(E
A
n
)| = 5n! e
que |P(E
A
n
)| = (
9n
2
−13n
2
)!. As permuta¸c˜oes (1, 2),(1, 2, . . . , 5n),(5n + 1, 5n + 2) e
(5n + 1, 5n + 2, . . . , 3n(3n − 1)/2) formam um conjunto gerador para T .
Por outro lado, construiremos tamb´em o grupo S
3n
a partir de S
3n
, usando
o seguinte homomorfismo, conforme Proposi¸c˜ao 6.
ψ
π
(i, j) = (π(i), π(j)), π ∈ S
3n
, 1 ≤ i, j ≤ 3n, i = j.
Logo,
S
3n
= {ψ
π
; ψ
π
(i, j) = (π(i), π(j)), π ∈ S
3n
, 1 ≤ i, j ≤ 3n, i = j} < S
3n(3n−1)/2
.
Como π
1
= (1, 2) e π
2
= (1, 2, . . . , 3n) s˜ao geradores para o grupo S
3n
, ent˜ao
ψ
π
1
e ψ
π
2
s˜ao geradores para o grupo S
3n
.
Assim, pelo Teorema 11 temos que Aut(A
n
) S
3n
∩T . Logo, achar Aut(A
n
)
reduz-se a achar S
3n
∩ T . Al´em disso, o Teorema 16 nos diz que o problema
de interse¸c˜ao de grupos reduz-se ao problema estabilizador em tempo polinomial
quˆantico com erro limitado se um dos grupos em quest˜ao for sol´uvel. Mais ainda, se
ambos os grupos forem sol´uveis, o Corol´ario 5 nos diz que o problema de interse¸c˜ao
de grupos pode ser resolvido eficientemente, desde que um dos grupos sol´uveis
possua um subgrupo comutador suavemente sol´uvel. A restri¸c˜ao de subgrupos
comutadores suavemente sol´uveis infelizmente reduz bastante a possibilidade de
uso de algoritmos quˆanticos para a solu¸c˜ao do PIG.
Um exemplo onde a estrat´egia adotada nessa se¸c˜ao funciona ´e tomar qualquer
grupo abeliano subgrupo do S
3n
que contenha o grup o Aut(A
n
) e o mesmo para
T . Uma vez que o subgrupo comutador de grupos ab elianos ´e suavemente sol´uvel,
o Corol´ario 5 exibe um algoritmo quˆantico que acha os geradores de Aut(A
n
)
eficientemente.
Exemplo 9 Vamos dar um exemplo que mostra a limita¸c˜ao dos algoritmos quˆan-
60
ticos desenvolvidos at´e o presente momento para determinar eficientemente os ge-
radores da interse¸c˜ao de dois grupos sol´uveis. Vamos tomar dois grupos diedrais,
um subgrupo de S
3n
e outro subgrupo de T cuja interse¸c˜ao ´e o grupo Aut(A
n
).
Vamos supor que n seja par, no entanto, se n for ´ımpar o m´etodo ´e o mesmo,
s´o as permuta¸c˜oes ser˜ao diferentes. Sejam ent˜ao as seguintes permuta¸c˜oes:
g
1
=
α
1
(1, 2, ..., n)
α
2
(n + 1, ..., 2n)
α
3
(2n + 1, ..., 3n)
α
4
(3n + 1, ..., 4n)
α
5
(4n + 1, ..., 5n),
g
2
=
β
1
(1, n)(2, n − 1)...(n/2, n/2)
β
2
(n + 1, 2n)(n + 2, 2n − 1)...(n + n/2, 2n − n/2)
β
3
(2n + 1, 3n)(2n + 2, 3n − 1)...(2n + n/2, 3n − n/2)
β
4
(3n + 1, 4n)(3n + 2, 4n − 1)...(3n + n/2, 4n − n/2)
β
5
(4n + 1, 5n)(4n + 2, 5n − 1)...(4n + n/2, 5n − n/2) .
Notemos que o grupo α
1
, β
1
´e isomorfo ao grupo diedral. De fato, (α
1
)
n
=
(β
1
)
2
= e. Al´em disso, verifica-se que α
1
β
1
= β
1
(α
1
)
−1
.
Da mesma forma, os grupos α
2
, β
2
, α
3
, β
3
, α
4
, β
4
e α
5
, β
5
s˜ao isomorfos
a grupos diedrais. Neste caso, podemos afirmar que o grupo D = g
1
, g
2
´e isomorfo
ao grupo diedral.
Afirmamos que D < T , pois g
1
e g
2
levam arestas em arestas e n˜ao-arestas
para n˜ao-arestas (n˜ao estamos movendo as n˜ao-arestas).
Note tamb´em que g
2
/∈ S
3n
. Para estar em S
3n
, a permuta¸c˜ao tem que ser
feita nos v´ertices. Uma permuta¸c˜ao de v´ertices inverte a diagonal gerando uma
permuta¸c˜ao diferente de g
2
, pois envolve tamb´em n˜ao-arestas. A permuta¸c˜ao g
2
foi
constru´ıda fazendo permuta¸c˜oes de arestas sem compromisso com as permuta¸c˜oes
de v´ertices.
Agora, renomearemos os v´ertices de A
n
usando a mesma l´ogica empregada
61
para as arestas. Os v´ertices a
0
, a
1
, . . . , a
n−1
ser˜ao representados por 1, 2, . . . , n,
respectivamente. Prosseguindo, os v´ertices b
0
, b
1
, . . . , b
n−1
ser˜ao representados por
n + 1, n + 2, . . . , 2n, respectivamente. Finalmente, os v´ertices c
0
, c
1
, . . . , c
n−1
ser˜ao
representados por 2n + 1, 2n + 2, . . . , 3n, respectivamente.
Nessa nova representa¸c˜ao, definiremos as seguintes permuta¸c˜oes de S
3n
,
h
1
= (1, 2, ..., n)(n + 1, ..., 2n)(2n + 1, ..., 3n)
h
2
= (2, n)(3, n − 1)...(n/2, n/2)(n + 1, 3n)(n + 2, 3n − 1)...(n + n/2, 3n − n/2)
Note que h
1
, h
2
´e isomorfo ao grupo diedral nessa nova representa¸c˜ao. De
fato, (h
1
)
n
= (h
2
)
2
= e. Verifica-se tamb´em que
h
1
h
2
= h
2
h
−1
1
(6.4)
Podemos ver isso geometricamente, ou seja, no lado esquerdo da equa¸c˜ao 6.4, temos
uma reflex˜ao seguida por uma rota¸c˜ao normal, enquanto no lado direito da equa¸c˜ao
temos uma rota¸c˜ao inversa seguida por uma reflex˜ao.
No isomorfismo que leva S
3n
em S
3n
, ´e f´acil ver que h
1
´e levado em g
1
(descrito
no in´ıcio do exemplo).
A permuta¸c˜ao h
2
ser´a levada pelo isomorfismo de S
3n
em S
3n
para uma
permuta¸c˜ao g
2
∈ S
3n
. Portanto, o grupo D
= g
1
, g
2
(D
< S
3n
) ser´a isomorfo
ao grupo diedral nessa nova representa¸c˜ao, ou seja, D
´e um grupo sol´uvel. A
permuta¸c˜ao g
2
´e dada por
g
2
= (1, n)(2, n − 1)...(n/2, n/2)
(n + 1, 5n)(n + 2, 5n − 1)...(2n, 4n + 1)
(2n + 1, 3n)(2n + 2, 3n − 1)...(2n + n/2, 3n − n/2)
(3n + 1, 6n)(3n + 2, 6n − 1)...(4n, 5n + 1)
Portanto, exibimos D e D
numa representa¸c˜ao compat´ıvel. Esses grupos s˜ao
62
grupos sol´uveis e s˜ao subgrupos de T e S
3n
, respectivamente. No entanto, o grupo
diedral n˜ao possui subgrupo comutador suavemente sol´uvel, como exige o Corol´ario
5. De fato, o subgrupo comutador do grupo diedral ´e ρ
2
, onde ρ representa uma
rota¸c˜ao, como descrito na Defini¸c˜ao 9. Tal subgrupo possui s´erie derivada limitada
por uma constante, no entanto, o grupo quociente ρ
2
n˜ao ´e suavemente abeliano,
pois n˜ao pode ser expresso como produto direto de um subgrupo cujo expoente ´e
limitado por uma constante e um subgrup o de tamanho polilogar´ıtmico na ordem
do grupo. Logo, n˜ao podemos aplicar o m´etodo descrito pelo Corol´ario 5.
63
Cap´ıtulo 7
Conclus˜ao
Este trabalho teve como objetivo principal a aplica¸c˜ao das ferramentas da
Computa¸c˜ao Quˆantica e da Teoria de Grupos ao Problema do Isomorfismo de
Grafos.
Mostramos neste trabalho uma breve revis˜ao sobre Teoria de Grupos. Em
seguida, apresentamos alguns conceitos b´asicos sobre a Teoria de Grafos necess´arios
para descrever o Problema do Isomorfismo de Grafos. Tamb´em foram apresentados
conceitos da Mecˆanica Quˆantica. Apresentamos o Problema do Subgrupo Oculto
(PSO) e mostramos (omitindo alguns detalhes) o algoritmo quˆantico padr˜ao para
a solu¸c˜ao do PSO em grupos abelianos.
Mostramos que o Problema do Isomorfismo de Grafos ´e um PSO sobre o
grupo sim´etrico S
n
, ou seja, uma solu¸c˜ao eficiente do PSO no grupo sim´etrico
S
n
implicar´a num algoritmo de tempo polinomial para decidir se dois grafos s˜ao
isomorfos ou n˜ao.
Utilizamos uma redu¸c˜ao do Problema do Isomorfismo de Grafos para o Pro-
blema de Interse¸c˜ao de Grupos, que juntamente com resultados da Computa¸c˜ao
Quˆantica nos permitiu obter um algoritmo quˆantico eficiente para uma classe par-
ticular de grafos, que infelizmente ´e bastante restrita. No entanto, um dos objetivos
desta disserta¸c˜ao foi determinar, dado o est´agio atual de desenvolvimento da Com-
puta¸c˜ao Quˆantica, se existem algoritmos quˆanticos eficientes para muitas classes
de grafos ou n˜ao. Nossa conclus˜ao ´e que a contribui¸c˜ao da Computa¸c˜ao Quˆantica
64
´e bastante restrita ainda, pois as duas estrat´egias adotadas: redu¸c˜ao do Problema
do Isomorfismo de Grafos para o PSO e uso do Problema de Interse¸c˜ao de Grupos,
juntamente com resultados da Computa¸c˜ao Quˆantica n˜ao produzem resultados
significativos.
Como proposta para trabalhos futuros, procuraremos usar o conhecimento
adquirido em Computa¸c˜ao Quˆantica e Teoria de Grafos para dar mais exemplos
onde essa segunda estrat´egia funcione, e tamb´em analisar poss´ıveis generaliza¸c˜oes
de algoritmos quˆanticos para relaxar as restri¸c˜oes impostas a este m´etodo.
65
Referˆencias Bibliogr´aficas
L. Von Ahn. Survey: Quantum computation and the hidden subgroup problem.
Relat´orio t´ecnico, Dept. of Science Computer, Carnegie Mellon University, Pitts-
burgh, 2002.
A. V. Aho, J. E. Hopcroft, e J. D. Ullman. The design and analysis of com-
puter algorithms. Addison-Wesley Series in Computer Science and Informa-
tion Processing, Reading, MA: Addison-Wesley, 1974.
G. L. Alexanderson. About the cover: Euler and K
¨
onigsberg’s Bridges: A historical
view. In: Bull. Amer. Math. Soc. 43, p´aginas 567–573, 2006.
L. Babai. On the complexity of canonical labeling of strongly regular graphs.
SIAM J. Comput., 9(1):212–216, 1980.
L. Babai e E. M. Luks. Canonical labeling of graphs. In: STOC ’83: Proceedings
of the fifteenth annual ACM symposium on Theory of computing,
p´aginas 171–183, New York, NY, USA, 1983. ACM. ISBN 0-89791-099-0.
L. Babai e E. Szemer´edi. On the complexity of matrix group problems i. In
Proc. of the 25th IEEE Symposium on Foudation of Computer Science,
p´aginas 229–240, 1984.
R. Beals. Quantum computation of Fourier transforms over symmetric groups. In:
Proc. 29th ACM Symp. on Theory of Computing, p´aginas 48–53, New
York, 1997. ACM.
H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic
index on partial k-trees. J. Algorithms, 11(4):631–643, 1990.
66
O. Cogis e O. Guinaldo. Linear descriptor for conceptual graphs and a class for
polynomial isomorphism test. In: Proceedings of the 3rd International
Conference on Conceptual Structures, ICCS’95, p´aginas 263–277, Santa
Cruz, CA, USA, August 1995., 1995. Lecture Notes in AI 954, Springer-Verlag.
C. J. Colbourn. On testing isomorphism of permutation graphs. Networks, 11:
13–21, 1981.
C. M. M. Cosme. Algoritmos Quˆanticos para o Problema do Subgrupo
Oculto N˜ao Abeliano. Tese de Doutorado, Laborat´orio Nacional de Com-
puta¸c˜ao Cient´ıfica - LNCC, 2008. A ser defendida.
C. M. M. Cosme e R. Portugal. Quantum algorithms for the hidden subgroup pro-
blem on a class of semidirect product groups. ArXiv:quant-ph/0703223v2,
2007.
I. Damgard. Qip note: On the quantum fourier transform and aplications. Re-
lat´orio t´ecnico, Computer Science Department of Aarhus University., 2004.
J. F. F. de Abreu. Computa¸c˜ao quˆantica em sistemas abertos e uma aplica¸c˜ao ao
modelo biol´ogico de fr
¨
ohlich. Disserta¸c˜ao de Mestrado, Lab orat´orio Nacional de
Computa¸c˜ao Cient´ıfica - LNCC, 2004.
C. M. H. de Figueiredo, J. Meidanis, e C. P. de Mello. A linear-time algorithm for
proper interval graph recognition. Inf. Process. Lett., 56(3):179–184, 1995.
ISSN 0020-0190.
D. Deutsch. Quantum theory, the Church-Turing principle and the universal quan-
tum computer. Proceedings of the Royal Society of London Ser. A, A400:
97–117, 1985.
M. Ettinger e P. Høyer. A quantum observable for the graph isomorphism problem.
ArXiv:quant-ph/9901029, 1999.
67
L. Euler. Solutio problematis ad geometriam situs pertinentis. In: Commentarii
Academiae Scientiarum Imperialis Petropolitanae 8, 128-140/Opera
Omnia (1), Vol. 7, 1-10, 1741.
S. A. Fenner e Y. Zhang. Quantum algorithms for a set of group theoretic problems.
In: ICTCS, p´aginas 215–227, 2005.
T. D. Fernandes. Problema do subgrupo o culto em grupos nilpotentes de classe
2. Disserta¸c˜ao de Mestrado, Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica -
LNCC, 2008. A ser defendida.
R. Feynman. Simulating physics with computers. International Journal of
Theoretical Physics, 21(6&7):467–488, 1982.
S. Fortin. The graph isomorphism problem. Relat´orio T´ecnico 96-20, University
of Alberta, Edmonton, Alberta, Canada., 1996.
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, e P. Sen. Hidden translation and
orbit coset in quantum computing. In: Proceedings of 35th ACM Sympo-
sium on Theory of Computing, p´aginas 1–9, 2003.
R. Frucht. Herstellung von graphen mit vorgegebener abstrakter gruppe. Com-
positio Mathematica, 6:239–250, 1939.
R. Frucht. Graphs of degree three with a given abstract group. Canad. J. Math.,
1:365–378, 1949.
H. H. Gan, S. Pasquali, e T. Schlick. Exploring the repertoire of RNA secondary
motifs using graph theory; implications for RNA design. Nucleic Acids Res,
31(11):2926–2943, June 2003. ISSN 1362-4962.
A. Garcia e Y. Lequain. Elementos de
´
Algebra. IMPA, Rio de Janeiro, 2001.
D. N. Gon¸calves. Transformada de fourier quˆantica no grupo diedral. Disserta¸c˜ao
de Mestrado, Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica - LNCC, 2005.
68
S. Hallgren, A. Russell, e A. Ta-Shma. Normal subgroup reconstruction and quan-
tum computing using group representations. In: Proc. 32nd ACM Symp. on
Theory of Computing, p´aginas 627–635. ACM, 2000.
F. Harary. Graph Theory. Addison-Wesley, Reading, Massachusetts, 1969.
F. Harary e E.M. Palmer. The smallest graph whose group is cyclic. Czech.
Math. J., 16/22:70–71/180, 1966/1972.
I.N. Herstein. Abstract Algebra. Macmillan Publishing Company, New York,
1986.
C. M. Hoffman. Group-Theoretic Algorithms and Graph Isomorphism,
volume 136 of Lecture Notes in Computer Science. Springer-Verlag, Berlin,
1979.
J. E. Hopcroft e J. K. Wong. Linear time algorithm for isomorphism of planar
graphs (preliminary report). In: STOC ’74: Proceedings of the sixth
annual ACM symposium on Theory of computing, p´aginas 172–184, New
York, NY, USA, 1974. ACM.
Wen-Lian Hsu. O(m.n) algorithms for the recognition and isomorphism problems
on circular-arc graphs. SIAM J. Comput., 24(3):411–439, 1995. ISSN 0097-
5397.
Y. Inui e F. Le Gall. An efficient quantum algorithm for the hidden subgroup
problem over a class of semi-direct product groups. Quantum Information
and Computation (to apear) or ArXiv:quant-ph/0412033v2, 2005.
G. Ivanyos, F. Magniez, e M. Santha. Efficient quantum algorithms for some
instances of the non-abelian hidden subgroup problem. International Journal
of Foundations of Computer Science, 14(5):723–739, 2003.
G. Ivanyos, L. Sanselme, e M. Santha. An efficient quantum algorithm for the
69
hidden subgroup problem in extraspecial groups. In: Proc. of STACS’07,
2007a.
G. Ivanyos, L. Sanselme, e M. Santha. An efficient quantum algorithm for the hid-
den subgroup problem in nil-2 groups. arXiv:quant-ph/0707.1260v1, 2007b.
R. Jozsa. Quantum factoring, discrete logarithms and the hidden subgroup pro-
blem. ArXiv:quant-ph/0012084, 2000.
P. Kaye, R. Laflamme, e M. Mosca. An Introduction to Quantum Com-
puting. Oxford University Press, Inc., New York, NY, USA, 2007. ISBN
0198570007.
A. Kitaev. Quantum measurements and the abelian stabilizer problem. Electronic
Colloquium on Computational Complexity (ECCC), 3(3), 1996.
J. K
¨
obler, U. Sch
¨
oning, e J. Tor´an. The graph isomorphism problem: its
structural complexity. Birkh
¨
auser Verlag, Basel, Switzerland, 1993. ISBN
0-8176-3680-3.
N. Koblitz. Algebraic aspects of cryptography, volume 3 of Algorithms
And Computation In Mathematics. Springer-Verlag, Berlin; New York,
1998. ISBN 3-540-63446-0.
G. Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden
subgroup problem. SIAM Journal on Computing, 30(1):170–188, 2005.
C. Lavor, L.R.U. Manssur, e R. Portugal. Shor’s algorithm for factoring large
integers. ArXiv:quant-ph/0303175, 2003.
X. Liu e D. J. Klein. The graph isomorphism problem. Journal of Computa-
tional Chemistry, 12(10):1243–1251, 1991.
C. Lomont. The hidden subgroup problem - review and open problems.
ArXiv:quant-ph/0411037, 2004.
70
G. S. Lueker e K. S. Booth. A linear time algorithm for deciding interval graph
isomorphism. J. ACM, 26(2):183–195, 1979. ISSN 0004-5411.
E. M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial
time. J. Comput. Syst. Sci., 25(1):42–65, 1982.
F. L. Marquezino. A Transformada de Fourier Quˆantica Aproximada e sua Simu-
la¸c˜ao. Disserta¸c˜ao de Mestrado, Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica
- LNCC, 2006.
R. Mathon. A note on the graph isomorphism counting problem. Inf. Process.
Lett., 8(3):131–132, 1979.
B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:
45–87, 1981.
B. D. McKay. nauty user’s guide (version 1.5). Relat´orio T´ecnico TR-CS-90-02,
Australian National University, Department of Computer Science, 1990.
M. Mosca e A. Ekert. The hidden subgroup problem and eigenvalue estimation on a
quantum computer. In: Proc. of the 1st NASA International Conference
on Quantum Computing and Quantum Communication, number 1509,
Palm Springs, 1999. Lecture Notes in Computer Science.
M. A. Nielsen e I. L. Chuang. Quantum computation and quantum in-
formation. Cambridge University Press, New York, NY, USA, 2000. ISBN
0-521-63503-9.
C. M. Papadimitriou. Computational complexity. Addison-Wesley, Reading,
Massachusetts, 1994. ISBN 0201530821.
J.W. Raymond e P. Willett. Maximum common subgraph isomorphism algorithms
for the matching of chemical structures. Journal of Computer-Aided Mo-
lecular Design, 16(7):521–533, July 2002.
71
O. Regev. Quantum computation and lattice problems. In: FOCS ’02: Pro-
ceedings of the 43rd Symposium on Foundations of Computer Science,
p´aginas 520–529, Washington, DC, USA, 2002. IEEE Computer Society. ISBN
0-7695-1822-2.
O. Regev. A subexponential time algorithm for the dihedral hidden subgroup
problem with polynomial space. ArXiv:quant-ph/0406151v1, 2004.
Jean-Pierre Serre. Linear Representations of Finite Groups. Number 42 in
Graduate Texts in Mathematics. Springer-Verlag, New York, 1977.
P. W. Shor. Algorithms for quantum computation: Discrete logarithms and fac-
toring. In: IEEE Symposium on Foundations of Computer Science,
p´aginas 124–134, 1994.
P. W. Shor. Polynomial-time algorithms for prime factorization and discrete lo-
garithms on a quantum computer. SIAM Journal on Computing, 26(5):
1484–1509, 1997.
D. R. Simon. On the power of quantum computation. In: Proceedings of
the 35th Annual Symp osium on Foundations of Computer Science,
p´aginas 116–123, Los Alamitos, CA, 1994. Institute of Electrical and Electronic
Engineers Computer Society Press.
D. R. Simon. On the power of quantum computation. SIAM J. Comput., 26
(5):1474–1483, 1997. ISSN 0097-5397.
J. L. Szwarcfiter. Grafos e Algoritmos Computacionais. Editora Campus,
Rio de Janeiro, 1984.
G. Valiente. Algorithms on Trees and Graphs. Springer-Verlag New York,
Inc., Secaucus, NJ, USA, 2002. ISBN 3540435506.
J. Watrous. Quantum algorithms for solvable groups. In: STOC, p´aginas 60–67,
2001.
72
V. N. Zemlyachenko, N. M. Kornienko, e R. I. Tyshkevich. Graph isomorphism
problem. Journal of Mathematical Sciences, 29(4):1426–1481, 1985.
73
Apˆendice A
Os Postulados da Mecˆanica Quˆantica
Aqui descrevemos os quatro postulados fundamentais da Mecˆanica Quˆantica
[Nielsen e Chuang (2000)]. O primeiro postulado trata da descri¸c˜ao matem´atica
de um sistema quˆantico isolado.
Postulado 1 A qualquer sistema f´ısico isolado existe associado um espa¸co vetorial
complexo com produto interno (ou seja, um espa¸co de Hilbert), conhecido como
espa¸co de estados do sistema. O sistema ´e completamente descrito pelo seu vetor
de estado, um vetor unit´ario no espa¸co de estados.
O segundo postulado trata da evolu¸c˜ao dos sistemas f´ısicos quˆanticos.
Postulado 2 A evolu¸c˜ao de um sistema quˆantico fechado ´e descrita por uma
transforma¸c˜ao unit´aria. Ou seja, o estado |ψ
0
de um sistema em um tempo t
0
est´a relacionado ao estado |ψ
f
do sistema em t
f
por um operador unit´ario U que
depende somente de t
0
e t
f
:
|ψ
f
= U |ψ
0
. (A.1)
O terceiro postulado descreve a forma como pode-se extrair informa¸c˜oes de
um sistema quˆantico atrav´es de medi¸c˜oes.
Postulado 3 As medidas quˆanticas s˜ao descritas por determinados operadores de
medida {M
m
}. Esses operadores atuam sobre o espa¸co de estados do sistema. O
´ındice m se refere aos poss´ıveis resultados da medida. Se o estado de um sistema for
74
|ψ, imediatamente antes da medida, a probabilidade de um resultado m ocorrer
´e dada por:
p(m) = ψ|M
†
m
M
m
|ψ, (A.2)
e o estado do sistema ap´os a medida ser´a:
M
m
|ψ
ψ|M
†
m
M
m
|ψ
. (A.3)
Os operadores de medida satisfazem a rela¸c˜ao de completitude:
m
M
†
m
M
m
= I. (A.4)
Por ´ultimo, o quarto postulado descreve a forma como sistemas quˆanticos
diferentes podem ser combinados.
Postulado 4 O espa¸co de estados de um sistema f´ısico composto ´e o produto
tensorial dos espa¸cos de estados dos sistemas f´ısicos individuais. Se os sistemas
forem numerados de 1 at´e n, e o sistema i for preparado no estado |ψ
i
, decorre
que o estado do sistema composto ser´a |ψ
1
⊗ |ψ
2
⊗ ... ⊗ |ψ
n
.
75
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
