WECIQ 2006 - Mini-curso 4
Algoritmos Quânticos
Renato Portugal1 , Carlos Magno Martins Cosme, Demerson Nunes Gonçalves1
1
Laboratório Nacional de Computação Científica
Petrópolis, RJ, Brasil
{portugal,magno,dnunes}@lncc.br
1. Introdução
A capacidade de se ter dados computacionais em estado de superposição e de podermos
manipulá-los através de operações unitárias é o diferencial da computação quântica em
relação a convencional. São as leis da mecânica quântica que tornam isso possível. Duas
tarefas devem ser realizadas para fazer uso dessas novas características na computação:
(1) construir um hardware que manipule estados quânticos, (2) desenvolver algoritmos
baseados na lógica quântica. Esse trabalho visa apresentar de forma didática uma parte
da área de algoritmos quânticos.
Atualmente existem três grandes vertentes na área de algoritmos quânticos, que
podem ser caraterizadas como (1) o problema do subgrupo escondido, que inclui o algoritmo de Shor como caso particular, (2) problemas de busca e otimização, que inclui o
algoritmo de Grover e (3) algoritmos baseados em caminhos aleatórios quânticos. Nesse
trabalho vamos nos concentrar na vertente (1).
O problema do subgrupo escondido surgiu quando os pesquisadores notaram que
os algoritmos de Shor, Simon e Deutsch&Josza eram todos casos particulares de um problema mais geral cuja terminologia mais adequada era usando a teoria de grupo computacional. De forma resumida, o problema consiste em achar os geradores de um subgrupo
H do grupo G. O grupo G é conhecido através de geradores e o subgrupo H pode ser
obtido a partir de uma função f que é constante nas classes laterais de H em G. O problema tem uma solução eficiente se conseguirmos achar os geradores de H de forma que
(1) o número de passos, (2) uso de memória e (3) número de vezes que f foi usada têm
complexidade computacional O(poly(log⌈G⌉)).
Nesse trabalho apresentamos uma breve revisão das portas quânticas mais usadas,
supondo que o leitor já tem um conhecimento prévio dos conceitos básicos de computação
quântica. A seguir descrevemos o algoritmo quântico para calcular o transformada de
Fourier e baseado nessa transformada, descrevemos os diversos algoritmos quânticos para
cálculo de ordem como o algoritmo de Shor, Kitaev e Watrous. O algoritmo de Kitaev é
apresentado como uma aplicação do algoritmo para cálculo de fase de um autovalor de um
operador unitário. Depois descrevemos o algoritmo para decompor grupos abelianos desenvolvido por Cheung&Mosca. Por falta de espaço, não podemos apresentar os detalhes
do problema do subgrupo escondido não abeliano.
2. Portas Principais
A porta X é a versão quântica da porta NOT clássica. O circuito dessa porta está mostrado
na figura 1, que deve ser lido da esquerda para a direita. A entrada é o estado |j1 i onde j1
assume o valor 0 ou 1, ou seja, o qubit está escrito na base binária. A saída é X |j1 i.
67
|j1 i
X
X |j1 i
Figura 1. Circuito da porta X.
A matriz X é unitária dada por
X=
0 1
1 0
.
Assim se a entrada é |0i, a saída é |1i e vice-versa. Esse é um exemplo de um circuito
com um único qubit. Vamos agora ver um exemplo com 2 qubits.
A porta CNOT é uma das principais portas usadas em algoritmos. Vamos descrevêla em detalhes, pois ela serve como paradigma para o entendimento de outras portas quânticas. O circuito dessa porta está mostrado na figura 2.
|j1 i
|j2 i
•
|j1 i
X j1 |j2 i
Figura 2. Circuito da porta CNOT.
Como sempre, o circuito deve ser lido da esquerda para a direita. A entrada é
o estado |j1 i |j2 i onde j1 e j2 podem assumir os valores 0 ou 1. A saída é |0i |j2 i se
j1 = 0 ou |1i (X |j2 i) se j1 = 1. Se a entrada do primeiro qubit for um estado da
base computacional e a entrada do segundo for |0i, a porta CNOT pode ser interpretada
como uma replicadora, pois a entrada |j1 i |0i gera a saída |j1 i |j1 i. Isso não pode ser
generalizado a menos que o teorema da não-clonagem seja violado. Esse teorema afirma
simplesmente que a produção de cópias de um estado quântico desconhecido é proibida
e a prova é uma simples constatação de que a cópia de estados quânticos é uma operação
não-unitária no caso geral. Foi possível fazer cópias no caso acima, porque os estados
envolvidos eram ortogonais.
A figura 2 nos dá a impressão que a saída da porta CNOT é sempre desemaranhada. Isso é falso. Na figura 3 podemos ver um exemplo em que a saída é emaranhada.
|0i+|1i
√
2
|0i
•
Figura 3. Porta CNOT gerando uma saída emaranhada.
Portas que emaranham podem desemaranhar e vice-versa. Isso segue do fato de
que todo operador unitário tem inversa. A porta inversa, isto é, a porta que representa o
operador inverso faz o papel inverso, como é de se esperar.
A porta CNOT é um caso particular de porta controlada. Na verdade o nome
CNOT vem de ‘Controlled NOT’. O qubit com a bolinha preta é o controle que só é
ativado se o estado do qubit for |1i, e o outro qubit é o alvo. No caso do CNOT, o
operador que é aplicado ao alvo é X, porém podemos substituí-lo por qualquer outro
operador unitário de 1 qubit. A notação C(X) é sinônimo de CNOT e pode ser usada
para outros operadores.
68
1
1
A porta H =
1 −1
ser descrita da seguinte forma
√1
2
tem também papel de destaque. A sua atuação pode
H |j1 i =
|0i + (−1)j1 |1i
√
.
2
(1)
A porta H é muito usada em algoritmos para criar um estado de superposição de todos os
vetores da base computacional. Esse estado é útil no paralelismo quântico. A forma usual
de gerar esse estado é aplicar H ⊗n no estado |0i⊗n :
n
(H |0i)
⊗n
2 −1
1 X
|ji .
=√
2n j=0
(2)
Note que nessa equação, o lado direito usa a notação decimal. Por exemplo, o estado
|2n − 1i corresponde ao estado |1i⊗n . Todo esse processo deve se feito num computador
quântico de n qubits.
E XERCÍCIO 2.1 Mostre como a equação (2) pode ser obtida a partir da equação (1).
E XERCÍCIO 2.2 Dado um operador unitário U de n qubits podemos definir um operador
controlado muito útil em algoritmos da seguinte forma
V (|ji |ψi) = |ji U j |ψi ,
(3)
onde o primeiro registrador tem m qubits e o segundo tem n qubits. No circuito abaixo
vemos sua representação esquemática.
|ji /m •
|ji
|ψi /n U
U j |ψi
Esse operador pode ser visto como uma porta C(U ) generalizada. A representação gráfica
é a mesma de C(U ), porém não há perigo de confusão pois o primeiro registrador tem
mais do que 1 qubit. Mostre que V é um operador unitário e mostre que o circuito abaixo
é a sua implementação correta em termos de portas controladas usuais, ou seja, cada uma
controlada por um qubit apenas.
···
|j1 i
•
..
.
..
.
•
|jm−2 i
•
|jm−1 i
|jm i
|ψi
|j1 i
•
/n U 20
1
U2
2
U2
69
···
|jm−2 i
···
|jm−1 i
···
|jm i
···
m−1
U2
U j |ψi
3. A Transformada de Fourier Quântica
A transformada de Fourier de uma função F : {0, . . . , N − 1} → C é uma nova função
F̃ : {0, . . . , N − 1} → C definida por
onde
N −1
1 X jk
ωN F (k),
F̃ (j) = √
N k=0
(4)
2πi
ωN = e N .
(5)
N
O termo ωN é chamado de N −ésima raiz da unidade pois (ωN ) = 1. Omitiremos o
sub-índice N quando for possível determiná-lo pelo contexto.
Podemos aplicar a transformada de Fourier tanto em uma função quanto em um
estado da base computacional. A transformada de Fourier aplicada ao estado |ji da base
computacional é
N −1
1 X jk
ω |ki ,
(6)
|ψj i ≡ TFN (|ji) = √
N k=0
onde o conjunto {|ψj i ; j = 0, . . . , N − 1} forma uma nova base ortonormal. A transformada de Fourier é um operador linear unitário, portanto se soubermos como ele atua nos
estados da base computacional, podemos obter sua atuação num estado genérico do tipo
|ψi =
N
−1
X
a=0
F (a) |ai .
(7)
A transformada de Fourier de |ψi pode ser obtida tanto através da equação (4) como da
equação (6). No primeiro caso calculamos a transformada de Fourier das amplitudes sem
mexer nos vetores e no segundo caso calculamos a transformada de Fourier dos vetores
sem mexer nas amplitudes. Os dois métodos são equivalentes.
E XERCÍCIO 3.1 Prove a identidade
N −1
1 X jk
1 se j é um múltiplo de N
ω =
0 caso contrário,
N k=0
(8)
usando a fórmula da progressão geométrica. A partir desse resultado prove que {|ψj i ; j =
0, . . . , N − 1} é uma base ortonormal.
E XERCÍCIO 3.2 Mostre que a transformada de Fourier de |ψi dado pela equação (7) pode
ser calculada tanto através da equação (4) como da equação (6).
Usando a identidade (8), podemos definir a transformada de Fourier inversa, que
†
é similar a (6), porém com um sinal de menos no expoente. Note que TF−1
N =TFN , já que
TFN é um operador unitário.
É um fato notável que a expressão (6) pode ser fatorada da seguinte forma
n
1 Y
l
|0i + e2πij/2 |1i
TFN (|ji) = √
2n l=1
!
!
!
j
j
j
|0i + e2πi 22 |1i
|0i + e2πi 2n |1i
|0i + e2πi 2 |1i
√
√
√
⊗
⊗. . .⊗
. (9)
=
2
2
2
70
E XERCÍCIO 3.3 Mostre que a expressão (6) é equivalente a (9). Sugestão: use a equação
(5) e faça a decomposição binária de k.
j
j
j
E XERCÍCIO 3.4 Mostre que as expressões exponenciais e2πi 2 , e2πi 22 , · · · , e2πi 2n que
aparecem na equação (9) são equivalentes a e2πi(0.j4 ) , e2πi(0.j3 j4 ) , · · · , e2πi(0.j1 ···jn ) , onde a
fração binária 0.j1 · · · jn é definida como
0.j1 · · · jn =
n
X
jk
.
k
2
k=1
Na figura 4 apresentamos um cicuito quântico que executa a transformada de
Fourier em 4 qubits. A partir desse circuito podemos facilmente generalizá-lo para mais
qubits desde que N seja da forma 2n onde n é o número de qubits. Se N não é uma potência de 2, não é conhecido um circuito exato para o cálculo da transformada de Fourier.
|j1 i
|j2 i
H
R(2)
R(3)
•
H
•
|j3 i
R(2)
R(3)
•
H
•
|j4 i
R(2)
•
•
H
j
√1 (|0i
2
+ e2πi 2 |1i)
×
√1 (|0i
2
+e
×
√1 (|0i
2
+e
×
R(4)
√1 (|0i
2
×
2πi j2
2
2πi j3
+
2
2πi j4
2
e
|1i)
|1i)
|1i)
Figura 4. Circuito da transformada de Fourier sobre 4 qubits. A entrada é o estado |ji que é equivalente a |j1 j2 j3 j4 i.
Vamos agora descrever as portas usadas no circuito. Vamos começar pelas mais
simples. A duas últimas portas são chamadas de SWAP. Elas invertem o estado dos qubits.
A figura 5 mostra como essa porta funciona e também descreve a sua decomposição em
termos de portas universais (CNOT e portas de 1 qubit).
|ψi
×
|ϕi
|ϕi
×
|ψi
≡
•
|ψi
|ϕi
•
•
|ϕi
|ψi
Figura 5. Circuito da porta SWAP. Esta porta inverte os estados dos qubits.
E XERCÍCIO 3.5 Mostre que a decomposição da porta SWAP mostrada na figura 5 funciona corretamente. Sugestão: mostre que a decomposição funciona corretamente para a
base computacional e conclua que ela é válida para vetores genéricos.
O operador R(k) é definido por
R
(k)
=
1 0
2πi
0 e 2k
.
No circuito da transfomada de Fourier ele aparece sempre controlado por outro qubit.
Uma vez que R(k) é sempre aplicado depois de uma porta Hadamard, é crucial que
saibamos o resultado da aplicação de R(k) controlado por um qubit |jl i sobre estados
do tipo (1). Isso é deixado como exercício, que mostra que o circuito 4 calcula a transformada de Fourier corretamente.
71
E XERCÍCIO 3.6 Mostre que
j
1
H |j4 i = √ (|0i + e2πi 2 |1i)
2
j
1
(2)
R4 H |j3 i = √ (|0i + e2πi 22 |1i)
2
j
1
(3) (2)
R4 R3 H |j2 i = √ (|0i + e2πi 23 |1i)
2
j
1
(4) (3) (2)
R4 R3 R2 H |j1 i = √ (|0i + e2πi 24 |1i)
2
onde o sub-índice do operador R(k) indica por qual qubit ele está sendo controlado. Sugestão: use a expressão j = j1 23 + j2 22 + j3 2 + j4 e note que alguns termos dessa soma
desaparecem quando estão no expoente.
Uma vez que vamos usar o circuito que calcula a transformada de Fourier outras
vezes, vamos descrevê-lo de uma forma mais sucinta. A figura 6 descreve o algoritmo
como uma caixa preta. A saída correspondente a um vetor genérico da base computacional está mostrada. Assim podemos obter a saída correspondente a um vetor em superposição usando linearidade.
˛ 2πi 0.j ¸
˛e
n
|j1 i
|j2 i
.
.
.
|jn i
TFN
˛ 2πi 0.j
¸
˛e
n−1 jn
.
.
.
˛ 2πi 0.j ···j ¸
˛e
n
1
˛
¸
Figura 6. Circuito compacto da transformada de Fourier. Os vetores do tipo ˛e2πi 0.jn descrevem de
√
forma compacta vetores do tipo (|0i + e2πi 0.jn |1i)/ 2.
4. Algoritmo de Shor
O algoritmo de Shor acha os fatores primos de um número composto N . A fatoração pode
ser reduzida ao cálculo da ordem de um número x menor que N escolhido aleatoriamente.
O número de qubits necessário para armazenar N é muito menor que N . Esse número é
log2 N , porém como ele não é um inteiro no caso geral, definimos
n = ⌈log2 N ⌉.
Um computador quântico com n qubits pode guardar N ou qualquer outro inteiro positivo
menor que N . Facilmente vemos que o número de fatores primos de N é no máximo n.
Se o número de qubits e o número de fatores primos são menores ou iguais que n, então
é natural perguntar se existe um algoritmo que fatora N em um número de passos que é
polinomial em n. Mais precisamente a questão é: Existe um algoritmo de fatoração na
classe de complexidade P?
A redução da fatoração de N ao problema de achar a ordem de um inteiro x menor
que N pode ser descrita da seguinte forma. Se x e N possuem fatores comuns, então o
72
MDC(x, N ) fornece um fator de N , portanto é suficiente investigar o caso quando x é
coprimo com N . A ordem de x módulo N é o menor inteiro positivo r tal que
xr ≡ 1
mod N.
Se r for par, podemos definir y como sendo
xr/2 ≡ y
mod N.
A notação acima significa que y é o resto da divisãode xr/2 por N e, pela definição,
0 ≤ y < N . Note que y satisfaz y 2 ≡ 1 módulo N , ou equivalentemente (y − 1)(y + 1) ≡
0 módulo N , o que significa que N divide (y − 1)(y + 1). Se 1 < y < N − 1, os
fatores y − 1 e y + 1 satisfazem 0 < y − 1 < y + 1 < N , portanto N não pode dividir
y − 1 nem y + 1 separadamente. A única alternativa é que ambos y − 1 e y + 1 tenham
fatores de N (que resulta N por multiplicação). Então, MDC(y − 1, N ) e MDC(y + 1, N )
produzem fatores não triviais de N . Se N tiver mais fatores, eles podem ser calculados
aplicando o algoritmo recursivamente. Considere N = 21 como exemplo. A sequência
de equivalências
24 ≡ 16 mod 21
25 ≡ 11 mod 21
26 ≡ 11 × 2 ≡ 1 mod 21
mostra que a ordem de 2 módulo 21 é r = 6. Portanto, y ≡ 23 ≡ 8 módulo 21. De
y − 1 resulta o fator 7 e de y + 1 resulta o fator 3 de 21. Resumindo, se escolhermos
aleatoriamente um inteiro positivo x menor que N e calcularmos o MDC(x, N ), ou teremos um fator de N ou ficaremos sabendo que x é coprimo com N . Neste último caso,
se x satisfizer as condições (1) a ordem r é par, e (2) 0 < y − 1 < y + 1 < N , então o
MDC(y − 1, N ) e MDC(y + 1, N ) produzem fatores de N . Se uma das condições não é
verdadeira, nós recomeçamos até achar um candidato x apropriado. O método não seria
útil se estas suposições fossem restritivas demais, mas felizmente este não é o caso. O
método sistematicamente falha se N for uma potência de algum primo, mas nesse caso
um algoritmo clássico eficiente é conhecido. Se N for par, podemos continuar dividindo
por 2 até o resultado ser ímpar. Resta-nos aplicar o método para os inteiros compostos
ímpares que não são potências de algum número primo. É possível provar que a probabilidade de achar x coprimo com N satisfazendo as condições (1) e (2) é alta.
Agora, considere o circuito da figura 7 que calcula a ordem r de um inteiro positivo
x menor que N , coprimo com N . Vx é um operador linear unitário dado por
Vx (|ji |ki) = |ji k + xj ,
(10)
onde |ji e |ki são os estados do primeiro e segundo registrador respectivamente. As
operações aritméticas são feitas módulo N , assim 0 ≤ k + xj < N . O operador TF2n foi
descrito na seção anterior.
E XERCÍCIO 4.1 Mostre que o operador Vx é unitário.
O primeiro registrador possui m qubits, onde m deve ser escolhido de forma que
N ≤ 2m ≤ 2N 2 para que a probabilidade de achar o resultado seja maior que 1/2. Se
2
73
2◦ registrador
(n qubits)
{
{
TF†2n
H
(n qubits)
H
1◦ registrador
|0i
|0i
Vx
|0i
|0i
|ψ0 i
|ψ1 i
|ψ2 i
|ψ3 i
|ψ4 i
|ψ5 i
Figura 7. Circuito quântico para achar a ordem de um inteiro positivo x módulo N .
a ordem é uma potência de 2, então é suficiente tomar m = n. Nesta seção, nós vamos
considerar somente esse caso especial.
Os estados do computador quântico estão indicados por |ψ0 i até |ψ5 i na figura 7.
O estado inicial é
|ψ0 i = |0 . . . 0i |0 . . . 0i .
| {z } | {z }
n
n
A aplicação do operador Hadamard em cada qubit do primeiro registrador resulta
n
2 −1
1 X
|ji |0i .
|ψ1 i = √
2n j=0
(11)
Agora note o que acontece quando aplicamos Vx em |ψ1 i:
|ψ2 i = Vx |ψ1 i
2n −1
1 X
= √
Vx (|ji |0i)
2n j=0
n
2 −1
1 X
= √
|ji xj .
2n j=0
(12)
O estado |ψ2 i é interessante, pois, já que Vx é linear, ele atua simultaneamente em todos os
termos |ji |0i para 2n valores de j, logo isto gera todas as potências de x simultaneamente.
Esta característica é chamada paralelismo quântico. Algumas destas potências são 1, as
quais correspondem aos estados
n
2
|0i |1i , |ri |1i , |2ri |1i , · · · , − 1 r |1i .
(13)
r
Isto explica a escolha de (10) para Vx . Classicamente, poderíamos calcular sucessivamente xj , para j começando de 2 até chegarmos a j = r. Quanticamente, pode-se
calcular todas as potências de x com uma única aplicação de Vx . No nível quântico,
74
todos os valores de j que produzem xj ≡ 1 módulo N são “conhecidos”. Mas esta informação não esta totalmente disponível no nível clássico. Uma informação clássica de um
estado quântico é obtida através de uma medida e, neste ponto, não ajudaria se medíssemos o primeiro registrador, já que todos os estados da superposição (12) possuem igual
amplitudes. A primeira parte da estratégia para determinar r é observar que o primeiro
registrador dos estados (13) é periódico. Então a informação que queremos é um período.
Para facilitar os cálculos, vamos medir o segundo registrador. Antes de fazer isto,
vamos reescrever o estado |ψ2 i fatorando os termos iguais do segundo registrador. Como
xj é uma função periódica com período r, vamos substituir j por ar + b na equação (12),
onde 0 ≤ a ≤ (2n /r) − 1 e 0 ≤ b ≤ r − 1. Lembre-se que estamos supondo que r é uma
potência de 2, portanto r divide 2n . A equação (12) é convertida em
 2n

−1
r−1
r
1 XX
|ψ2 i = √
|ar + bi xb .
(14)
2n b=0 a=0
No segundo registrador, substituímos xar+b por xb , já que xr ≡ 1 módulo N . Agora o
segundo registrador é medido. Qualquer resultado x0 , x1 , ..., xr−1 pode ser obtido com
igual probabilidade. Suponha que o resultado é xb0 . O estado do computador quântico
seja agora
 2n

r
−1
r
X
r 
|ψ3 i =
(15)
|ar + b0 i xb0 .
n
2
a=0
p
Note que depois da medida, a constante é renormalizada para r/2n , já que existem
2n /r termos na soma (15). A figura 8 mostra a probabilidade de obtermos os estados da
base computacional medindo o primeiro registrador. A probabilidade forma uma função
periódica com período r. Estes valores são zeros exceto para os estados |b0 i, |r + b0 i,
|2r + b0 i, ...,|2n − r + b0 i. Como o valor de b0 é randômico, ele esconde com perfeição
a informação que desejamos encontrar, ou seja, o valor de r. A única saída é explorar a
periodicidade dos kets ou equivalentemente, das amplitudes.
Como podemos descobrir o período de uma função eficientemente? A resposta é a
transformada de Fourier. A transformada de Fourier de uma função periódica de período
Distribuição de probabilidades
{
r
r
2n
0
b0
r + b0
2r + b0
3r + b0
Termos de |ψ3 i
(1◦ registrador)
Figura 8. Distribuição de probabilidades de |ψ3 i medido na base computacional (para o caso
b0 = 3 and r = 8). O eixo horizontal tem 2n pontos. O número de picos é 2n /r e o período é r.
75
r é uma nova função com período proporcional a 1/r. Isto faz toda a diferença para
determinar r. A transformada de Fourier é a segunda e última parte da estratégia usada
por Shor. Todo o método depende de um algoritmo quântico eficiente para calcular a
transformada de Fourier, que não está disponível classicamente.
Vamos continuar o processo de cálculo da figura 7. Estamos prontos para achar
o próximo estado do computador quântico — |ψ4 i. Aplicando a transformada de Fourier
inversa no primeiro registrador, usando a equação (6) e a linearidade da TF†2n , obtemos
|ψ4 i = TF†2n (|ψ3 i)
!
r 2rn −1
2n −1
b
r X
1 X −2πij(ar+b0 )/2n
x 0 .
√
e
|ji
=
n
2n a=0
2 j=0
Invertendo a ordem do somatório, temos




2n
n −1
−1
2X
r
X −2πija
1
n
2n /r  e−2πijb0 /2 |ji xb0 .
 1
|ψ4 i = √ 
e
r j=0 2n /r a=0
(16)
Usando (8), vemos que a expressão no colchetes é diferente de zero se e somente se
j = k2n /r com k = 0, ..., r − 1. Quando j assume tais valores, a expressão no colchetes
é igual a 1. Então temos
!
r−1
b
1 X −2πi k b0 k2n
x 0 .
r
e
(17)
|ψ4 i = √
r
r k=0
Para acharmos r, a expressão |ψ4 i têm duas vantagens sobre a expressão |ψ3 i (equação
(15)): r está no denominador do ket e o parâmetro aleatório b0 foi movido do ket para o
expoente ocupando agora um lugar inofensivo.
Distribuição de probabilidades
{
2n
r
1
r
0
2n
r
2 2n
r
3 2n
r
Termos de |ψ4 i
(1◦ registrador)
Figura 9. Distribuição de probabilidades de |ψ4 i medida na base computacional. O eixo horizontal tem 2n pontos, apenas os termos não nulos são mostrados. O número de picos é r e o
período é 2n /r.
A figura 9 mostra a distribuição de probabilidades de |ψ4 i medido na base computacional. Medindo o primeiro registrador, pegamos o valor k0 2n /r, onde k0 pode ser
qualquer número entre 0 e r − 1 com igual probabilidade (os picos na figura 9). Se obtivermos k0 = 0, não teremos nenhuma informação sobre r e o algoritmo tem que ser
76
rodado novamente. Se k0 6= 0, dividimos k0 2n /r por 2n , obtendo k0 /r. Nem k0 nem
r são conhecidos. Se k0 é coprimo com r, simplesmente selecionamos o denominador.
Se k0 e r tem fator comum, o denominador da fração reduzida k0 /r é um fator de r mas
não é o próprio r. Suponha que o denominador é r1 . Seja r = r1 r2 . Agora o objetivo
é determinar r2 , que é a ordem de xr1 módulo N . Rodamos novamente a parte quântica
do algoritmo para achar a ordem de xr1 . Se acharmos r2 na primeira rodada, o algoritmo para, caso contrário o aplicamos recursivamente. O processo recursivo não é longo,
porque o número de interações é menor ou igual a log2 r.
Tome N = 15 como exemplo, que é o menor número composto não trivial. O
conjunto de números menores que 15 coprimo com 15 são {1, 2, 4, 7, 8, 11, 13, 14}. Os
números no conjunto {4, 11, 14} tem ordem 2 e os números do conjunto {2, 7, 8, 13} tem
ordem 4. Portanto, em qualquer caso r é uma potência de 2 e os fatores de N = 15 podem
ser encontrados num computador quântico com ⌈log2 15⌉ = 8 qubits.
E XERCÍCIO 4.2 Refaça os passos descritos nessa seção sem supor que r divide N . Note
que todas as expressões onde aparece o termo 2n /r devem ser modificadas consistentemente. Após obter o estado |ψ4 i equivalente, faça o gráfico da distribuição de probabilidades (como o da figura 9) para N = 21 e x = 2. Repita novamente todo o processo
aumentando o número de qubits m no primeiro registrador de forma que obedeça a restrição N 2 ≤ 2m ≤ 2N 2 . Compare o novo gráfico da distribuição de probabilidades com
o anterior e explique porque as chances de encontrar r é maior no segundo caso.
5. Algoritmo para o Cálculo da Fase de um Autovalor
O autovalor de um operador unitário U é sempre da forma e2πiφ onde a fase φ é um
número real satisfazendo 0 ≤ φ < 1.
E XERCÍCIO 5.1 Mostre!
Nessa seção vamos apresentar um algoritmo para calcular uma aproximação de φ uma vez
dado o autovetor |ψi correspondente, isto é, supomos conhecido o vetor |ψi que satisfaz
U |ψi = e2πiφ |ψi. Na verdade não vamos supor apenas que |ψi seja conhecido. Vamos
supor que é possível de alguma forma preparar um registrador do computador quântico
no estado |ψi. Vamos assumir também que U é conhecido e pode ser implementado
eficientemente.
E XERCÍCIO 5.2 Suponha que U |ψi = e2πiφ |ψi. Mostre que a porta U k controlada pelo
primeiro qubit como no circuito abaixo
|0i
H
•
|ψi
/n
Uk
√1 (|0i
2
+ e2πiφk |1i)
|ψi
onde k é um inteiro, produz o seguinte resultado
|0i + e2πiφk |1i
|0i + |1i
k
√
√
|ψi =
|ψi .
C(U )
2
2
77
Se o inteiro k do exercício 5.2 for da forma 2m onde m é um inteiro de tamanho controlado, isto é, m = O(poly n) onde n é o número de qubits usado por |ψi, podemos
implementar U k eficientemente usando o algoritmo do quadrado repetido.
E XERCÍCIO 5.3 O algoritmo do quadrado repetido pode ser facilmente entendido com
um exemplo. Suponha que queremos calcular U 13 . Fazemos a decomposição binária de
13 = 1 · 23 + 1 · 22 + 0 · 2 + 1. Então com um pouco de álgebra podemos expressar U 13
apenas com quadrados
U 13 = (((U 2 U )2 )2 U.
Note que o número de vezes que temos que elevar uma matriz ao quadrado é bem menor
que o número 13. O número de multiplicações reduz drasticamente usando esse método.
Mostre que U k pode ser calculada com um número O(log k) multiplicações matriciais.
H
|0i
H
|0i
H
|0i
H
•
|ψi
/n
U2
•
•
0
U2
1
U2
2
m−1
1
√
(|0i
2
+ e2πiφ2
···
1
√
(|0i
2
+ e2πiφ2 |1i)
···
1
√
(|0i
2
+ e2πiφ2 |1i)
···
1
√
(|0i
2
+ e2πiφ2 |1i)
···
|0i
···
•
U2
m−1
|1i)
2
1
0
|ψi
Figura 10. Primeira parte do circuito para cálculo da fase de um autovalor.
O circuito da figura 10 mostra a primeira parte do algoritmo para o cálculo da fase
φ. A partir do resultado do exercício 5.2, podemos facilmente confirmar que o resultado
do circuito 10 é exatamente como mostrado.
Vamos supor para simplificar a apresentação que a fase tem no máximo m dígitos
binários φ = 0.φ1 · · · φm onde φ1 é igual a 0 ou 1, o mesmo para φ2 e assim por diante.
Usando a equação
m
X
φk
0.φ1 · · · φm =
,
k
2
k=1
m−1
m−2
0
podemos ver que os termos exponenciais e2πiφ2 , e2πiφ2 , · · · , e2πiφ2 na saída do
circuito da figura 10 são iguais a e2πi(0.φm ) , e2πi(0.φm−1 φm ) , · · · , e2πi(0.φ1 ···φm ) . Se consultarmos a figura 6 podemos nos convencer de que se aplicarmos a transformada de Fourier
inversa na saída do primeiro registrador do circuito da figura 10 obteremos o resultado
|φ1 i · · · |φm i. Isso quer dizer que o circuito completo para o cálculo da fase de um autovalor é o circuito da figura 11.
Se φ tiver um número de casas decimais muito grande ou se for um número irracional, o algoritmo fornece uma aproximação para o valor da fase. A aproximação
melhora se o número m de qubits do primeiro registrador for aumentado. Na verdade o
resultado é probabilístico e pode ser formalizado da seguinte forma. Seja ǫ a probabilidade de erro do algoritmo e n o número de casas decimais corretas de φ. Então o número
78
|0i
H
···
|0i
H
···
•
•
>=
>=
φ1
>=
>=
φm−1
φ2
TF†
•
|0i
H
|0i
H
•
|ψi
/n
U2
···
···
0
U2
1
···
U2
m−2
U2
m−1
φm
|ψi
Figura 11. Circuito completo para cálculo da fase de um autovalor.
de qubits no primeiro registrador deve ser
1
m = n + log(2 + ) .
2ǫ
(18)
E XERCÍCIO 5.4 (Difícil) Mostre que m deve ter no mínimo o valor descrito pela equação
(18) caso se queira n dígitos de φ corretos com uma probabilidade de erro ǫ.
Uma vez que vamos usar o circuito de cálculo de fase outras vezes, vamos descrevêlo de uma forma mais sucinta. A figura 12 descreve o algoritmo como uma caixa preta. Os
seus detalhes não são mostrados, porém as grandezas relevantes estão alí representadas
(U , |ψi, φ). Note que a saída do primeiro registrador corresponde aos dígitos binários de
φ. Como φ é um número menor que 1, segue que a saída na verdade é o número φ2m ou
uma aproximação desse número caso φ tenha mais do que m dígitos binários.
|0i /m
Fasem (U )
|ψi /n
>=
aprox. para φ2m
|ψi
Figura 12. Circuito simplificado para cálculo da fase de um autovalor φ de autovetor |ψi do operador
U , onde U |ψi = e2πiφ |ψi. O número de qubits m no primeiro registrador deve ser dado pela equação
(18) caso se queira n dígitos de φ corretos com uma probabilidade de erro ǫ.
E XERCÍCIO 5.5 (Fácil) Mostre que o circuito abaixo
H ⊗m
•
TF†
U
é equivalente ao circuito Fasem (U ). Sugestão: use o exercício 2.2.
6. Algoritmo de Kitaev
O algoritmo de Shor calcula a ordem de um número x modulo N desde que MDC(x, N ) =
1. Na terminologia de Teoria de Grupos dizemos que o algoritmo de Shor calcula a ordem de x no grupo Z×
N , chamado grupo das unidades, isto é, o conjunto dos números
inteiros positivos x menores que N tal que MDC(x, N ) = 1 com a operação de multiplicação modulo N . Uma questão natural que surge é se o algoritmo de Shor pode ser
79
generalizado para o cálculo de ordem em outros grupos. Só para recordar, um grupo é
um conjunto não vazio com uma operação binária que não precisa ser comutativa que satisfaz as propriedades de fechamento, associatividade, tem o elemento identidade e todo
elemento tem um elemento inverso no conjunto.
E XERCÍCIO 6.1 Seja G um grupo multiplicativo com o elemento identidade e e seja g ∈
G. Mostre que o conjunto hgi = {g, g 2 , · · · , g r } é um grupo comutativo onde r é a ordem
de g, isto é, o menor inteiro tal que g r = e. O elemento g é chamado de gerador do grupo
< g >. Quando um grupo é gerado por um único elemento ele é dito cíclico.
O primeiro problema a se resolver é como representar os elementos do grupo no
computador quântico. Vamos considerar grupos finitos. Seja |G| a ordem do grupo G. O
número de qubits deve ser pelo menos
n = ⌈log2 |G|⌉.
Cada elemento do grupo deve ser então “codificado” como um número binário de n dígitos. Assim os vetores da base computacional vão corresponder aos elementos do grupo
a menos de uma sobra. Se |G| < 2n então alguns vetores da base computacional não
têm correspondência com elementos do grupo de forma que um subespaço do espaço de
Hilbert não é utilizado. Nesse subespaço assumimos que todos os operedores tem atuação
trivial, isto é, atuam como o operador identidade. Além disso assumimos que podemos
implementar a operação de multiplicação do grupo, isto é, se |j1 · · · jn i corresponde ao
elemento g1 ∈ G e |k1 · · · kn i corresponde ao elemento g2 ∈ G então assumimos que
podemos encontrar o vetor |l1 · · · ln i da base computacional que corresponde ao elemento
g1 g2 . De agora em diante vamos usar a notação |gi para representar o vetor da base
computacional correspondente ao elemento g. Essa discussão mostra que é possível implementar o operador unitário Uh para um elemento genérico fixo h em G cuja atuação na
base computacional é
Uh |gi = |hgi .
(19)
Também assumimos que o custo computacional da operação Uh |gi é baixo, melhor dizendo,
assumimos que é O(1). O algoritmo de Kitaev resolve eficientemente o problema de achar
a ordem de Uh , isto é, achar o menor r tal que (Uh )r = I.
E XERCÍCIO 6.2 Mostre que (1) Uh é unitário, (2) (Uh )j = Uhj para qualquer inteiro j,
(3) a ordem de Uh é igual a ordem de h e (3) r ≤ |G|.
E XERCÍCIO 6.3 Como é a atuação de Uh† na base computacional?
Suponha que |ψi seja um autovetor de Uh , isto é, Uh |ψi = λ |ψi, onde λ ∈ C é o
autovalor correspondente. Uma vez que (Uh )r |ψi = |ψi, segue que λr = 1. Portanto λ é
uma das r-ésimas raízes da unidade. Para cada g ∈ G vamos definir r vetores indexados
por k = 0, 1, · · · , r − 1 da seguinte forma
r−1
E
1 X
(g)
(ωr )jk ghj .
=√
ψk
r j=0
(20)
E
(g)
Os vetores ψk são autovetores de Uh cujos autovalores correspondentes são (ωr )k .
80
E
(g)
E XERCÍCIO 6.4 Mostre que ψk
são autovetores de Uh com autovalores (ωr )k para
k = 0, 1, · · · , r − 1 e ∀g ∈ G.
E
(g)
Note que a fase do autovalor (ωr )k do autovetor ψk é kr . Como k é um inteiro
satisfazendo 1 ≤ k < r, a determinação da fase pode nos dar o valor de r pois k pode ser
coprimo com r. Temos a nossa disposição o algoritmo para cálculo da fase, conhecemos
Uh e queremos a fase de um autovalor. O problema agora é como
o segundo reg preparar
E
(g)
istrador do circuito Fasem (Uh ) da figura 12 como o autovetor ψk . Parece um problema
intransponível.
No
E entanto existe uma estratégia um pouco diferente. A superposição dos
(g)
autovetores ψk para todos os valores de k fornece um vetor bastante conhecido, que é
r−1
1 X (g) E
.
|gi = √
ψ
r k=0 k
(21)
E XERCÍCIO 6.5 Mostre que a equação (21) está correta.
A idéia é usar |gi como entrada do segundo registrador, como mostra o circuito da figura
13.
|0i /m
|gi /n
Fasem (Uh )
>=
aprox. para
˛
E
˛ (g)
˛ψk0
k0 2m
r
Figura 13. Circuito para cálculo da ordem r do operador Uh dado pela equação (19).
A saída do circuito 13 pode ser surpresa para muitos leitores. Aprendemos que
o circuito para cálculo de fase mantém o estado do segundo registrador invariante se a
entrada for o autovetor em questão. Isso não acontece no circuito 13, pois |gi não é um
autovetor de Un . Para calcular a saída temos que usar e equação (21) e a linearidade do
circuito da seguinte forma
!
r−1
1 X (g) E
Fasem (Uh )(|0i |gi) = Fasem (Uh ) √
|0i ψk
r k=0
r−1
E
1 X
(g)
Fasem (Uh ) |0i ψk
= √
r k=0
r−1
E
1 X k k2m
(g)
ωr = √
ψk .
r aprox
r k=0
(22)
Ao medirmos o primeiro registrador obtemos uma aproximação de k0 2m /r para algum
valor de k0 com igual probabilidade
no intervalo 1 ≤ k < r. O estado do segundo
E
(g)
registrador passa a ser ψk0 . A probabilidade de acerto do algoritmo é maior que 1/2
pois existem mais números k coprimos com r do que números com fatores comuns.
81
7. Algoritmo de Watrous
Nesta seção abordaremos o problema do cálculo da ordem de um grupo solúvel, apresentando um algoritmo quântico eficiente para a sua solução. Vale ressaltar que não é
possível construir algoritmo clássico eficiente para resolver esse problema no caso geral.
O algoritmo que apresentaremos é uma generalização do algoritmo de Shor.
Nessa seção e na seguinte estamos supondo que o leitor tenha já alguma familiaridade com teoria de grupos. Vamos relembrar rapidamente alguns conceitos básicos.
Um grupo G é dito abeliano se a operação binária do grupo for comutativa. H ⊆ G é
dito um subgrupo de G se H forma um grupo com o operação binária de G. Neste caso,
escrevemos H ≤ G. Seja a ∈ G, o conjunto aH = {g ∈ G |g = ah para algum h ∈ H}
é chamado uma classe lateral de H em G com representante a. Um subgrupo H de G é
dito normal se H = gHg −1 para todo g ∈ G, neste caso escrevemos H E G.
Vamos agora a definir o que é um grupo solúvel e descrever algumas de suas
propriedades básicas. Existe vasta literatura a respeito dessa classe de grupos como mencionamos na bibliografia. Ao longo de toda esta seção sempre consideraremos G finito.
Um grupo G é solúvel se existem g1 , · · · , gm ∈ G tais que, definindo Hj = hg1 , · · · , gj i
temos
G = Hm D · · · D H1 D H0 := {e}.
(23)
Note que pela normalidade de Hj−1 em Hj , temos que gj Hj−1 = Hj−1 gj e, assim, Hj =
hgj i Hj−1 . Uma série de subgrupos como (23) é chamada uma série subnormal.
E XERCÍCIO 7.1 Mostre que Hj = hgj i Hj−1 e que na série subnormal (23) os quocientes
são todos cíclicos, com Hj /Hj−1 = hgj Hj−1 i.
Dado um grupo G, um subgrupo H de G e g ∈ G, define-se a ordem de g em
relação à H, denotada por rH (g), como
rH (g) := min{d ∈ N; g d ∈ H}.
Sendo G um grupo solúvel denotamos rj := rHj−1 (gj ).
E XERCÍCIO 7.2 Mostre que
rj = |Hj /Hj−1 | = | hgj Hj−1 i |.
Conclua daí que |G| =
Qm
j=1 rj .
Assim como no algoritmo de Kitaev, admitimos que os elementos do grupo G
estejam codificados como um número binário de n dígitos. Nesta codificação a operação
do grupo é efetuada por uma transformação unitária que, para cada g ∈ G fixo, atua da
seguinte forma
Ug |hi = |ghi .
O algoritmo quântico que iremos apresentar computa eficientemente a ordem de
um grupo solúvel e, além disso, produz um estado quântico que aproxima, com alta prob82
abilidade, uma superposição uniforme dos elementos desse grupo. A superposição uniforme dos elementos de um conjunto S é definida como o estado
1 X
|gi .
|Si := p
|S| g∈S
O algoritmo combina duas subrotinas. A primeira delas computa a ordem de um elemento,
g ∈ G, em relação à um subgrupo H ≤ G. A segunda, converte superposições uniformes
dos elementos do subgrupo H, em superposições uniformes do subgrupo hgi H. Vamos
apresentar as duas subrotinas e depois combiná-las num algoritmo principal, obtendo o
resultado desejado.
Pelo Execício 7.2 vemos que se soubermos calcular a ordem rj dos elementos gj
em relação ao subgrupo Hj−1 teremos calculado a ordem do grupo G. Nesta seção descrevemos como fazer isso. O algoritmo é basicamente o algoritmo de Shor para cálculo
de ordem. A diferença reside no fato de iniciarmos um dos registradores com uma superposição uniforme dos elementos do subgrupo em questão. Surge aqui uma dificuldade
que será superada à frente: Como criar eficientemente essas superposições?
Seja H um subgrupo de G e g um elemento qualquer de G. Desejamos determinar
r = rH (g). Considere um circuito quântico
com dois
p
Pregistradores, R e A, o primeiro
inicializado com a superposição |Hi = 1/ |H|
h∈H |hi e o segundo inicializado
no estado |0i correspondente à ZN , onde N será escolhido posteriormente. A figura 14
mostra um circuito para o cálculo de r.
|0i /?
Vg
↓
•
TFN
|Hi /?
↑
|ϕ1 i
TF†N
Ug
↑
|ϕ2 i
NM
↑
|ϕ3 i
↑
|ϕ4 i
↑
|ϕ5 i
Figura 14. Circuito para o cálculo da ordem rH (g).
A porta TFN é, como antes, a transformada de Fourier em ZN e TF†N sua transposta
conjugada. A porta Vg é definida como
Vg (|ai |hi) = |ai (Ug )a |hi
= |ai |g a hi
(24)
e sua implementação foi discutida no exercício 2.2. Vamos agora descrever passo a passo
os estados |ϕ1 i · · · |ϕ5 i do algoritmo. Para o estado inicial |ϕ1 i = |0i |Hi, vamos supor
que saibamos montar a superposição uniforme |Hi. O circuito começa aplicando a transformada de Fourier no primeiro registrador, que produz uma superposição dos elementos
de ZN da seguinte forma
N −1
1 X
|ai |Hi .
|ϕ2 i = |ZN i |Hi = √
N a=0
83
Quando a porta Vg atua sobre o estado |ϕ2 i obtemos
N −1
1 X
√
|ai |g a Hi .
|ϕ3 i =
N a=0
Desde que N seja suficientemente grande, N ≫ r, podemos rearranjar o estado |ϕ3 i, juntando os estados do primeiro registrador que tem o mesmo estado no segundo registrador.
Por simplicidade, admitamos que r | N . Note que os únicos valores distintos possíveis
para o segundo registrador são H, gH, g 2 H, · · · , g r−1 H, já que r = rH (g). Assim, dado
a ∈ {0, · · · , N − 1}, podemos escrevê-lo como a = a′ + br onde 0 ≤ a′ ≤ r − 1 e
′
′
0 ≤ b ≤ N/r − 1 e temos que g a H = g a g br H = g a H. Assim |ϕ3 i pode ser reescrito
como
N
r−1 r −1
E
1 XX
′
|ϕ3 i = √
|a′ + bri g a H .
N a′ =0 b=0
Aplicando a transposta conjugada da transformada de Fourier, tomamos a informação
importante contida no ket |a′ + bri e a colocamos no expoente de uma fase. Por simplicidade, trocaremos o símbolo a′ por a. O estado resultante é:
N
r−1 r −1 N
−1
X
1 XX
−c(a+br)
ω
|ci |g a Hi ,
|ϕ4 i =
N a=0 b=0 c=0 N
−c(a+br)
onde ωN
= e−
é projetado em
2πic(a+br)
N
. Efetuando a medida no primeiro registrador, o estado |ϕ4 i
N
r−1 r −1
1 XX
−c (a+br)
|ϕ5 i = √
ωN 0
|c0 i |g a Hi
N a=0 b=0
para algum valor de c0 como discutiremos adiante. Rearranjando este estado, temos
N

−1
r−1
r
X
X
1
−c0 br  −c0 k

ωN |c0 i |g a Hi .
ωN
|ϕ5 i = √
N a=0 b=0
Note a semelhança com o algoritmo de Shor. Usando a identidade (8) segue que c0 =
sN/r, com s uniformemente distribuído entre 0 e r − 1. Dividindo por N obtemos s/r.
Escolhendo N = 22n+O(log(1/ε)) , 0 < ε < 1, pelo método das frações repetidas encontramos u e v coprimos, tais que u/v = s/r com probabilidade 1 − ε. O v assim determinado ou é o próprio r ou algum de seus fatores primos. Para determinar r, repetimos
todo o procedimento O (log (1/ε)) vezes e calculamos o mínimo múltiplo comum entre
os vários v’s encontrados. Isto irá determiná-lo com probabilidade de pelo menos 1 − ε.
Passamos agora a descrição da segunda subrotina. Como mencionamos anteriormente, ao iniciarmos o algoritmo anterior, pressupomos a existência de um estado de
superposição de todos os elementos do subgrupo H. Descreveremos agora um método
para converter superposições uniformes dos elementos do subgrupo H em superposições
uniformes do subgrupo hgi H, ou seja, converter |Hi em |hgi Hi. Seja então H ≤ G e
g ∈ G com a suposição adicional que gH = Hg.
84
E XERCÍCIO 7.3 Mostre que nessas condições hgi H é um subgrupo de G tal que H E
hgi H. Além disso, | hgi H/H| = rH (g).
Supondo que tenhamos várias cópias de |Hi, desejamos convertê-las em cópias
de |hgi Hi. Para simplificar a notação, seja r = rH (g). Tomemos l suficientemente
grande, mais tarde o definiremos apropriadamente. Considere registradores R1 , · · · , Rl
todos inicializados no estado |Hi. Sejam ainda A1 , · · · , Al registradores inicializados
com |0i, onde aqui 0 ∈ Zr . O circuito na figura 15 dará início à conversão das l cópias de
|Hi em l − 1 cópias de |hgi Hi.
A1 = |0i
•
TFr
..
.
•
TFr
TFr
NM
Ug
..
.
Ri = |Hi
..
.
Al = |0i
NM
Ug
..
.
R1 = |Hi
..
.
Ai = |0i
TFr
..
.
•
TFr
TFr
NM
Ug
Rl = |Hi
↑
|ϕi
Figura 15. Circuito para início da conversão das cópias de |Hi em cópias de |hgi Hi.
Para cada par de registradores (Aj , Rj ), a ação do circuito da figura 15 é equivalente à ação do circuito da figura 14 exceto pelo fato da medida ser feita sobre os registradores A’s. Deixamos então o seguinte exercício.
E XERCÍCIO 7.4 Mostre que o estado |ϕi da figura 15 é
⊗l

1 X X a j bj
ωr |bj i |g aj Hi
|ϕi = 
r a ∈Z b ∈Z
j
r
r
j
Efetuada a medida nos registradores Aj e denotando por b′j o resultado da medida
para cada j = 1, · · · , l, o registrador Rj , após a renormalização, se encontra no estado
|ψj i dado por
1 X aj b′j aj
ωr |g Hi .
|ψj i = √
r a ∈Z
j
r
Se escolhemos l ∈ Ω((log log r)(log(1/ε))), 0 < ε < 1, a probabilidade de um desses b′j
ser coprimo com r é, no mínimo, 1 − ε. Assumindo que seja este o caso, escolha k tal que
b′k seja coprimo com r. Agora usaremos o estado |ψk i para converter os demais estados
|ψj i em cópias de |hgi Hi. Primeiro, notemos que |ψk i é autovetor da transformação
Ugs h qualquer que seja s ∈ Zr e h ∈ H, lembre-se Ugs h |h′ i = |g s hh′ i. De fato, como
85
gH = Hg
1 X ak b′k s ak
Ugs h |ψk i = √
ωr |g hg Hi
r a ∈Z
r
k
1 X ak b′k s ak
ωr |g g hHi
= √
r a ∈Z
r
k
1 X ak b′k s+ak ωr
g
H
= √
r a ∈Z
r
k
1 X (a′k −s)b′k a′k E
ωr
= √
g H
r ′
ak ∈Zr
−sb′k
= ωr
|ψk i .
Como b′k é coprimo com r, para cada j = 1, · · · , l, j 6= k seja cj ∈ N tal que cj ≡ b′j b−1
k
mod r. De maneira análoga ao que fizemos anteriormente, mostra-se que |g s hi |ψk i
c
também é um autovetor de UGj .
c
E XERCÍCIO 7.5 Mostre que |ψk i é autovetor da transformação Ugsjh quaisquer que sejam
s ∈ Zr , j = 1, · · · , l, j 6= k e h ∈ H com
c
−sb′j
Ugsjh |ψk i = ωr
|ψk i .
Vamos definir o operador U
U (|gi |hi) = |gi Ug |hi = |gi |ghi .
E XERCÍCIO 7.6 Mostre que U é unitário.
Além disso, temos que
−sb′j
U cj |g s hi |ψk i = ωr
|g s hi |ψk i .
quaisquer que sejam s ∈ Zr , j = 1, · · · , l, j 6= k e h ∈ H.
E XERCÍCIO 7.7 Verifique a afirmação anterior.
Dito isto, usaremos agora o estado |ψk i para converter cada um dos estados |ψj i
em cópias da superposição uniforme dos elementos do grupo hgi H. Considere para cada
par (Rj , Rk ) o circuito, exibido na figura 16, onde um novo registrador foi criado para
carregar o qubit cj . Mostraremos que ele converte o estado |ψj i em uma cópia de |hgi Hi
86
e mantém |ψk i inalterado. De fato, temos que:
Vg |cj i |ψj i |ψk i = U cj |ψj i |ψk i
X X a j b′
1
= p
ωr j U cj |g aj hi |ψk i
r|H| aj ∈Zr h∈H
X X aj b′ −aj b′
1
ωr j ωr j |g aj hi |ψk i
= p
r|H| aj ∈Zr h∈H
X X
1
= p
|g aj hi |ψk i
r|H| aj ∈Zr h∈H
= |hgi Hi |ψk i
|cj i
|ψj i
|ψk i
Vg
↓
•
U
Figura 16. Este circuito converte o estado |ψj i no estado |hgi Hi.
Repetindo este argumento para cada j 6= k resulta na obtenção de l − 1 cópias
de |hgi Hi. Após isso, podemos descartar o estado |ψk i. Vemos que a conversão das
cópias de |Hi em cópias de |hgi Hi pode ser feita eficientemente e com probabilidade de
correção tão alta quanto desejarmos.
Iremos agora mostrar o algoritmo que, combinando as duas subrotinas mostradas
até aqui, computa a ordem do grupo G. Relembrando as nossas hipóteses, temos um
grupo G solúvel, portanto, existem g1 , · · · , gm ∈ G tais que sendo Hj = hg1 , · · · , gj i
tem-se
G = Hm D · · · D H1 D H0 := {e},
com Hj = hgj i Hj−1 , rj = rHj−1 (gj ) = |Hj /Hj−1 | e r = |G| =
Qm
j=1 rj .
O algoritmo será inicializado com uma grande quantidade, K ∈ N, de cópias
do estado |ei, que podem ser obtidas trivialmente. Após isso, o algoritmo executa as
operações conforme mostra a figura 16.
A fim de que ele calcule r com erro limitado por 0 < ε < 1, é necessário que em
cada volta do laço, o erro cometido seja no máximo ε/m. Assim, o cálculo de rj deve
ser feito com erro máximo ε/2m e também a conversão das cópias de |Hj−1 i em cópias
de |Hj i deve ser feita com erro máximo ε/2m. Desta forma, K deve ser escolhido para
atender às necessidades tanto do cálculo de ordem, quanto para a conversão das cópias,
sendo suficiente escolher K = O(log n log(m/ε)). No algoritmo, quando usamos K − 1
cópias de |Hj−1 i para computar rj , significa que o procedimento para cálculo de ordem,
primeira subrotina apresentada, se repetirá k − 1 vezes. Note também, que a cada volta
87
Algoritmo 1 Algoritmo para o cálculo da ordem de um grupo solúvel G.
Entrada: K(m + Q
1) cópias do estado |ei.
Saída: r = |G| = m
j=1 rj .
1: Prepare K(m + 1) cópias do estado |ei.
2: para j from 1 to m, downward faça
3:
Use K − 1 cópias de |Hj−1 i para computar rj e descarte estas cópias.
4:
Use uma das cópias de |Hj−1 i para converter as cópias restantes em cópias de |Hj i.
Descarte a cópia não convertida.
5: fim para
do laço, K cópias são descartadas. Portanto, na última volta, K cópias serão descartadas
e as K cópias remanescentes serão convertidas em cópias de |Gi.
Por fim, concluímos que com a escolha feita para K, a ordem r de G e a superposição |Gi são computadas em tempo quântico polinomial em nm + O(1/ε), com
probabilidade de acerto de pelo menos 1 − ε.
8. Algoritmo para Decompor Grupos Abelianos
O Teorema Fundamental de Grupos Finitos Abelianos nos diz que qualquer grupo finito
abeliano pode ser decomposto como uma soma direta de subgrupos cíclicos cujas ordens
são potências de primos. Entretanto, não é conhecido nenhum algoritmo clássico que
explicite este isomorfismo eficientemente. Por exemplo, considere o grupo das unidades
Z×
N . Nenhum algoritmo eficiente para determinar um conjunto gerador para esse tipo de
grupo abeliano é conhecido. Consequentemente não podemos determinar eficientemente
a decomposição de Z×
N como uma soma direta de subgrupos cíclicos. Nesta seção apresentaremos um algoritmo quântico eficiente para fazer a decomposição.
Sejam G1 , . . . , Gn grupos, definimos o produto direto de G1 , . . . , Gn como sendo
o produto cartesiano G1 × . . . × Gn com a operação
(g1 , . . . , gn ) · (h1 , . . . , hn ) := (g1 h1 , . . . , gn hn ).
(25)
E XERCÍCIO 8.1 Mostre que G1 × . . . × Gn é de fato um grupo com a operação definida
em (25). Sugestão: o elementro neutro de G1 × . . . × Gn é (e1 , . . . , en ), onde ei é o
elemento neutro de Gi , i = 1, . . . , n; o elemento inverso de (g1 , . . . , gn ) é (g1−1 , . . . , gn−1 ).
No produto direto, um novo grupo é gerado a partir dos grupos G1 , . . . , Gn . Cada grupo
pode ter um tipo diferente de produto, isto é, o produto dos elementos de G1 não precisa
ter relação com o produto dos elementos de G2 . Um conceito relacionado ao produto
direto é a soma direta, no entanto nesse último temos um único produto binário. Quando
um grupo G e subgrupos H1 , . . . , Hn satisfazem as condições i) G = H1 . . . Hn , ii) Hi Gi , ∀ i = 1, . . . , n., iii) Hi ∩ (H1 . . . Hi−1 Hi+1 . . . Hn ) = {e}, ∀ i = 1, . . . , n, dizemos
que G é a soma direta de H1 , . . . , Hn e escrevemos G = H1 ⊕ . . . ⊕ Hn .
E XERCÍCIO 8.2 Mostre que se H é um subgrupo de um grupo abeliano G, então o conjunto das classes laterais de H formam um grupo com a multiplicação de classes laterais
definida por
g1 H · g 2 H = g 1 g2 H
88
para todo g1 , g2 ∈ G. Este grupo é denotado por G/H.
E XERCÍCIO 8.3 Seja H um subgrupo de um grupo abeliano G. Mostre que se g1 , . . . , gk
geram G, então g1 H, . . . , gk H geram G/H.
Seja G um grupo e p um número primo. Seja H ≤ G. Então H é dito um psubgrupo de Sylow de G se |H| = pα para algum α ∈ N tal que pα divide |G| mas pα+1
não divide.
E XERCÍCIO 8.4 Mostre que todo grupo finito abeliano G pode ser expresso como uma
soma direta de seus p-subgrupos de Sylow. Sugestão: use o fato de que todo p-subgrupo
de G é normal em G e as ordens dos p-subgrupos são coprimas.
E XERCÍCIO 8.5 Seja H um subgrupo de G = Gp1 ⊕ . . . ⊕ Gpl onde Gpi é um pi subgrupo de Sylow para todo i = 1, . . . , l e p1 , . . . , pl primos distintos. Mostre que
existe Hpi ≤ Gpi , i = 1, . . . , l tal que H = Hp1 ⊕ . . . ⊕ Hpl . Sugestão: defina
Πi : G → Gpi , tal que (g1 , . . . , gl ) 7→ gi , i = 1, . . . , l e Hi = Πi (H). Verifique
que Hi ≤ Gpi e H ≤ H1 ⊕ . . . ⊕ Hl . Tome (h1 , . . . , hl ) ∈ H1 ⊕ . . . ⊕ Hl e note que
|Gp1 |, . . . , |Gpl | são dois a dois primos entre si, assim utilize o Teorema Chinês do Restos
e conclua que (h1 , 0, . . . , 0), (0, h2 , . . . , 0), (0, 0, . . . , hl ) ∈ H.
Uma matriz U é dita unimodular se ela é composta apenas de elementos inteiros e
seu determinante tem módulo unitário. Sabemos que a matriz U −1 pode ser determinada
em geral pela fórmula
1
Uij−1 =
(26)
(−1)i+j det(U ij ),
det(U )
onde U ij é a matriz obtida eliminando a i-ésima linha e j-ésima coluna da matriz U .
Como Uij−1 é um inteiro, concluímos que a matriz U −1 é inteira.
E XERCÍCIO 8.6 Mostre que U é unimodular se, e somente se, U −1 é unimodular.
Chamamos de operações elementares as seguintes operações sobre as colunas de
uma matriz:
1. trocar duas colunas de lugar;
2. multiplicar uma coluna por −1;
3. adicionar um múltiplo inteiro de uma coluna numa outra coluna;
As operações elementares sobre as linhas são definidas de forma análoga.
T EOREMA 8.1 Para qualquer matriz com entradas inteiras A, pode-se determinar em
tempo polinomial usando operações elementares
sobre
as linhas e colunas de A matrizes
D 0
, onde D = diag(d1 , . . . , dk ) é uma
unimodulares U e V tais que U AV =
0 0
matriz diagonal com entradas inteiras d1 , . . . , dk tais que d1 |d2 | . . . |dk , e para cada i, o
produtod1 , . . . , di é igual ao mdc dos subdeterminantes de A de ordem i. Dizemos que a
D 0
é a forma normal de Smith de A.
matriz
0 0
89
O teorema que vamos enunciar logo abaixo é parte fundamental do algoritmo de
decomposição de grupos abelianos.
T EOREMA 8.2 Dado um conjunto gerador {a1 , . . . , ak } de um grupo finito abeliano G e
uma matriz M tal que ax1 1 . . . axk k = e se, e somente se, x = (x1 , . . . , xk )T ∈ intcol(M ),
onde intcol(M ) denota o conjunto dos valores obtidos tomando combinações lineares
inteiras das colunas de M , nós podemos determinar em tempo polinomial (no tamanho
de M ) g1 , . . . , gl , com l ≤ k tais que, G = hg1 i ⊕ . . . ⊕ hgl i.
Demonstração: Pelo teorema 8.1, podemos achar
em tempo
polinomial matrizes uniD
0
−1
modulares Uk×k e Vn×n tais que Uk×k
Mk×n Vn×n =
, onde D = diag(d1 , . . . , dm )
0 0
| {z }
D′
é uma matriz diagonal com entradas inteiras d1 , . . . , dm . Como V é unimodular, temos
que
intcol(M V ) = intcol(M ).
(27)
Assim,
ax1 1 . . . axk k = e ⇔ x = (x1 , . . . , xk )T ∈ intcol(M V ).
′
′
Agora para cada i, j = 1, . . . , k, seja ri a ordem de ai , onde ai = au1 1i . . . auk ki e uji
são as entradas da matriz U . Pela proposição 8.1 a′1 r1 . . . a′k rk = e se, e somente se, di |ri ,
logo di = ri pela minimalidade de ri . Observe também que devemos ter m = k. De fato,
suponhamos por absurdo que m = k − j, para algum 1 ≤ j ≤ k − 1, então invocando
novamente a proposição 8.1 temos
x
(a′1 1 . . . a′k−j
xk−j
x
x
)a′k−j+1 k−j+1 . . . a′k k = e
x
x
⇔ a′k−j+1 k−j+1 . . . a′k k = e
⇔ xk−j+1 = . . . = xk = 0.
Mas isso é um absurdo, pois, como G é finito, existem inteiros positivos rk−j+1 , . . . , rk ,
tais que
r
r
(28)
a′k−j+1 k−j+1 . . . a′k k = e,
onde rk−j+1 , . . . , rk são as ordens dos elementos a′k−j+1 , . . . , a′k , respectivamente. Portanto, m = k.
Agora, seja j o menor índice tal que dj > 1. Considere o conjunto formado
′
pelos gi = ai+j−1 para todo i = 1, . . . , l, onde l = m − j + 1. É claro que o conjunto
{g1 , . . . , gl } ainda gera G e a ordem de cada gi é di+j−1 . Com efeito, suponhamos que
′
′
d1 = . . . = dj−1 = 1. Daí temos que a1 = . . . = aj−1 = e (pois di é a ordem de
′
ai ). Assim, se retirarmos as identintades do conjunto de geradores, ainda continuaremos
com um conjunto de geradores para G. Observe ainda que são satisfeitas as seguintes
propriedade para o grupo G:
(1) G = hg1 , . . . , gl i = hg1 i . . . hgl i;
(2) Para todo g ∈ G, existem elementos unicamente determinados x1 ∈ hg1 i , . . . , xl ∈
hgl i tais que g = x1 . . . xl ;
(3) hgi i ∩ (hg1 i . . . hgi−1 i hgi+1 i . . . hgl i) = {e}, ∀ i = 1, . . . , l.
90
Portanto, segue direto das relações (1), (2) e (3) acima que G = hg1 i ⊕ . . . ⊕ hgl i e com
isto provamos o teorema 8.2.
E XERCÍCIO 8.7 Mostre que a equação (27) está correta.
′
′ E XERCÍCIO 8.8 Mostre que G = a1 , . . . , ak .
E XERCÍCIO 8.9 Mostre que o grupo G satisfaz as propriedades (1), (2), e (3) na demonstração do teorema 8.2.
P ROPOSIÇÃO 8.1 Seja a′i = au1 1i . . . auk ki , ∀ i = 1, . . . , k. Então as seguintes condições
são equivalentes:
′
x1
′
x
(i) a1 . . . ak k = e
(ii) (x1 , . . . , xk )T ∈ intcol(D′ )
(iii) di |xi para i = 1, . . . , m e xi = 0 para i = m + 1, . . . , k.
Demonstração: De fato, para provarmos que (i) ⇒ (ii), observe que
′
x1
′
x u + . . . + xk ukk
| 1 k1 {z
}
x u + . . . + xk u1k
}
| 1 11 {z
xk
z
z1
k
. . . ak
a1 . . . ak = a1
=e
T
⇔ z = (z1 , . . . , zk ) ∈ intcol(M ) = intcol(M V ) = intcol(U D′ ).
Logo,
z1 = α1 u11 d1 + . . . + αm u1m dm + αm+1 u1m+1 .0 + . . . + αn u1k .0
z2 = α1 u21 d1 + . . . + αm u2m dm + αm+1 u2m+1 .0 + . . . + αn u2k .0
..
.
(29)
zk = α1 uk1 d1 + . . . + αm ukm dm + αm+1 ukm+1 .0 + . . . + αn ukk .0.
Substituindo zi = x1 ui1 + . . . + xk uik nas equações em (29) para todo i = 1, . . . , k,
obtemos
(x1 − α1 d1 )u11 + . . . + (xm − αm dm )u1m + xm+1 u1m+1 + . . . + xk u1k = 0
(x1 − α1 d1 )u21 + . . . + (xm − αm dm )u2m + xm+1 u2m+1 + . . . + xk u2k = 0
(x1 − α1 d1 )uk1 + . . . + (xm − αm dm )ukm + xm+1 ukm+1 + . . . + xk ukk = 0
ou equivalente,



(x1 − α1 d1 ) 

u11
u21
..
.
uk1






 + . . . + (xm − αm dm ) 


u1m
u2m
..
.
ukm






 + . . . + xk 


u1k
u2k
..
.
ukk


 
 
=
 
0
0
..
.
0





⇔ x1 = α1 d1 , . . . , xm = αm dm , com xi = 0 ∀ i = m + 1, . . . , k, pois, U é invertível.
Logo, (x1 , . . . , xk )T ∈ intcol(D′ ).
91
Que (ii) ⇒ (iii), segue imediatamente da definição de intcol(D′ ). Finalmente,
vamos mostrar que (iii) ⇒ (i). Com efeito, segue de (iii) que existem inteiros positivos
α1 , . . . , αm tais que
x
a′1 1 . . . a′k
xm
= ax1 1 u11 +...+xm u1m . . . axk 1 uk1 +...+xm ukm
= a1α1 d1 u11 +...+αm dm u1m . . . aαk 1 d1 uk1 +...+αm dm ukm
= ay11 . . . aykk ,
onde
y = (y1 , . . . , yk )T ∈ intcol(U D′ ) = intcol(M ).
(30)
Mas por hipótese ay11 . . . ayk = e, portanto, a′1 x1 . . . a′k xk = e, e com isto terminamos a
prova.
Computadores quânticos prometem resolver certos problemas assintoticamente
mais rápido do que seus equivalentes clássicos. A maior parte dos algoritmos quânticos
com ganho exponencial em relação aos seus equivalentes clássicos pode ser considerada
casos particulares do chamado Problema do Subgrupo Escondido (PSE). O PSE consiste
em achar os geradores de um subgrupo H de um determinado grupo finito G com uma
função oráculo f definida em G tal que f (a) = f (b) se, e somente se, aH = bH para todo
a, b ∈ G. O PSE em grupos abelianos é resolvido eficientemente num computador quântico. O algoritmo para o PSE abeliano requer que o grupo finito G seja identificado com
ZN1 ×. . .×ZNk . Mostraremos que usando o algoritmo para o PSE abeliano, nós podemos
determinar o isomorfismo responsável pela identificação de G com ZN1 × . . . × ZNk de
forma eficiente. Para isto faremos algumas suposições sobre o grupo G.
1. Temos uma única representação binária para cada elemento de G e podemos reconhecer eficientemente se uma palavra binária representa um elemento de G ou
não.
2. Usando a representação binária, para qualquer a ∈ G, podemos construir um
operador linear unitário eficiente Ua , tal que, Ua : |yi → |ayi .
3. Podemos achar um conjunto gerador para G eficientemente.
4. As ordens dos geradores são potências de primos.
Para a suposição 3 veja o teorema abaixo.
T EOREMA 8.3 Seja G um grupo finito. Para qualquer inteiro t ≥ 0, a probabilidade que
t + ⌈log |G|⌉ elementos escolhidos aleatoriamente de G gerem G é dada por
1
prob{ g1 , g2 , . . . , gt+⌈log |G|⌉ = G} ≥ 1 − t para t ≥ 0.
2
Afim de entendermos a suposição 4, seja a um elemento no conjunto gerador de
G de ordem pq, onde mdc(p, q) = 1, p 6= 1 e q 6= 1. Note que podemos encontrar p e q
eficientemente utilizando o algoritmo de Shor. Então pelo algoritmo Euclidiano, podemos
encontrar inteiros r e s, tais que, rp + sp = 1. Assim, temos que
a = arp+sq = arp asq ,
92
(31)
e é fácil verificar que a ordem de arp é q e a ordem de sq é p (Mostre!). Se p e q são
potências de primos, basta substituirmos a por arp e asq , que continuamos com um conjunto gerador, caso contrário, repetimos este procedimento, agora utilizando as ordens p
e q. Façamos isto até que cada elemento no conjunto de geradores tenha ordem potência
de primo.
Para a suposição 2, já que conhecemos a ordem pq de a, podemos calcular eficientemente a−1 = apq−1 , e portanto, calcular Ua−1 .
Sabemos que se G é um grupo finito abeliano então G pode ser espresso como
uma soma direta de seus p-subgrupos de Sylow. Estes p-subgrupos de Sylow podem
ser determinados eficientemente, uma vez que conhecemos a decomposição da ordem do
grupo em seus fatores primos utilizando o algoritmo de Shor. Seja então G = Gp1 ⊕
. . . ⊕ Gpl onde Gpi é um pi -subgrupo de Sylow de G com pi primos distintos, para todo
i = 1, . . . , l. Considere o conjunto Sj formado por todos os elementos no conjunto
gerador de G cujas ordens são potências do primo pj . Veremos na proposição a seguir, a
importância de termos definido o conjunto Sj desta forma .
P ROPOSIÇÃO 8.2 Se G = Gp1 ⊕ . . . ⊕ Gpl onde Gpi é um pi -subgrupo de Sylow de G
para todo i = 1, . . . , l e p1 , . . . , pl são primos distintos, então Sj gera Gpj .
Demonstração: Para cada a ∈ Sj , seja Ka = hai. Pelo exercício (8.5), nós temos
Ka = Kp1 ⊕ . . . ⊕ Kpl onde Kpi ≤ Gpi para todo i = 1, . . . , l. Como Ka é um pj -grupo,
devemos ter Ka ≤ Gpj , o que implica que Sj ⊂ Gpj , portanto,hSj i ⊂ Gpj . Agora vamos
mostrar que Gpj ⊂ hSj i. De fato, se g ∈ Gpj então |g| = pαj para algum inteiro positivo
α. Por outro lado, g ∈ G, então g = aα1 1 . . . aαk k com ai no conjunto de geradores de G
para todo i = 1, . . . , k. Como |g| = pαj , devemos ter |aαi i | = pαj i ∀ i = 1, . . . , k. Mas isto
implica que g ∈ Sj , logo, Gpj ⊂ hSj i e isto demonstra a proposição 8.2.
A proposição 8.2 nos diz como achar um conjunto de geradores para cada psubgrupo de Sylow de G. Então, podemos obter uma decomposição para G tomando
o produto das decomposições dos p-subgrupos de Sylow de G. Desta forma, o problema
de achar uma decomposição para G resume-se ao problema de achar a decomposição para
cada p-subgrupo de Sylow de G.
O algoritmo que descreveremos logo abaixo, determina a decomposição de cada
p-subgrupo de Sylow de G, uma vez dado o seu conjunto de geradores.
Verifiquemos agora que o algoritmo DecomporSylow realmente expressa um psubgrupo de Sylow como uma soma direta de subgrupos cíclicos com ordens potências
de primos.
Observe que o subgrupo escondido K de Zkq é o conjunto
K = {x ∈ Zkq | ρ(x) = ax1 1 . . . axk k = e}
(32)
É fácil ver que a função ρ é um homomorfismo sobrejetor de Zkq em G, logo, temos
um isomorfismo entre Zkq /K e G. Assim se o conjunto {y1 , . . . , yl } gera Zkq /K, então
{ρ(y1 ), . . . , ρ(yl )} gera G.
93
Algoritmo 2 DecomporSylow
1: ENTRADA:
2: Um conjunto gerador {a1 , . . . , ak } de um p-subgrupo de Sylow de G.
r
r
3: q = max{p i , onde p i = |ai | ∀ i = 1, . . . , k}.
4: SAÍDA:
5: Um conjunto de elementos g1 , g2 , . . . , gl , l ≤ k, de Gp .
6: PROCEDIMENTO:
xk
x1
k
7: Defina ρ : Zq → G tal que (x1 , . . . , xk ) 7→ a1 . . . ak . Determine os geradores para
o subgrupo escondido K de Zkq definido pela função ρ.
k
k
8: Calcule um conjunto y1 ,. . .,yk ∈ Zq /K de geradores para Zq /K.
9: Saída é o conjunto {g(y1 ), . . . , g(yl )}.
E XERCÍCIO 8.10 Mostre que a equação (32) está correta.
E XERCÍCIO 8.11 Mostre que a aplicação ρ definida pelo algoritmo DecomporSylow é
um homomorfismo sobrejetor. Conclua então que ker(ρ) = K.
E XERCÍCIO 8.12 Mostre que Zkq /K e G são isomorfos. Sugestão: use o exercício anterior seguido do Teorema dos Isomorfismos.
Vejamos agora como podemos determinar os geradores de Zkq /K. Observe que
e1 , . . . , ek geram Zkq , onde ei é um 0, 1-vetor com 1 na i-ésima coordenada. Além disso,
seja M = qI, onde I é a matriz identidade de ordem k. Não há dificuldades em demonstrar
que
x1 e1 + . . . + xk ek = 0 (em Zkq ) ⇔ x ∈ intcol(M ).
(33)
E XERCÍCIO 8.13 Mostre que a expressão (33) está correta.
Agora note que, como K ≤ Zkq e {e1 , . . . , ek } gera Zkq , temos que
{e1 + K, . . . , ek + K}
gera Zkq /K (veja exercício (8.3)). Observe também que
v1 (e1 + K) + . . . + vk (ek + K) = K
(34)
se, e somente se, Iv ∈ K, onde I é a matriz identidade e v = (v1 , . . . , vk )T .
E XERCÍCIO 8.14 Verifique que a equação dada em (34) está correta.
P ROPOSIÇÃO 8.3 Seja A a matriz cujas colunas são os geradores do subgrupo escondido
K. Então Iv ∈ K se, e somente se, v ∈ intcol([M |A]), onde


q ··· 0 |


[M |A] =  ... . . . ... |
A ,
0 ··· q |
94
Demonstração: Note que, Iv ∈ K se, e somente se, existe um vetor x tal que
⇔
⇔
⇔
⇔
⇔
⇔
Iv = Ax
Iv = IAx
I(v − Ax) = 0
v − Ax ∈ intcol(M ) (veja equação (33))
v − Ax = α1 qe1 + . . . + αk qek
v = α1 qe1 + . . . + αk qek + Ax
v ∈ intcol([M |A]).
Aplicando o teorema 8.2 ao conjunto de geradores
{ei + K | i = 1, . . . , k}
(35)
de Zkq /K e fazendo M ′ = [M |A], nós obtemos y1 ,. . . ,yl ∈ Zkq /K tal que
Zkq /K = hy1 i ⊕ . . . ⊕ hyl i
(36)
como desejado.
E XEMPLO 8.1 Veremos agora uma aplicação do algoritmo DecomporSylow no grupo
×
Z×
35 . O grupo Z35 é gerado pelo conjunto {8, 16} (verifique!). Podemos verificar facilmente que |8| = 22 e 26 = 2 × 3. Como o mdc(2, 3) = 1, pelo algoritmo de Euclides,
podemos encontrar inteiros r e s tais que 2r + 3s = 1. Assim, temos que
r
s
26 = 262r+3s = (262 ) (263 ) .
(37)
Note que |262 | = 3 e |263 | = 2, logo, se substituírmos 26 por 262 ≡ 11 mod 35 e
263 ≡ 6 mod 35, obtemos um novo conjunto gerador para Z×
35 dado por
Z×
35 = h6, 8, 11i ,
(38)
onde as ordens dos elementos são todas potências de primos.
Agora, vejamos quantos subgrupos de Sylow existem em Z×
35 a menos de subgrupos conjugados. Como φ(35) = 24 = 23 × 3, os subgrupos de Sylow de Z×
35 devem ter
×
3
ordens 2 e 3 apenas. Vamos denominar os subgrupos de Sylow de Z35 de ordens 23 e 3
por G2 e G3 , respectivamente. Sejam S2 = {6, 8} e S3 = {11} os conjuntos formados
pelos geradores de Z×
35 cujas ordens são potências de 2 e 3, respectivamente. Segue da
proposição 8.2 que
G2 = hS2 i e G3 = hS3 i .
(39)
Como o grupo G3 é cíclico de ordem potência de primo, basta aplicarmos o algoritmo
DecomporSylow ao grupo G2 , e depois tomarmos a soma direta com G3 para obtermos a
decomposição desejada.
Para aplicarmos o algoritmo DecomporSylow ao grupo G2 , devemos passar como
entrada para o algoritmo o conjunto de geradores {6, 8} e q = max{|6|, |8|} = 4. Considere então a função ρ : Z2q → G2 tal que ρ((x1 , x2 )) = 6x1 × 8x2 mod 35. Segue da
expressão (32) que o subgrupo escondido K de Z24 é o conjunto
K = {x ∈ Z24 | ρ(x) = 6x1 × 8x2 = 1}.
95
(40)
Após alguns cálculos, vemos que
K = h(2, 0)i .
(41)
4 0 | 2
Agora, seja [M |A] =
dada como na proposição 8.3. Então, basta
0 4 | 0
aplicar o teorema 8.2 ao conjunto de geradores e1 + K , e2 + K de Z24 e M ′ = [M |A].
| {z } | {z }
a1
a2
Sejam
D=
(42)

0 0 34
eV = 1 1 0 
1 0 2
(43)
2 0 0
0 4 0
a forma normal de Smith da matriz M ′ ,
U=
1 0
33 1

′
matrizes unimodulares tais que U M ′ V = D. Observe que gi = ai ∀ i = 1, 2. Logo o
conjunto {g1 , g2 } dado por
′
g1 = a1 = a1 + a02 = (1, 0) + K,
′
g2 = a2 = a33
1 + a2 = (3, 1) + K
(44)
é tal que
Z24 /K = hg1 i ⊕ hg2 i .
(45)
G2 = hρ(g1 )i ⊕ hρ(g2 )i .
(46)
Como a função ρ : Z24 /K → G2 é um isomorfismo, temos
Então,
ρ(g1 ) = ρ((1, 0)) = 61 × 80 mod 35 = 6,
ρ(g2 ) = ρ((3, 1)) = 63 × 81 mod 35 = 13
(47)
e
G2 = h6i ⊕ h13i .
(48)
Z×
35 = h11i ⊕ h6i ⊕ h13i .
(49)
Portanto,
E XERCÍCIO 8.15 Verifique que as matrizes U e V dadas no exemplo (8.1) são de fato
unimodulares.
Podemos generalizar o algoritmo acima trabalhando com todos os p-subgrupos de
Sylow simultaneamente. De fato, suponha que o conjunto
{ai1 , . . . , aiki }
96
(50)
gere o grupo Gpi . Então, seja qi = max{pi rj , com pi rj = |aij | ∀ j = 1, . . . , ki }. Em
seguida, defina ρ : Zkqi1 × . . . × Zkqll → G que leva
(x11 , . . . , x1k1 , . . . , xl1 , . . . , xlkl ) 7→ ρ(x) =
l
Y
xik
xi1
. . . aiki i .
ai1
(51)
i=1
Agora basta prosseguir como antes. Na prática deseja-se evitar trabalhar com todos os
p-subgrupos de Sylow de uma única vez, pois, desta forma precisaríamos construir uma
super rede quântica para resolver PSE no cálculo dos geradores para Zkq11 × . . . × Zkqll /K,
onde K é o subgrupo escondido definido por ρ, além disso, precisaríamos de uma matriz
com tamanho muito grande na aplicação do teorema 8.2. Observe também que para cada
primo p, ao invés de usar Zkq , nós poderíamos ter usado Zpt1 × Zpt1 × . . . × Zptk .
E XERCÍCIO 8.16 Mostre que a aplicação ρ definida pela expressão (51) é um homomorfismo.
9. Notas Bibliográficas
As referências mais básicas de computação quântica que recomendamos são [Nielsen & Chuang 2000,
Portugal et al. 2004, Aharonov 1998, Steane 1998, Rieffel & Polak 2000, Kitaev et al. 2002].
A seção sobre portas e circuitos quânticos se baseou nas referências [Nielsen & Chuang 2000,
Portugal et al. 2004]. Outras referências relevantes são [Barenco et al. 1995b, Barenco et al. 1995a,
Barenco 1995, Cleve et al. 1998].
A seção sobre transformada de Fourier se baseou nas referências [Nielsen & Chuang 2000,
Portugal et al. 2004]. Outras referências relevantes são [Coppersmith 1994, Barenco et al. 1996,
Griffiths & Niu 1996, Hales & Hallgren 2000, Cleve & Watrous 2000, Coppersmith 1994,
Lomont 2004a, Cleve 2004].
A seção sobre o algoritmo de Shor se baseou nas referências [Shor 1997, Lavor et al. 2003].
Outras referências relevantes são [Ekert & Jozsa 1996, Vandersypen et al. 2001, Beckman et al. 1996].
As seções sobre cálculo de fase e do algoritmo de Kitaev se basearam nas referências [Nielsen & Chuang 2000, Kitaev 1995].
O algoritmo de Watrous foi descrito pela primeira vez em [Watrous 2001]. Outras
referências relevantes são [Ivanyos et al. 2003, Fenner & Zhang 2004].
O algoritmo para decompor grupos abelianos finitos foi descrito pela primeira
vez em [Cheung & Mosca 2001]. Outra referência relevante é [Mosca 1999a]. Algumas
das principais referências sobre o problema do subgrupo são [Lomont 2004b, Jozsa 2000,
Lomonaco & Kauffmann 2002, Ettinger & Hoyer 1999, Grigni et al. 2001]. A prova do
teorema 8.1 pode ser encontrada na referência [Kannan & Bachem 1979] e a do teorema
8.3 em [Lomont 2004b].
Referências
D. Aharonov. Quantum computation. In Dietrich Stauffer, editor, Annual Reviews of
Computational Physics, volume 6. World Scientific, 1998.
A. Barenco. A universal two bit gate for quantum computation. 449:679–683, 1995.
97
A. Barenco, D. Deutsch, and R. Jozsa. Conditional quantum dynamics and logic gates.
Phys. Rev. Lett., 74:4083–4086, 1995.
A. Barenco, A. Ekert, K.-A. Suominen, and P. Törmä. Approximate quantum Fourier
transform and decoherence. Phys. Rev. A, 54:139–146, 1996.
D. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator,
J. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Phys.
Rev. A, 52:3457, 1995.
D. Beckman, A. N. Chari, S. Devabhaktuni, and J. Preskill. Efficient networks for quantum factoring. Phys. Rev. A, 54:1034, 1996.
K.K.H. Cheung and M. Mosca. Decomposing finite abelian groups. J. Quantum Inf.
Comp., 1(3):26–32, 2001.
R. Cleve.
A note on computing Fourier transforms by quantum programs.
http://pages.cpsc.ucalgary.ca/~cleve, 2004.
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proc.
R. Soc. Lond. A, 454:339–354, 1998.
R. Cleve and J. Watrous. Fast parallel circuit for the quantum Fourier transform. In 41th
Annual Symposium on Foundations of Computer Science, page 526, 2000.
D. Coppersmith. An approximate Fourier transform useful in quantum factoring. Technical Report IBM Research Report 19642, IBM, 1994.
A. Ekert and R. Jozsa. Notes on quantum factoring. 68:733–753, 1996.
M. Ettinger and P. Hoyer. On quantum algorithms for noncommutative hidden subgroups.
In Proc. 16th STACS, pages 478–487, 1999. Final version in Adv. in Appl. Math. .
Stephen Fenner and Yong Zhang. Quantum algorithms for a set of group theoretic problems, 2004.
R. B. Griffiths and C.-S. Niu. Semiclassical Fourier transform for quantum computation.
Phys. Rev. Lett., 76:3228, 1996.
M. Grigni, L. Schulman, M. Vazirani, and U. Vazirani. Quantum mechanical algorithms
for the nonabelian hidden subgroup problem. In Proc. 33th STOC, pages 68–74,
2001.
L. Hales and S. Hallgren. An improved quantum Fourier transform algorithm and applications. In Proc. 41st Ann. Symp. on Foundations of Computer Science, pages
515–525, Redonda Beach, California, November 2000.
G. Ivanyos, F. Magniez, and M. Santha. Efficient quantum algorithms for some instances
of the non-abelian hidden subgroup problem, 2003. to be published in I. J. Found.
Comput. Sci.
R. Jozsa. Quantum factoring, discrete logarithms and the hidden subgroup problem, 2000.
Prepared for IEEE Computing in Science and Engineering.
R. Kannan and A. Bachem. Historical notes on the Fast Fourier Transform. SIAM Journal
on Computing, 8(4):499–507, 1979.
A. Kitaev. Quantum measurements and the abelian stabilizer problem, 1995.
98
A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and quantum computation. Graduate studies in mathematics. American Mathematical Society, Providence, Rhodes
Island, 2002.
C. Lavor, L.R.U. Manssur, and R. Portugal. Shor’s algorithm for factoring large integers.
quant-ph/0303175, 2003.
S.J. Lomonaco Jr. and L.H. Kauffmann. Quantum hidden subgroup problems: a mathematical perspective. quant-ph/0201095, 2002.
C. Lomont. A quantum Fourier transform algorithm.
ph/0404060, 2004.
Los Alamos arXiv, quant-
C. Lomont. The hidden subgroup problem: review and open problems.
ph/0411037, 2004.
quant-
M. Mosca. Quantum Computer Algorithms. PhD thesis, University of Oxford, 1999.
M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK, 2000.
R. Portugal, C.C. Lavor, L.M. Carvalho, and N. Maculan. Uma Introdução à Computação
Quântica, volume 8 of Notas em Matemática Aplicada. SBMAC, 2004.
E.G. Rieffel and W. Polak. An introduction to quantum computing for non-physicists.
ACM Comput. Surv., 32(3):300–335, 2000.
P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms
on a quantum computer. SIAM J. Comput., 26:1484–1509, 1997.
A. M. Steane. Quantum computing. 61:117, 1998.
Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni,
Mark H. Sherwood, and Isaac L. Chuang. Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature, 414:883–886,
December 2001.
J. Watrous. Quantum algorithms for solvable groups. Proceedings of the 33rd ACM
Symposium on Theory of Computing, pages 60–67, 2001.
99
100