Topicos especiais engenharia da computação aula 5

Prévia do material em texto

TÓPICOS ESPECIAIS EM 
ENGENHARIA DA 
COMPUTAÇÃO 
AULA 5 
 
 
 
 
 
 
 
 
 
Prof. Luciano Frontino de Medeiros 
 
 
2 
CONVERSA INICIAL 
Nesta aula, serão apresentados os conceitos de algoritmos quânticos e 
como eles se posicionam em relação às classes de complexidade 
computacional. O algoritmo de busca de Grover será explicado, mostrando-se 
com um exemplo com que a aplicação de portas é feita para se alcançar um item 
em um vetor qualquer. 
Em seguida, será explicado o conceito de fase de um estado, mostrando 
que um estado quântico apresenta um ângulo de rotação no espaço complexo. 
Por fim, serão apresentadas as portas controladas que generalizam as portas de 
um q-bit, de forma que contenham um q-bit de controle. As portas controladas 
são importantes tanto para o entendimento de algoritmos como da Transformada 
Quântica de Fourier e da estimativa de fase. 
TEMA 1 – ALGORITMOS QUÂNTICOS 
A ideia central por trás do desenvolvimento de algoritmos quânticos está 
em obter, a partir de um novo paradigma de computação, resultados melhores e 
mais eficientes do que a abordagem tradicional dos chamados algoritmos 
clássicos. 
Em termos de complexidade computacional, com os algoritmos clássicos 
existe a dificuldade de se obter soluções de uma série de problemas em tempo 
polinomial, são os chamados NP-completos, algoritmos que permitem a 
resolução dos problemas, mas necessitam de tempo exponencial. Espera-se 
que os algoritmos quânticos proporcionem as soluções em tempo polinomial dos 
problemas NP-completos pelo uso das características de processamento 
exponencial e paralelismo. 
De acordo com Nielsen; Chuang (2005), as duas classes de problemas 
mais importantes são denominadas P (Polynomial) e NP (Non-deterministic 
Polynomial). A classe P é considerada a dos problemas que podem ser 
resolvidos de forma rápida em um computador clássico. Já a NP se refere à 
classe de problemas em que as soluções podem ser verificadas eficientemente 
em um computador clássico. Se um problema está em NP, não é requerido que 
exista um algoritmo de tempo polinomial que possa resolvê-lo; é necessária a 
existência de um algoritmo que possa testar uma solução e verificar se é correta 
em tempo polinomial (Aharonov, 1998). 
 
 
3 
Segundo Cormen et al. (2002), qualquer problema em P está em NP, pois 
pode ser resolvido em tempo polinomial sem necessidade de verificação. Porém, 
acredita-se que P seja diferente de NP devido à existência dos problemas NP-
completos, que seriam considerados os problemas mais difíceis dentro da classe 
NP, aos quais se reduziriam os problemas NP. Se qualquer problema NP-
completo pudesse ser resolvido em tempo polinomial, então todo problema NP 
teria uma solução em tempo polinomial, ou seja, P=NP. Entretanto, não foi 
descoberto nenhum algoritmo de tempo polinomial para resolver problemas NP-
completos (Cormen et al., 2002). 
Outro aspecto relevante a ser considerado, refere-se ao caráter 
determinístico na obtenção de soluções dos problemas. Preskill (1998), 
comenta, inclusive, sobre a possibilidade de um computador clássico simular um 
circuito quântico. Entretanto, a necessidade de armazenamento cresce 
exponencialmente com o aumento de q-bits no circuito, mas se a condição de 
determinismo for relaxada, aceitando-se soluções probabilísticas com alguma 
margem de erro, o desempenho dos algoritmos quânticos é superior aos 
clássicos em certa classe de problemas. 
Nielsen; Chuang (2005), mostram que certos tipos de problemas podem 
ser resolvidos utilizando-se algoritmos aleatórios capazes de resolver em tempo 
polinomial, aceitando uma probabilidade de erro limitada. Essa classe de 
problemas é denominada BPP (Bounded Probability Polynomial) e nela podem 
ser encontrados os algoritmos genéticos ou as redes neurais artificiais, por 
exemplo. Aharonov (1998), coloca que a margem de aceitação de uma solução 
de um problema na classe BPP seria acima de 2/3. 
Existe a contrapartida da classe BPP na computação quântica, a BQP 
(Bounded Quantum Polynomial), que é definida como a classe de algoritmos 
quânticos que resolvem os problemas de forma eficiente em um computador 
quântico, aceitando-se uma margem de erro (Nielsen; Chuang, 2005). Todavia, 
ainda não se sabe qual é a relação entre a classe BQP e as classes P e NP. 
Os computadores quânticos podem resolver problemas P com eficiência, 
mas existem problemas fora de P que eles não poderiam resolver com a mesma 
eficiência. O que está bem claro, é que “a teoria da computação quântica 
apresenta interessantes e significativos desafios às noções tradicionais da 
computação” (Nielsen; Chuang, 2005). Isso é importante, à medida que tal 
modelo teórico da computação quântica é experimentalmente realizável, pois a 
 
 
4 
teoria está em concordância com a forma como a natureza funciona. Não fosse 
este o caso, “a computação quântica seria uma mera curiosidade matemática” 
(Nielsen; Chuang, 2005). 
Figura 1 – Relação entre as classes de complexidade computacional P, BQP e 
NP 
 
Fonte: Adaptado de Nielsen; Chuang, 2005. 
Com o intuito de aproveitar as propriedades de superposição e 
emaranhamento, permitindo, por sua vez, uma eficiência maior em relação a 
algoritmos clássicos em termos de complexidade, alguns algoritmos quânticos 
foram propostos. A combinação do paralelismo exponencial e a interferência 
(proporcionada pelo fenômeno da superposição) tornam a Computação 
Quântica mais poderosa e detentora de um papel importante nos algoritmos 
quânticos (Aharonov, 1998). 
O algoritmo de Deutsch mostrado anteriormente, ilustrou o uso da 
superposição para permitir, por meio de uma única avaliação da função, 
conhecer a característica desta, possibilitando saber simultaneamente os dois 
valores de avaliação da função 𝑓𝑓(𝑥𝑥). Apesar dos esforços, a quantidade de 
algoritmos quânticos desenvolvidos até agora permanece pouca (Steane, 1997). 
De acordo com Nielsen; Chuang (2005), os algoritmos quânticos existem 
organizados em três classes distintas: 
 
 
 
5 
1. algoritmos quânticos de busca. 
2. algoritmos quânticos baseados na Transformada de Fourier. 
3. simulações quânticas. 
TEMA 2 – BUSCA DE GROVER (FORMALISMO) 
Grover (1996) propôs um algoritmo de busca que permite encontrar um 
elemento em um espaço de busca contendo N elementos, sem nenhum 
conhecimento prévio sobre a estrutura da informação contida nele e com 
eficiência ( )O N . Os algoritmos clássicos de busca apresentam complexidade 
( )O N e, portanto, o algoritmo de Grover apresenta ganho quadrático de 
velocidade nesse tipo de busca. Esse ganho quadrático pode ser utilizado na 
aceleração das soluções de problemas NP-completos (Nielsen; Chuang, 2005). 
A busca mediante o algoritmo de Grover é feita de forma a aumentar a 
probabilidade de se encontrar o elemento desejado dentro do espaço de q-bits. 
O algoritmo altera, portanto, as amplitudes de todas as possíveis soluções por 
meio da aplicação de operadores específicos, resultando em um processo 
denominado amplificação de amplitude quântica (Brassard; Hoyer; Tapp, 1998). 
O algoritmo de Grover opera sobre um registrador de n q-bits, iniciando 
no estado |00...0〉. Da mesma forma que o algoritmo de Deutsch, existe um 
segundo q-bit auxiliar, no estado (| 0 |1 ) / 2〉− 〉 
0
| 0 |1| | 00...0
2
ψ 〉− 〉 〉 = 〉   
 
Com base em Nielsen e Chuang (2005), a seguir são listadas as três 
operações necessárias para se efetuar a busca com o algoritmo de Grover: 
1. Operação de transformação de Hadamard 
Coloca todos os elementos possíveis de busca {0..N-1} em superposição: 
1
1 1/ 2
0
1| |
N
x
x
N
ψ
−
=
〉 = 〉∑ 
2. Aplicação do oráculo 
Efetua a seguinte transformação sobre o estado |ψ1〉 
: | | | | ( )fU x y x y f x〉 〉 → 〉 ⊕ 〉 
A função f(x) retorna 1, caso o elemento buscado seja encontrado, senão 
retorna 0. O oráculo pode ser representado também como 
(1)(2) 
(3) 
 
 
6 
( )| 0 |1 | 0 |1: | (-1) |
2 2
f x
fU x x
〉− 〉 〉− 〉   〉 → 〉      
 
Como o q-bit auxiliar não muda, convenciona-se o uso apenas do primeiro 
q-bit, ( ): | (-1) |f xfU x x〉 → 〉 . 
O oráculo então marca a solução do problema de busca, mudando a sua 
fase. 
3. Aplicação de um deslocamento de fase 
Feita no registrador quântico |x〉, antecedido e sucedido de 
transformações Hadamard. O deslocamento de fase é feito em todos os estados 
da base computacional, menos o estado |0〉. A operação de deslocamento é 
representada utilizando-se o produto externo para o estado |0〉 e a matriz 
identidade, da forma 2 | 0 0 | I〉〈 − , de maneira que os três operadores combinados,
| (2 | 0 0 | ) |x H I H x〉 → 〉〈 − 〉 podem ser representados pelo operador único
2 | | Iψ ψ〉〈 − . 
A iteração de Grover, é representada pela combinação dos passos 2 e 
3, sendo representada por (2 | | ) fG I Uψ ψ= 〉〈 − e deve ser aplicada 
iterativamente para aumentar a probabilidade de obtenção do elemento 
desejado, ao se efetuar a medida do registrador |x〉. Geometricamente, a iteração 
de Grover executa reflexões do vetor em relação ao vetor inicial, resultando 
numa rotação no espaço de busca (Nielsen; Chuang, 2005). 
TEMA 3 – BUSCA DE GROVER (EXEMPLO) 
Utilizando um exemplo para explicar o funcionamento do algoritmo de 
Grover para um circuito quântico de três q-bits, o número de estados possíveis 
será 𝑁𝑁 = 23 = 8. O conjunto de estados é, portanto, 
(|0⟩, |1⟩, |2⟩, |3⟩, |4⟩, |5⟩, |6⟩, |7⟩). Pretende-se buscar o estado |6⟩ no conjunto, 
começando com o estado inicial e a aplicação das portas Hadamard aos três q-
bits. O estado inicial inicia, então, com (será ignorado, para fins de explicação do 
exemplo, o q-bit auxiliar 0| | 000 |ψ 〉 = 〉 = 〉0 . 
Com a aplicação das portas Hadamard, tem-se a superposição dos 
estados dos q-bits, ( )
7
1
0
1 1| | | 0 |1 | 2 | 3 | 4 | 5 | 6 | 7
2 2 2 2x
xψ
=
〉 = 〉 = 〉+ 〉+ 〉+ 〉+ 〉+ 〉+ 〉+ 〉∑ . 
(4) 
(5) 
(6) 
(7) 
 
 
7 
Figura 2 – Primeiro passo do Algoritmo de Grover 
 
0 1 2 3 4 5 6 7 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
A seguir, na Figura 3, estão representados o circuito e os estados do 
registrador, com as respectivas amplitudes. Nota-se que todos os estados 
possuem igual amplitude (1/ 2 2 0,354≅ ) e probabilidade (1/ 8 0,125= ). O 
próximo passo será aplicar o oráculo a essa superposição e ele deverá, então, 
marcar o estado a ser encontrado mudando o sinal da amplitude respectiva ao 
estado (Figura 2). A função 𝑓𝑓(𝑥𝑥) = 0 para todos os estados, exceto 𝑓𝑓(6) = 1: 
( )
7
( )
2
0
1 1| ( 1) | | 0 |1 | 2 | 3 | 4 | 5 | | 7
2 2 2 2
f x
x
xψ
=
〉 = − 〉 = 〉+ 〉+ 〉+ 〉+ 〉+ 〉 〉+ 〉∑ 6− 
Figura 3 – Passo do oráculo do Algoritmo de Grover 
 
0 1 2 3 4 5 6 7 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
+0,354 
0,000i 
-0,354 
0,000i 
+0,354 
0,000i 
O passo seguinte é o deslocamento de fase, sendo aplicado o operador 
2 | | Iψ ψ〉〈 − ao estado obtido após a aplicação do oráculo. Na Figura 4, observa-
-se o circuito com o deslocamento de fase aplicado e o efeito no registrador 
quântico. 
 
 
 
8 
Figura 4: Passo do deslocamento de fase do Algoritmo de Grover 
 
0 1 2 3 4 5 6 7 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.884 
0.000i 
+0.177 
0.000i 
 
Construindo o operador de deslocamento de fase, fazendo-se o produto 
externo do estado ψ1, 
[ ]1 1
1
1
1
11 1| | . 1 1 1 1 1 1 1 1
12 2 2 2
1
1
1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 11
1 1 1 1 1 1 1 18
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
ψ ψ
 
 
 
 
 
 〉〈 = = 
 
 
 
 
  
 
 
 
 
 
 =  
 
 
 
 
  
 
O operador de deslocamento de fase é, portanto, 
 
 
9 
1 1
1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 11 12 | |
1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 14 4
1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3
I Iψ ψ
−   
   −   
   −
   −  〉〈 − = − =   −
  
−  
   −
  
−     







 Aplicando-se o operador ao vetor ψ2 produzido pela aplicação do oráculo, 
obtém-se 
3 1 1 2
3 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1
1 1 3 1 1 1 1 1 1
1 1 1 3 1 1 1 1 11 1(2 | | ) .
1 1 1 1 3 1 1 1 14 2 2
1 1 1 1 1 3 1 1 1
1 1 1 1 1 1 3 1 1
1 1 1 1 1 1 1 3 1
2
2
2
21 1
28 2
2
2
Iψ ψ ψ ψ
−   
   −   
   −
   −   = 〉〈 − = =   −
   
−   
   − −
   
−      
 
 
 
 
 
 = = 
 
 
 
 
  
10
( )
1
1
1
1 1 | 0 |1 | 2 | 3 | 4 | 5 | | 7
14 2 4 2
1
1
 
 
 
 
 
  = 〉+ 〉+ 〉+ 〉+ 〉+ 〉 + 〉+ 〉 
 
 
 
 
  
5 6
5
 
As amplitudes de todos os estados foram reduzidas (1/ 4 2 0,177≅ ), 
exceto a amplitude do estado procurado, que foi aumentada (5 / 4 2 0,883≅ ). 
Antes do deslocamento de fase, as probabilidades de obtenção dos estados 
eram iguais (a probabilidade é igual ao quadrado da amplitude e, inicialmente, 
estava em 12,5% para todos os estados). Após, a probabilidade de obtenção do 
estado |6〉 aumentou para aproximadamente 77%, enquanto para os estados 
restantes ela foi reduzida para, aproximadamente, 3%. 
A iteração de Grover pode ser novamente aplicada, ou seja, o passo do 
oráculo mais o deslocamento de fase (Figura 5). Após o passo do oráculo, 
tem-se novamente o estado procurado com o sinal invertido, 
 
 
10 
( )4 3
1 | 0 |1 | 2 | 3 | 4 | 5 | | 7
4 2f
Uψ ψ= = 〉+ 〉+ 〉+ 〉+ 〉+ 〉 − 〉+ 〉5 6 
Repetindo-se o passo do deslocamento de fase (Figura 6), tem-se o 
estado ψ5 
5 1 1 4
3 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1
1 1 3 1 1 1 1 1 1
1 1 1 3 1 1 1 1 11 1(2 | | ) .
1 1 1 1 3 1 1 1 14 4 2
1 1 1 1 1 3 1 1 1
1 1 1 1 1 1 3 1 5
1 1 1 1 1 1 1 3 1
2
2
2
21
216 2
2
2
Iψ ψ ψ ψ
−   
   −   
   −
   −   = 〉〈 − = =   −
   
−   
   − −
   
−      
− 
 − 
 −
 − = −

−


− 
22
( )
1
1
1
11 1 | 0 |1 | 2 | 3 | 4 | 5 | | 7
18 2 8 2
1
1
− 
 − 
 −
 − = = − 〉− 〉− 〉− 〉− 〉− 〉 + 〉− 〉  −
  
−  
  
  
−   
11 6
11
 
Figura 5 – Nova aplicação do oráculo Uf 
 
0 1 2 3 4 5 6 7 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.177 
0.000i 
+0.884 
0.000i 
+0.177 
0.000i 
 
Agora, a probabilidade do estado procurado |6〉 aumentou para 
aproximadamente 94,5%, enquanto as probabilidades dos estados restantes 
diminuíram para 0,7%. Efetuando-se a medida do registrador quântico, a 
probabilidade de encontrar o estado procurado é bastante alta em relação aos 
 
 
11 
outros. Na Figura 5 observa-se o circuito com o operador de medida, mostrando 
o colapso do estado superposto ψ5 para o único estado |6〉. 
Figura 6 – Segunda aplicação do deslocamento de fase 
 
0 1 2 3 4 5 6 7 
-0.088 
0.000i 
-0.088 
0.000i 
-0.088 
0.000i 
-0.088 
0.000i 
-0.088 
0.000i 
-0.088 
0.000i 
+0.972 
0.000i 
-0.088 
0.000i 
 
Analisando a execução do algoritmo, para encontrar o estado buscado 
foram necessárias duas iterações de Grover mais a aplicação de Hadamard. O 
algoritmo clássico procederia à busca sequencial em seis iterações de 
comparação, lembrando que o algoritmo de Grover atua sobre um conjunto de 
estados sem estrutura. 
A vantagem do algoritmo de Grover para os clássicos começa a ficar 
maior para circuitos com mais q-bits, com a complexidade sendo reduzida em 
média de forma quadrática ( ( )O N ), em relação aos algoritmos clássicos (em 
média, ( )O N ). 
Figura 7 – Medida do registrador quântico, mostrando o estado desejado 
 
0 1 2 3 4 5 6 7 
0.000 
0.000i 
0.000 
0.000i 
0.000 
0.000i 
0.000 
0.000i 
0.0000.000i 
0.000 
0.000i 
+1.000 
0.000i 
0.000 
0.000i 
 
As operações referentes ao algoritmo de Grover podem ser reduzidas a 
portas quânticas usuais (Nielsen; Chuang, 2005). 
 
 
12 
TEMA 4 – CONCEITO DE FASE QUÂNTICA 
O uso do termo fase é bastante comum em mecânica quântica e está 
relacionado com o avanço ou o atraso de uma onda em relação a outra como 
ocorre, por exemplo, em óptica quântica, onde a reflexão de uma onda de luz 
introduz um atraso de fase em relação à onda original. 
Estados em superposição podem apresentar diferença de fase, chamada 
de fase relativa. A Figura 8 mostra duas ondas em fase e depois deslocadas 
entre si, em um ângulo específico. 
Figura 8 – Ondas superpostas em fase (a) e deslocadas de um ângulo (b) 
 
(a) 
 
 
(b) 
Por exemplo, sejam dois estados quânticos |0⟩+|1⟩
√2
 e |0⟩−|1⟩
√2
. No primeiro, a 
amplitude de |1⟩ é 1/√2, enquanto no segundo estado a amplitude de |1⟩ é 
−1/√2. Apesar de a magnitude ser a mesma, ela se difere pelo sinal negativo. 
Quando representados no espaço complexo ℂ, os vetores mostram 
diferentes orientações. Pode-se notar que na representação no espaço 
complexo ℂ, os vetores estão deslocados por um ângulo de 180 graus (Figura 
 
 
13 
9). Após a medida de um estado quântico, no entanto, perde-se a informação de 
fase de um q-bit. 
Figura 9 – Orientações dos estados +|1⟩ e −|1⟩ no espaço complexo 
 
+|𝟏𝟏⟩ 
 
−|𝟏𝟏⟩ 
A fase de um estado quântico pode ser atribuída pelo termo 𝑒𝑒𝑖𝑖𝑖𝑖 
aparecendo como amplitude, onde 𝜃𝜃 é o ângulo do vetor em relação ao eixo real 
no espaço complexo (Figura 10). Pela fórmula de Euler, 𝑒𝑒𝑖𝑖𝑖𝑖 = 𝑐𝑐𝑐𝑐𝑐𝑐 𝜃𝜃 + 𝑖𝑖 𝑐𝑐𝑖𝑖𝑠𝑠 𝜃𝜃. 
Figura 10 – Representação de um vetor no estado complexo 
 
Algumas portas quânticas podem alterar a fase de um estado: 𝑍𝑍 (180 
graus), 𝑆𝑆 (90 graus) ou 𝑇𝑇 (45 graus). Existem também as portas de deslocamento 
 
 
14 
de fase, as quais permitem rotacionar estados quânticos em um ângulo 
específico. 
Figura 11 – Portas Z, S e T e a rotação proporcionada (180°, 90° e 45°, 
respectivamente) 
 
O cálculo das amplitudes dos estados pode envolver as informações de 
fase destes. A Figura 12 mostra uma tabela de equivalência entre os ângulos 
“cheios” (divididos em 45°), com as potências complexas para cada um. 
Figura 12 – Equivalência entre ângulos e potências complexas 
 
 
 
15 
Exemplo 1: Aplicação da porta T (porta π/8). 
Faça a aplicação da porta T sobre o estado quântico |ψ0⟩ =
|0⟩+|1⟩
√2
. 
A aplicação da porta T fará com que o estado |1⟩ fique rotacionado por 
um ângulo de 45°: 
|𝜓𝜓1⟩ = 𝑇𝑇|𝜓𝜓0⟩ =
1
√2
�|0⟩ + 𝑒𝑒
𝑖𝑖𝑖𝑖
4 |1⟩� 
Exemplo 2: Aplicação da porta S (porta de fase). 
Faça a aplicação da porta T sobre o estado quântico |ψ0⟩ =
|0⟩+|1⟩
√2
. 
A aplicação da porta T fará com que o estado |1⟩ fique rotacionado por 
um ângulo de 90°: 
|𝜓𝜓1⟩ = 𝑆𝑆|𝜓𝜓0⟩ =
1
√2
�|0⟩ + 𝑒𝑒
𝑖𝑖𝑖𝑖
2 |1⟩� =
1
√2
(|0⟩ + 𝑖𝑖|1⟩) 
TEMA 5 – PORTAS CONTROLADAS 
A operação controlada permite inserir na computação quântica o conceito 
de instrução condicional da computação clássica, sendo a porta CNOT um 
exemplo de operação controlada. Considerando que existe um q-bit de controle 
e um q-bit alvo a porta CNOT faz a mesma operação da porta X, porém 
condicionada ao valor do q-bit de controle. 
O operador CNOT é uma matriz 4x4, mostrando nas duas últimas linhas 
e colunas o operador da porta X. Quando o q-bit de controle for |1⟩, o q-bit alvo 
terá suas amplitudes invertidas: 
𝐶𝐶𝑁𝑁𝐶𝐶𝑇𝑇 = �
1 0
0 1
0 0
0 0
0 0
0 0
0 1
1 0
� 
As portas de um q-bit podem ser generalizadas para as denominadas 
portas controladas U, onde U é o tipo da porta, de maneira que a operação 
somente será executada se o q-bit de controle for |1⟩. Por exemplo, as portas 
UZ, US e UT: 
𝑈𝑈𝑍𝑍 = �
1 0
0 1
0 0
0 0
0 0
0 0
1 0
0 −1
� 
 
 
16 
𝑈𝑈𝑆𝑆 = �
1 0
0 1
0 0
0 0
0 0
0 0
1 0
0 𝑖𝑖
� 
𝑈𝑈𝑇𝑇 = �
1 0
0 1
0 0
0 0
0 0
0 0
1 0
0 𝑒𝑒𝑖𝑖𝑖𝑖/4
� 
Como as portas controladas utilizam mais de um q-bit, na representação 
do operador é interessante colocar índices referentes aos q-bits de controle e ao 
alvo onde opera a porta. Por exemplo, 𝑆𝑆12 indica que o q-bit alvo é o primeiro q-
bit e o q-bit de controle é o segundo q-bit. 𝐶𝐶𝑁𝑁𝐶𝐶𝑇𝑇13 indica que o q-bit alvo é o 
primeiro q-bit e o q-bit de controle é o terceiro q-bit. Na representação gráfica, a 
caixa ou o símbolo são sempre o q-bit alvo (Figura 13). 
Figura 13 – Representação das portas controladas 𝑺𝑺𝟏𝟏𝟏𝟏 e 𝑪𝑪𝑪𝑪𝑪𝑪𝑻𝑻𝟏𝟏𝟏𝟏 
 
Exemplo 1: Circuito QFT de 3 q-bits. 
Represente a Transformada Quântica de Fourier para 3 q-bits utilizando 
as portas H, S e T e SWAP, conforme a Figura 14. 
Figura 14 – Circuito QFT para 3 q-bits utilizando portas controladas: 
 
 
 
17 
O circuito mostrado na Figura 13 permite implementar a Transformada 
Quântica de Fourier para 3 q-bits e contém 3 portas Hadamard, sendo duas 
portas S-controladas e uma porta T-controlada, além de uma porta SWAP. O 
operador final U pode ser representado por 𝑈𝑈 = 𝑆𝑆𝑆𝑆𝑆𝑆𝑆𝑆13𝐻𝐻1𝑆𝑆21𝐻𝐻2𝑇𝑇31𝑆𝑆32𝐻𝐻3. 
Deve-se lembrar que o circuito evolui da esquerda para a direita, mas que 
a aplicação dos operadores ocorre da direita para a esquerda. 
 
FINALIZANDO 
Nesta aula, foram explorados conceitos importantes envolvendo os 
algoritmos quânticos e a relação da classe BQP e a relação dos algoritmos 
quânticos probabilísticos com as outras classes de complexidade computacional. 
O algoritmo de busca de Grover foi apresentado e a partir da visualização de um 
exemplo, foi possível verificar como o algoritmo de Grover faz a busca de uma 
ótima maneira. 
Em seguida, o conceito de fase de um estado quântico foi abordado, 
mostrando que um estado pode ser representado no espaço complexo, 
apresentando um ângulo de rotação. Certas portas, como a S e a T, fazem com 
que um estado seja rotacionado, ou seja, que apresente uma fase com relação 
ao estado original. 
Por fim, as portas controladas foram apresentadas, mostrando que as 
portas de um q-bit podem ser generalizadas, de forma a conter também um q-bit 
de controle. Tais portas são importantes para o estudo de algoritmos, como a 
Transformada Quântica de Fourier e a estimativa de fase. 
 
 
 
 
 
 
 
 
 
18 
REFERÊNCIAS 
AHARONOV, D. Quantum Computation. In: Annual Reviews of Computational 
Physics. VI ed. [s.l.] Dietrich Stauffer World Scientific, 1998. 
BRASSARD, G.; HOYER, P.; TAPP, A. Quantum Counting. [S.l: s.n.]. 
Disponível em: <http://arxiv.org/abs/quant-ph/9805082v1>. Acesso em: 30 set. 
2019. 
CORMEN, T. et al. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2002. 
GROVER, L. K. A fast quantum-mechanical algorithm for database search. In: 
PROCEEDINGS STOC. Anais Philadelphia-PA: 1996. 
NIELSEN, M. A.; CHUANG, I. L. Computação quântica e informação 
quântica. Porto Alegre-RS: Bookman, 2005. 
PRESKILL, J. Quantum Information and Computation. Lecture Notes for 
Physics 229, 1998. 
STEANE, A. M. Quantum Computing. [S.l: s.n.]. 
 
	Conversa inicial
	TEMA 1 – ALGORITMOS QUÂNTICOS
	TEMA 2 – BUSCA DE GROVER (FORMALISMO)
	TEMA 3 – BUSCA DE GROVER (EXEMPLO)
	TEMA 4 – CONCEITO DE FASE QUÂNTICA
	TEMA 5 – PORTAS CONTROLADAS
	FINALIZANDO
	REFERÊNCIAS