Algoritmo quântico para equações linearescollier/CursosGrad/QC/Julio_Zynger_Algoritmo... · C Ampli cação de Amplitude 73 D Método de Newton 76 ... O uso de tais estruturas

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO

INSTITUTO DE MATEMÁTICA

JÚLIO ZYNGER

Algoritmo quântico para equações

lineares

Prof. Severino Collier Coutinho, D.Sc.

Orientador

Rio de Janeiro, Março de 2015

Algoritmo quântico para equações lineares

Júlio Zynger

Projeto Final de Curso submetido ao Departamento de Ciência da Computação do

Instituto de Matemática da Universidade Federal do Rio de Janeiro como parte dos

requisitos necessários para obtenção do grau de Bacharel em Informática.

Apresentado por:

Júlio Zynger

Aprovado por:

Prof. Severino Collier Coutinho, D.Sc.

Prof. Luis Menasché Schechter, D.Sc.

Prof. Franklin de Lima Marquezino, D.Sc.

RIO DE JANEIRO, RJ - BRASIL

Março de 2015

Agradecimentos

Aos meus pais, herois de minha formação e inspiração diária, que tanto bata-

lharam para que alcançasse este momento e sempre dispostos a esforços para criar

oportunidades e abrir portas para meu caminhar intelectual. Assim também, agra-

deço a meus irmãos, avós, primos, tios e familiares, que sempre zeram entender

que o futuro é feito a partir da constante dedicação no presente!

Meus agradecimentos aos amigos, em especial aqueles com os quais dividi a sala

de aula desde o ensino fundamental, médio e aos que me acompanharam durante

a graduação, irmãos na amizade que zeram parte da minha formação e que vão

continuar presentes em minha vida com certeza.

Ao professor e grande mestre Collier, singular no método de ensino, e que me

permitiu enxergar mais longe no caminho acadêmico, desde o primeiro semestre na

Universidade, assim como ao longo do curso me inspirando no estudo da Compu-

tação. Agradeço a todos os professores por me proporcionar o conhecimento, não

apenas racional, e pelo tanto que se dedicaram a mim, não somente por terem me

ensinado, mas por terem me feito aprender.

À Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) pelo

incentivo à educação através da bolsa de intercâmbio aos Estados Unidos pelo pro-

grama Ciência Sem Fronteiras.

A todos que direta ou indiretamente zeram parte de minha formação, o meu

muito obrigado.

חי ישראל Mע

i

RESUMO


Júlio Zynger

Março/2015

Orientador: Severino Collier Coutinho, D.Sc.

Algoritmos quânticos têm sido apresentados como o futuro do processamento de

informação. O aumento de eciência por vezes exponencial atrai a atenção para o

desenvolvimento de rotinas presentes em diversos campos da ciência. Neste artigo,

revisitamos um algoritmo quântico que aproxima a solução de um sistema linear

do tipo Ax = b, comparando-o com suas contra-partes clássicas e apresentando os

resultados experimentais obtidos mais recentemente.

ii

ABSTRACT


Júlio Zynger

Março/2015

Advisor: Severino Collier Coutinho, D.Sc.

Quantum algorithms have been presented as the future of information processing.

The increased eciency sometimes exponential attracts attention to the development

of routines present in many elds of science. In this article, we revisit a quantum

algorithm that approximates the solution of a linear system of type Ax = b, comparing

it with its classical counterparts and presenting the experimental results obtained

more recently.

iii

Lista de Figuras

Figura 2.1: Representação da porta lógica quântica CNOT. . . . . . . . . . . . 21

Figura 2.2: Representação da porta lógica quântica de Fredkin. . . . . . . . . . 22

Figura 2.3: Exemplos de portas quânticas comuns em circuitos. . . . . . . . . . 24

Figura 2.4: Representação de qubits através da polarização de fótons, em que

V e H representam a polarização vertical e horizontal, respecti-

vamente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

Figura 3.1: Exemplo de ajuste de curva, com pontos gerados por uma fun-

ção Seno, aproximada por curvas polinomiais (vermelho, verde,

laranja e azul representam primeiro, segundo, terceiro e quarto

graus, respectivamente) [1] . . . . . . . . . . . . . . . . . . . . . . . . 36

Figura 3.2: Circuito para resolução de sistemas lineares, adaptado de [2], em

que REC representa a rotina de cálculo do recíproco dos autova-

lores λj da matriz A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Figura 3.3: Etapa inicial de transformação dos registradores C e B. . . . . . . 42

Figura 3.4: Aplicação da simulação hamiltoniana controlada. . . . . . . . . . . 44

Figura 3.5: Circuito implementando cada passo iterativo do método de New-

ton, adaptado de [2]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

Figura 4.1: Resultados obtidos, adaptado de [3]. . . . . . . . . . . . . . . . . . . 54


iv


Figura 5.1: Circuito quântico para resolução do sistema Ax = b com A2×2 e

precisão m na etapa de rotação. De cima para baixo temos o

qubit auxiliar, três qubits para o registrador C e um qubit que

armazena ∣b⟩ . Adaptado de [2]. . . . . . . . . . . . . . . . . . . . . . 59

Figura A.1: Circuito quântico que implementa a transformada de Fourier quân-

tica, omitindo portas SWAP para reversão de ordem de qubits e

fatores de normalização ao nal, adaptado de [6]. . . . . . . . . . . 69

Figura B.1: Circuito quântico que implementa o teste SWAP. . . . . . . . . . . 71

Figura D.1: Os grácos exibem as bacias de atração das funções x2 − 2x e

x3 − 3x [7]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Figura D.2: Bacias de atração de x5 − 1, em que as zonas mais escuras re-

presentam regiões em que são necessárias mais iterações para a

convergência de aproximações. . . . . . . . . . . . . . . . . . . . . . 78

v

Sumário

Agradecimentos i

Resumo ii

Abstract iii

Lista de Figuras iv

1 Introdução 1

2 Conceitos 3

2.1 Álgebra Linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.1.1 Independência Linear e Bases . . . . . . . . . . . . . . . . . . . . 4

2.1.2 Operadores Lineares e Matrizes . . . . . . . . . . . . . . . . . . . 5

2.1.2.1 Matrizes esparsas . . . . . . . . . . . . . . . . . . . . . . 6

2.1.3 Produto hermitiano e tensor . . . . . . . . . . . . . . . . . . . . . 6

2.1.4 Autovalores e autovetores . . . . . . . . . . . . . . . . . . . . . . 8

2.1.4.1 Número de condição . . . . . . . . . . . . . . . . . . . . 9

2.1.5 Matrizes de Pauli . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.6 Adjuntos e operadores Hermitianos . . . . . . . . . . . . . . . . 10

vi

2.1.6.1 Todo operador Hermitiano é Diagonalizável . . . . . . 11

2.1.6.2 Funções de operadores . . . . . . . . . . . . . . . . . . 12

2.1.7 Espaço de Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1.8 Mecânica Quântica: evolução de Schrödinger . . . . . . . . . . . 14

2.1.9 Mecânica Quântica: medições projetivas . . . . . . . . . . . . . 15

2.1.9.1 Observáveis . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.10 Mecânica Quântica: emaranhamento . . . . . . . . . . . . . . . . 16

2.2 Computação Quântica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.1 Bits quânticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.2 Portas Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.2.1 Reversibilidade . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.2.2 A porta CNOT . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.2.3 A porta de Fredkin . . . . . . . . . . . . . . . . . . . . 22

2.2.3 Circuitos Quânticos . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2.4 Paralelismo Quântico . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.2.5 Transformada de Fourier Quântica . . . . . . . . . . . . . . . . . 26

2.2.6 Computação Quântica com Ótica Linear . . . . . . . . . . . . . 27

3 O algoritmo de Harrow, Hassidim e LLoyd 30

3.1 Caso clássico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.1 Eliminação de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.2 Método do Gradiente Conjugado . . . . . . . . . . . . . . . . . . 32

3.2 Visão Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

vii

3.3 Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.3.1 Estados estáveis de processos estocásticos . . . . . . . . . . . . . 35

3.3.2 Ajuste Quântico de Dados e Aprendizado de Máquina . . . . . 35

3.4 Preparação da entrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.4.1 Simulação hamiltoniana . . . . . . . . . . . . . . . . . . . . . . . 37

3.4.2 Codicando b em ∣b⟩ . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.5 O algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.5.1 Registradores C e B . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.5.1.1 Balanceamento de Hadamard . . . . . . . . . . . . . . 42

3.5.1.2 Evolução hamiltoniana . . . . . . . . . . . . . . . . . . 42

3.5.1.3 Transformada de Fourier . . . . . . . . . . . . . . . . . 44

3.5.1.4 Simplicação do estado . . . . . . . . . . . . . . . . . . 45

3.5.2 Inversão de autovalores . . . . . . . . . . . . . . . . . . . . . . . . 46

3.5.3 Rotação controlada . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3.5.4 Computação reversa . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.5.5 Medição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4 Resultados e trabalhos relacionados 52

4.1 Comparação de eciência: Clássico × Quântico . . . . . . . . . . . . . . 52

4.2 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2.1 Barz et. al [3] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.2.2 Pan et. al [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.2.3 Cai et. al [5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

viii

5 Implementação 57

6 Trabalhos Futuros 61

Referências 63

A Transformada de Fourier Quântica 67

B Teste SWAP 71

C Amplicação de Amplitude 73

D Método de Newton 76

D.1 Convergência Quadrática . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

D.2 Funções Complexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

E Implementação Scilab para A2×2 80

F Resultado da execução Scilab para A2×2 88

ix

Capítulo 1

Introdução

Sistemas de equações lineares são de importância ímpar em vários campos da

ciência, desde ciências naturais, engenharia e medicina até as ciências sociais, e a

resolução de tais sistemas é a base para muitas tecnologias modernas como previsão

do tempo e tomograas computadorizadas. O problema da resolução remonta a

épocas muito antigas, mas algoritmos de obtenção de valores para as variáveis em

sistemas de qualquer dimensão começaram a se desenvolver a partir do século XIX.

Hoje, os sistemas lineares envolvem petabytes de dados e, dessa forma, o número

de variáveis necessárias para modelá-los é extremamente grande, dicultando sua

resolução, e assim, cando limitados até mesmo quando são usados os melhores

supercomputadores modernos.

A capacidade de obter uma melhor eciência na execução de certas tarefas tem

atraído grande atenção e interesse no desenvolvimento de algoritmos quânticos, que

se beneciam do princípio de superposição de estados da mecânica quântica para

alcançar aumentos de velocidade até mesmo exponenciais, quando comparados com

suas contra-partes clássicas. Exemplos notáveis incluem algoritmos de simulação de

sistemas físicos quânticos e o algoritmo de fatoração de Shor.

Recentemente, Harrow, Hassidim e Lloyd [8] propuseram um algoritmo quântico

para a resolução de sistemas lineares, que como demonstraram, é exponencialmente

mais rápido do que um computador clássico na tarefa de obter valores médios e

2

propriedades da solução.

Neste trabalho, além de apresentarmos tal algoritmo, descrevendo também as ba-

ses teóricas da álgebra linear e mecânica quântica requeridas para seu entendimento,

analisaremos sua eciência e complexidade e destacaremos alguns experimentos fí-

sicos realizados que comprovam seu funcionamento.

Capítulo 2

Conceitos

Para garantirmos um melhor entendimento do conteúdo deste trabalho, apresen-

taremos aqui os conceitos básicos sobre o campo de estudo referido na execução do

algoritmo a ser apresentado a seguir. Porém, assim como os conceitos de computação

quântica requerem um conhecimento prévio da mecânica quântica, esta por sua vez

pressupõe um estudo de álgebra linear elementar. Uma vez com este conhecimento-

fundação, consideramos que o leitor leigo seja capaz de trabalhar sobre problemas

simples da área sem conhecimento prévio da matéria.

A primeira seção do capítulo introduz algumas denições e notações utilizadas

em álgebra linear, e apresenta alguns conceitos de mecânica quântica necessários

para o entendimento do algoritmo de resolução de sistemas lineares. A seção sub-

sequente apresenta conceitos de computação quântica, e estabelece paralelos com

o que já é conhecido dos métodos clássicos, iniciando-se por noções básicas sobre

os bits quânticos e levando ao entendimento mais complexo dos circuitos quânticos,

tratando ainda do caso especial conhecido como a transformada de Fourier em seu

viés quântico.

2.1. ÁLGEBRA LINEAR 4

2.1 Álgebra Linear

A álgebra linear é um ramo da matemática surgido do estudo das equações line-

ares (algébricas e diferenciais) que se utiliza de conceitos e estruturas fundamentais

da matemática como vetores, espaços vetoriais, transformações lineares e matrizes.

O uso de tais estruturas em áreas como relatividade geral, estatística, e mecânica

quântica deu a importância à álgebra linear nos dias de hoje, e é possivel notar sua

presença em vários campos do conhecimento moderno e suas aplicações no dia-dia,

passando desde as técnicas de otimização de sistemas da programação linear ao pro-

cessamento de imagens e cálculos físicos e matemáticos que possibilitam a inovação

em vários campos tecnológicos.

Os espaços vetoriais são os objetos básicos do estudo da álgebra linear, sendo

o espaço de todas as n-uplas de números complexos, conhecido por Cn, o mais

interessante para nosso estudo. Cada elemento deste espaço vetorial é chamado

vetor, comumente representado por uma matriz-coluna, e admite as operações de

adição e multiplicação por um escalar complexo.

Uma vez que a mecânica quântica é nossa principal motivação para o estudo

da álgebra linear, utilizaremos as notações da mesma para os conceitos algébricos

apresentados. A notação padrão para um vetor ca então representada por

∣ψ⟩ (2.1)

onde ψ é o rótulo do vetor (qualquer rótulo é válido, embora seja comum utilizar ψ

e φ), e a notação ∣.⟩ é usada para indicar que o objeto é um vetor.

2.1.1 Independência Linear e Bases

Um conjunto gerador de um espaço vetorial é um conjunto de vetores ∣v1⟩ , ..., ∣vn⟩

de forma que qualquer vetor ∣v⟩ no espaço vetorial pode ser escrito como a combi-

nação linear dos vetores naquele conjunto; isto é,

∣v⟩ =∑i

ai ∣vi⟩ , (2.2)


em que a1,⋯, an ∈ C. Um espaço vetorial pode ter muitos conjuntos geradores

diferentes.

Denição: Independência Linear

Um conjunto de vetores não-nulos ∣v1⟩ ,⋯, ∣vn⟩ é linearmente dependente se existe

um conjunto de números complexos a1,⋯, an com pelo menos um ai ≠ 0 tais que

a1 ∣v1⟩ + a2 ∣v2⟩ +⋯ + an ∣vn⟩ = 0. (2.3)

Dizemos que um conjunto de vetores é linearmente independente se não for line-

armente dependente.

Denição: Base

A base de um espaço vetorial V é denida como um subconjunto v1,⋯, vn dos

vetores de V que são linearmente independentes e que geram V .

Dois conjuntos de vetores linearmente independentes que geram V contêm o

mesmo número de elementos. Cada um destes conjuntos é uma base de V.

Além disso, pode ser demonstrado que todo espaço vetorial nitamente gerado

admite uma base. O número de elementos na base do espaço V é a dimensão de V.

2.1.2 Operadores Lineares e Matrizes

Uma transformação linear é uma aplicação entre dois espaços vetoriais V → W

que preserva as operações de adição e multiplicação por escalar. No caso em que

V = W , a transformação é chamada de operador linear (ou endomorsmo de V ),

sendo linear em cada entrada de seu domínio. Assim, se A é um operador linear,

então

A(∑i

ai ∣vi⟩) =∑i

aiA ∣vi⟩ . (2.4)

Todos os operadores lineares podem ser representados na forma matricial: uma

matriz A com dimensão m×n e entradas Aij representa um operador linear que leva


vetores do espaço vetorial Cn no espaço vetorial Cm, sob a multiplicação da matriz

A por um vetor de Cn. Da mesma forma, um operador linear A ∶ V →W pode ser

representado por uma matriz de forma que, se ∣v1⟩ ,⋯, ∣vm⟩ for uma base de V e

∣w1⟩ ,⋯, ∣wn⟩ for uma base de W , temos números complexos A1j a Anj (1 ≤ j ≤m)

tais que

A ∣vj⟩ =n

∑i=1Aij ∣wi⟩ . (2.5)

2.1.2.1 Matrizes esparsas

Deniremos aqui o que chamamos de matriz esparsa, conceito este que será

uma das hipóteses do algoritmo apresentado no capítulo 3. Uma matriz esparsa é

aquela cuja maioria dos elementos vale zero - a fração de elementos com valor nulo

é chamada esparsidade.

Por exemplo, a matriz⎛⎜⎜⎜⎜⎜⎜⎜⎜⎝

0 8 0 0

5 0 0 0

0 0 3 0

0 0 0 6

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎠

(2.6)

tem dimensão 4 × 4 apesar de apresentar somente 4 elementos diferentes de zero.

Armazenar e manipular matrizes esparsas em um computador pode ser feito

de forma mais eciente do que uma matriz genérica, quando utilizamos algoritmos

especializados que se beneciam da estrutura vazia da matriz.

2.1.3 Produto hermitiano e tensor

O produto hermitiano é uma função de dois vetores de determinado espaço ve-

torial cuja imagem é um escalar complexo. A notação usual do produto interno

dos vetores u e v é por ⟨u, v⟩ mas, levando em consideração a notação da mecânica

quântica para vetores ∣u⟩ e ∣v⟩ , o produto hermitiano será representado por ⟨u∣v⟩

em que ⟨u∣ é o vetor dual de ∣u⟩ , isto é, seu transposto-conjugado.

Matematicamente, se ∣u⟩ = ∑i ui ∣i⟩ e ∣v⟩ = ∑j vj ∣j⟩ , então:


⟨v∣u⟩ =∑i

viui = [v1 ⋯ vn]

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣

u1

⋮

un

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦

, (2.7)

em que a representa o conjugado do número complexo a.

Dois vetores ∣u⟩ e ∣v⟩ são ortogonais se seu produto interno vale zero. Além

disso, podemos denir a norma de um vetor ∣v⟩ por

∥ ∣v⟩∥ =√

⟨v∣v⟩. (2.8)

Diremos que um vetor é unitário (também chamado de vetor normalizado) se

sua norma vale 1.

Assim como o produto hermitiano toma dois vetores para formar um escalar

complexo, o produto tensorial será aplicado a dois espaços vetoriais para formar um

terceiro espaço vetorial.

Suponha que V e W sejam dois espaços vetoriais de dimensões m e n, respec-

tivamente. O produto tensorial representado por V ⊗W é um espaço vetorial de

dimensão mn, cujos elementos são combinações lineares de expressões da forma

∣v⟩ ⊗ ∣w⟩ , em que ∣v⟩ ∈ V e ∣w⟩ ∈ W . Estas expressões satisfazem as seguintes

condições:

(∣v1⟩ + ∣v2⟩)⊗ ∣w⟩ = ∣v1⟩ ⊗ ∣w⟩ + ∣v2⟩ ⊗ ∣w⟩ ;

∣v⟩ ⊗ (∣w1⟩ + ∣w2⟩) = ∣v⟩ ⊗ ∣w1⟩ + ∣v⟩ ⊗ ∣w2⟩ ;

c ∣v⟩ ⊗ ∣w⟩ = ∣v⟩ ⊗ c ∣w⟩ = c(∣v⟩ ⊗ ∣w⟩).

Por exemplo, se o espaço vetorial V tem como base os vetores ∣0⟩e ∣1⟩ , então

∣0⟩ ⊗ ∣0⟩ + ∣1⟩ ⊗ ∣1⟩ é um dos elementos de V ⊗ V .

Utilizaremos a notação ∣vw⟩ para o produto tensor ∣v⟩ ⊗ ∣w⟩ , assim como ∣ψ⟩⊗k

para representar o produto tensorial de ∣ψ⟩ consigo mesmo k vezes; por exemplo,

∣ψ⟩⊗3 = ∣ψ⟩ ⊗ ∣ψ⟩ ⊗ ∣ψ⟩ .


É muito mais fácil visualizar o produto tensorial através da representação ma-

tricial conhecida como produto de Kronecker. Para isso, supondo as transformações

lineares T ∶ V1 → W1 e S ∶ V2 → W2, em que V1, V2,W1 e W2 são espaços vetoriais,

e T ⊗ S ∶ V1 ⊗ V2 → W1 ⊗W2 é denido por T ⊗ S(v1 ⊗ v2) = Tv1 ⊗ Sv2 em que

v1 ∈ V1 e v2 ∈ V2, escolheremos bases para V1, V2,W1 eW2 e assim seremos capazes de

representar S e T como as matrizes Am×n e Bp×q, respectivamente. Assim, teremos

A⊗B =

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣

a11B ⋯ a1nB

⋮ ⋮ ⋮

am1B ⋯ amnB

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦

. (2.9)

Notamos no exemplo

⎡⎢⎢⎢⎢⎢⎣

1 2

3 4

⎤⎥⎥⎥⎥⎥⎦m×n

⊗⎡⎢⎢⎢⎢⎢⎣

0 5

6 7

⎤⎥⎥⎥⎥⎥⎦p×q

=

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

0 5 0 10

6 7 12 14

0 15 0 20

18 21 24 28

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦mp×nq

(2.10)

que as dimensões da primeira e da segunda matrizes são (m,n) = 2 × 2 e (p, q) =

2 × 2, respectivamente, e as dimensões da matriz resultante do produto tensorial é

(m × p, n × q) = 4 × 4.

2.1.4 Autovalores e autovetores

Suponhamos um operador linear A de um espaço vetorial V . Um autovetor deste

operador é um vetor ∣v⟩ ∈ V tal que

A ∣v⟩ = v ∣v⟩ , (2.11)

em que v é um número complexo conhecido como o autovalor de A correspondente

ao autovetor ∣v⟩ . É comum utilizar a notação v tanto como rótulo do autovetor e

também para representar o autovalor com o qual se relaciona.

A determinação dos autovalores de um operador A pode ser dada como solução

da equação característica c(λ) = 0, em que c(λ) é a chamada função característica

c(λ) = det ∣A − λI ∣.


Deniremos também a representação diagonal de um operador A como A =

∑i λi ∣i⟩ ⟨i∣ , em que os vetores ∣i⟩ formam um conjunto ortonormal de autovetores de

A, sendo λi os autovalores correspondentes. Um operador é, portanto, diagonalizável

se possui representação diagonal.

2.1.4.1 Número de condição

Na análise numérica, o número de condição de uma função mede quanto a saída

de tal função pode variar a partir de uma pequena diferença na entrada. Em outras

palavras, o número de condição mede quão sensível à entrada é certa função e assim,

também, a possíveis erros que serão reetidos em sua saída.

O número de condição pode ou não ser nito, e é comumente dado pela razão

entre o maior e o menor valor singular (denidos, por sua vez, como as raízes-

quadradas dos autovalores não-negativos da matriz adjunta) do operador analisado.

No caso dos operadores mais utilizados na mecânica quântica, e mais especi-

camente, do operador utilizado no desenvolvimento do algoritmo tema deste artigo,

um operador hermitiano (ver seção 2.1.6), o número de condição será dado por

κ(A) =RRRRRRRRRRR

λmax(A)λmin(A)

RRRRRRRRRRR(2.12)

em que λmax(A) e λmin(A) são, respectivamente, o maior e o menor (em módulo)

autovalores de A.

2.1.5 Matrizes de Pauli

Quatro matrizes extremamente importantes no estudo da física e da matemática,

e com várias aplicações no campo da mecânica quântica são as chamadas matrizes

de Pauli. São matrizes complexas de dimensão 2×2 e usualmente são indicadas pela

notação σi como se segue:

σ0 = I =⎛⎜⎝

1 0

0 1

⎞⎟⎠

σ1 = σx =X =⎛⎜⎝

0 1

1 0

⎞⎟⎠


σ2 = σy = Y =⎛⎜⎝

0 −i

i 0

⎞⎟⎠

σ3 = σz = Z =⎛⎜⎝

1 0

0 −1

⎞⎟⎠

As matrizes foram nomeadas em homenagem ao sico Wolfgang Pauli, e na

mecânica quântica, são vistas na equação de Pauli, que leva em conta a interação

do spin de uma partícula com um campo eletromagnético externo [9].

2.1.6 Adjuntos e operadores Hermitianos

Supondo A como operador linear em um espaço vetorial V , existirá em V um

operador linear único A, conhecido como adjunto ou conjugado hermitiano de A,

para o qual

⟨Ax∣y⟩ = ⟨x∣Ay⟩, (2.13)

para todo x, y ∈ V .

Podemos representar o adjunto, mais simplesmente, através da igualdade A =

(A∗)T .

Obs.: Como observamos anteriormente, ∣v⟩ = ⟨v∣ , e assim, (A ∣v⟩) = ⟨v∣A.

Um operador cujo adjunto é igual a si mesmo é chamado de operador Hermitiano.

Deniremos os operadores normais como aqueles para os quais AA = AA.

Claramente, todo operador Hermitiano é também um operador normal.

A última denição importante, no que se refere aos operadores normais, é a classe

especial dos operadores unitários, que são aqueles para os quais vale a propriedade

UU = U U = I. Geometricamente, operadores unitários são importantes pois pre-

servam o produto interno entre vetores. Isto é, supondo ∣v⟩ e ∣w⟩ vetores, o produto

interno entre U ∣v⟩ e U ∣w⟩ tem o mesmo valor do produto interno entre ∣v⟩ e ∣w⟩ :

⟨U ∣v⟩∣U ∣w⟩⟩ = ⟨v∣U U ∣w⟩ = ⟨v∣ I ∣w⟩ = ⟨v∣w⟩. (2.14)

Obs.: Vale notar que as matrizes de Pauli apresentadas na seção 2.1.5 são her-

mitianas e unitárias e, conjuntamente, geram o espaço vetorial de todas as matrizes

hermitianas de dimensão 2 × 2.


2.1.6.1 Todo operador Hermitiano é Diagonalizável

Para nossas aspirações na execução do algoritmo tema deste trabalho, o resultado

acima será de grande importância uma vez que a diagonalização do operador de

entrada do sistema linear representa uma etapa do processamento.

Antes, apresentamos os seguinte teoremas:

Teorema 1. Seja A uma matriz Hermitiana, isto é, A = A e λ um autovalor de

A. Então, λ é um número real, isto é, λ ∈ R.

Prova. Utilizando as notações acima de A, λ e sendo v o autovetor associado à λ,

temos que

λ⟨v∣v⟩ = ⟨λv∣v⟩. (2.15)

Pela denição de autovetor (λv = Av):

⟨λv∣v⟩ = ⟨Av∣v⟩. (2.16)

Usando as propriedades do produto interno e a hermiticidade de A:

⟨Av∣v⟩ = ⟨v∣Av⟩ = ⟨v∣Av⟩. (2.17)

Novamente pela denição de autovetor:

⟨v∣λv⟩ = λ⟨v∣v⟩. (2.18)

Uma vez que v ≠ 0, obtemos λ = λ. Mas, para isso, é necessário que λ ∈ R.

Teorema 2. Se A for uma matriz qualquer, existe uma matriz unitária U de forma

que U−1AU é triangular superior.

Prova. Como sabemos, A tem pelo menos um autovetor unitário v1. Deniremos a

matriz U1 unitária (através do processo de Gram-Schmidt) de forma

⎛⎜⎜⎜⎜⎝v1 ⋯ vn

⎞⎟⎟⎟⎟⎠

(2.19)


onde as colunas de 2 a n podem ser escolhidas de qualquer forma. Se aplicarmos

U−11 AU1 a e1, teremos:

U−11 AU1e1 = U−1

1 Av1 = λ1U−11 v1 = λ1e1. (2.20)

Isto é, U−11 AU1 é da forma

⎛⎜⎜⎜⎜⎝

λ1 ∗ ∗

0 ∗ ∗

0 ∗ ∗

⎞⎟⎟⎟⎟⎠

(2.21)

(a matriz de dimensão 3× 3 foi escrita por conveniência, mas a prova funciona para

qualquer n).

Se seguirmos para o `sudeste' da matriz A, poderemos repetir o processo para a

matriz (n − 1) × (n − 1) obtida removendo-se a primeira linha e a primeira coluna

de A e assim sucessivamente até que tenhamos uma matriz triangular similar a A

através da concatenação multiplicativa das matrizes Ui geradas a cada passo. Assim,

a matriz U buscada pelo teorema será U = U1U2⋯Un, e por consequência, U−1AU

será triangular superior.

Finalmente seremos capazes de provar a diagonalização de uma matriz hermiti-

ana. Pelo teorema acima, sabemos que

U−1AU = T (2.22)

de forma que T é triangular superior e também hermitiana, pois

(U−1AU) = U A(U−1) = U−1AU. (2.23)

Ora, se T é triangular superior, então T é triangular inferior. E se T é hermiti-

ana, então T = T . Assim, T é uma matriz diagonal.

2.1.6.2 Funções de operadores

Funções de operadores (ou matrizes) são denidos através da expansão de Taylor

da função escalar correspondente. Por exemplo, como

ex = 1 + x + x2

2!+ x

3

3!+ x

4

4!+⋯ (2.24)


então, escolhendo como argumento a matriz de Pauli σx, teremos

eσx = 1 + σx +σ2x

2!+ σ

3x

3!+ σ

4x

4!+⋯

= 1⎛⎝

1 + 1

2!+ 1

4!+⋯

⎞⎠+ σx

⎛⎝

1 + 1

3!+ 1

5!+⋯

⎞⎠

= 1 cosh 1 + σx senh 1. (2.25)

em que usamos que σ2x = 1, e 1 é a matriz identidade 2 × 2.

Funções de matrizes diagonais são ainda mais simples, uma vez que poderemos

aplicar a função a cada elemento da diagonal separadamente. Além disso, se a matriz

M = UDU−1 é diagonalizável, sendo D sua matriz diagonal, a expansão de Taylor

nos dará que f(M) = Uf(D)U−1 e aí poderemos aplicar a função f a cada elemento

de D.

2.1.7 Espaço de Hilbert

Um espaço de Hilbert H é um espaço vetorial onde está denida a operação do

produto hermitiano, associando a cada par de vetores um escalar complexo, assim

como também está denida a norma de cada vetor com respeito à distância induzida

pelo produto interno.

A denição do produto interno de vetores para um espaço de Hilbert deve satis-

fazer as propriedades:

⟨x∣y⟩ = ⟨y∣x⟩;

⟨ax1 + bx2∣y⟩ = a⟨x1∣y⟩ + b⟨x2∣y⟩ para a, b ∈ R;

⟨x∣x⟩ ≥ 0.

Deniremos a norma de um vetor como

∥x∥ =√

⟨x∣x⟩, (2.26)

e a distância d entre dois pontos x, y em H em termos da norma por

d(x, y) = ∥x − y∥ =√

⟨x − y∣x − y⟩. (2.27)


A existência desta função d(x, y) nos leva à conclusão que o espaço vetorial H é

também um espaço métrico (sendo d sua métrica), e, portanto, valem as proprieda-

des:

d(x, y) = d(y, x);

d(x,x) = 0;

d(x, z) ≤ d(x, y) + d(y, z), a chamada desigualdade triangular.

A denição de espaços de Hilbert ainda considera que o espaço H deva ser

completo: toda sequência de Cauchy de elementos de H convergirá com respeito à

norma para um elemento deH. Como os espaços que consideramos nesta monograa

(à exceção da seção 2.1.8) têm dimensão nita, esta condição é automaticamente

satisfeita.

2.1.8 Mecânica Quântica: evolução de Schrödinger

A evolução de um sistema quântico fechado é descrita por uma transformação

unitária. Isto é, o estado ∣ψ⟩ to sistema no tempo t1 relaciona-se com o estado ∣ψ′⟩

do tempo t2 através de um operador unitário U que depende somente dos tempos

t1 e t2, em que ∣ψ′⟩ = U ∣ψ⟩ .

A denição acima descreve a relação entre dois estados em tempos discretos t1 e

t2. Se a estendermos para uma denição em tempo contínuo, obteremos a equação

de Schrödinger:

i~d ∣ψ⟩dt

=H ∣ψ⟩ (2.28)

em que ~ é a chamada constante de Planck (cujo valor, 6,62607 × 10−34 [10], é

obtido experimentalmente) e H é um operador hermitiano xo conhecido como

Hamiltoniano, especíco deste sistema fechado.

O Hamiltoniano é um operador que corresponde à energia total de um sistema,

isto é, à soma entre as energias cinéticas de todas as partículas do sistema assim

como a energia potencial das mesmas. Dessa forma, para diferentes sistemas físicos


e com um número de partículas variável, o Hamiltoniano terá seu valor alterado.

A partir desta equação, se conhecermos o Hamiltoniano do sistema e o valor da

constante de Planck, seremos capazes de modelar o comportamento de um sistema

quântico completamente, desde que seu estado inicial também seja conhecido:

∣ψ(t)⟩ = e−iHt~ ∣ψ(0)⟩ (2.29)

em que e−iHt

~ representa a série de potências em H.

Para muitos sistemas, entretanto, é possível também escrever um Hamiltoniano

que varia de acordo com o tempo (ou seja, que não é constante) e assim, teríamos

um sistema não-fechado, ao contrário de nossa hipótese original. Ainda assim, tais

sistemas comportam-se satisfazendo a equação de Schrödinger, mesmo quando o

Hamiltoniano varia com o tempo.

2.1.9 Mecânica Quântica: medições projetivas

Medições quânticas são descritas por uma coleção de operadores de medição

Mm que atuam no espaço de estados sendo medido. Se um estado do sistema

quântico é ∣ψ⟩ , a probabilidade de que o resultadom ocorra é p(m) = ⟨ψ∣M mMm ∣ψ⟩ .

O conjunto de operadores Mm satisfaz a equação de completude ∑m p(m) = 1.

Denição: Medição projetiva

Seja M um operador hermitiano em um espaço de estados de um sistema sendo

observado. M terá decomposição espectral

M =∑m

mPm (2.30)

em que Pm é a projeção no autoespaço de M associado ao autovalor m. Após medir

o estado ∣ψ⟩ , a probabilidade de se obter o resultado m será p(m) = ⟨ψ∣Pm ∣ψ⟩ , como

visto acima.

Medições projetivas são interessantes pela possibilidade do cálculo de seus valo-

res médios e desvio padrão, após uma série de medições. Utilizaremos o conceito

estatístico de esperança para o cálculo da média:


E(M) = ∑m

mp(m)

= ∑m

m ⟨ψ∣Pm ∣ψ⟩

= ⟨ψ∣ (∑m

mPm) ∣ψ⟩

= ⟨ψ∣M ∣ψ⟩ . (2.31)

2.1.9.1 Observáveis

As propriedades de um sistema que podem ser determinadas por uma sequên-

cia de operações físicas são os observáveis do sistema, como por exemplo posição,

momentos e energia.

Na mecânica quântica, a medição dos observáveis exibe propriedades contraintui-

tivas, no sentido que o processo afetará o sistema de uma forma não determinística

e irreversível, fazendo-o colapsar imediatamente a um de seus autoestados.

O valor médio de um observável M é comumente escrito como ⟨M⟩. Poderemos

então calcular o desvio padrão de M através do valor encontrado anteriormente:

[∆(M)]2 = ⟨(M − ⟨M⟩)2⟩ = ⟨M2⟩ − ⟨M⟩2. (2.32)

2.1.10 Mecânica Quântica: emaranhamento

O emaranhamento quântico (ou entralaçamento quântico) é o fenômeno que

ocorre quando pares ou grupos de partículas interagem de forma que o estado quân-

tico de cada uma não pode ser descrito independentemente, e ao invés disso, um

estado quântico deve ser dado para o sistema como um todo.

Nota-se que medições em observáveis de sistemas com partículas entrelaçadas

estão fortemente correlacionadas. Por exemplo, se um par de particulas entrelaçadas

é de tal forma que seu spin total é zero, e sabe-se que uma destas partículas tem spin

em sentido horário em certo eixo, então a outra partícula terá seu spin no sentido

anti-horário, quando medido no mesmo eixo.

2.2. COMPUTAÇÃO QUÂNTICA 17

Se considerarmos dois sistemas A e B, que não interagem entre si, em que ∣ψ⟩Aé o estado do primeiro sistema e ∣φ⟩B é o estado do segundo sistema, então o estado

do sistema composto será

∣ψ⟩A ⊗ ∣φ⟩B. (2.33)

Estados do sistema composto que podem ser representados desta forma são chama-

dos estados separáveis. Mas, uma vez xadas as bases ∣i⟩A e ∣j⟩B para os espaços

de Hilbert HA de A e HB de B, os estados do sistema composto serão escritos, de

forma mais geral, como

∣ψ⟩AB =∑i,j

ci,j ∣i⟩A ⊗ ∣j⟩B. (2.34)

O estado ∣ψ⟩AB será separável se existir cAi , cBj de forma que ci,j = cAi c

Bj , e será

inseparável caso contrário. Se um estado é inseparável, é chamado de estado ema-

ranhado.

Por exemplo, dados os vetores ∣0⟩A, ∣1⟩A base de HA e ∣0⟩B, ∣1⟩B base de HB,

um dos estados emaranhados do sistema composto HA ⊗HB é

1√2( ∣0⟩A ⊗ ∣1⟩B − ∣1⟩A ⊗ ∣0⟩B). (2.35)

2.2 Computação Quântica

Após apresentar esses vários conceitos teóricos da álgebra linear e da mecânica

quântica, nalmente seremos defrontados com suas aplicações no campo de estudo

em que estamos realmente interessados: a computação quântica.

Como dene a ACM [11], a computação, como um todo, é qualquer atividade

com objetivo de obter algum resultado através de um processo algorítmico, como

por exemplo, através do uso de computadores. Abrange o desenho e construção de

ferramentas para processamento, estruturação e manutenção da informação.

Assim como no caso clássico, a computação quântica é o ramo do conhecimento

que se foca na aplicação de algoritmos de base quântica para a transformação e

processamento da informação (quântica). Um computador tradicional utiliza-se de

longas cadeias de bits, que representam os numerais zero ou um (baseado na base


binária), enquanto um computador quântico pode se beneciar do uso de bits quân-

ticos, ou qubits, que podem estar em um estado de superposição entre zero e um,

possibilitando, através do que chamamos de paralelismo quântico, um vasto número

de cálculos simultâneos.

2.2.1 Bits quânticos

O que chamamos aqui de qubits é a unidade básica da informação quântica, o

análogo do bit clássico. Um qubit é qualquer sistema quântico de dois estados, como,

por exemplo, a polarização de um fóton (horizontal ou vertical) ou o spin de um

elétron (up ou down). Em um sistema clássico, o bit precisaria estar em um dos dois

estados, mas para um qubit é possível estar em uma superposição dos dois estados

simultaneamente.

Os dois estados em que um qubit pode ser mensurado são chamados estados base,

comumente representados como ∣0⟩ e ∣1⟩ . O estado de um qubit ∣ψ⟩ é, portanto,

uma superposição linear dos estados base; isto é,

∣ψ⟩ = α ∣0⟩ + β ∣1⟩ (2.36)

em que α e β são números complexos chamados de amplitudes, de forma que, ao

medir o valor de ∣ψ⟩ na base padrão, a probabilidade de se obter ∣0⟩ e ∣1⟩ será dada

por ∣α∣2 e ∣β∣2 respectivamente.

Notemos que, como os quadrados das amplitudes representam probabilidades,

teremos que α e β devem satisfazer a equação ∣α∣2 + ∣β∣2 = 1 pelo fato de que são os

únicos resultados possíveis de serem obtidos após uma medição de ∣ψ⟩ .

2.2.2 Portas Lógicas

Analogamente a um computador clássico, construído a partir de circuitos elétri-

cos, os e portas lógicas, o computador quântico será construído a partir de circuitos

quânticos baseados em portas lógicas quânticas, que manipulam a informação quân-

tica representada pelos qubits.


A porta lógica de um qubit mais simples a ser considerada é a análoga ao NOT

clássico, isto é, o inversor 0 → 1 e 1 → 0, que levará o estado α ∣0⟩ + β ∣1⟩ no estado

α ∣1⟩ + β ∣0⟩ , e que é representada

X =⎛⎜⎝

0 1

1 0

⎞⎟⎠

(2.37)

de forma que possamos representar matricialmente o estado α ∣0⟩ + β ∣1⟩ por

α ∣0⟩ + β ∣1⟩ =⎛⎜⎝

α

β

⎞⎟⎠

(2.38)

e assim aplicando a porta lógica

X⎛⎜⎝

α

β

⎞⎟⎠=⎛⎜⎝

β

α

⎞⎟⎠. (2.39)

Importante notar que nem todo tipo de matriz pode descrever as portas quân-

ticas. Como é necessário que o estado resultante da aplicação da porta quântica (e

consequentemente, da matriz que a representa) tenha amplitudes cujos quadrados

somam 1 (devido ao limite das probabilidades), as matrizes portas de um qubit

devem ser unitárias.

Além da porta NOT para um qubit de entrada, também existem outras portas

que terão aplicação em vários algoritmos quânticos, dentre elas a chamada ip que

mapeia ∣0⟩ → ∣0⟩ e altera o sinal de ∣1⟩ da forma ∣1⟩ → − ∣1⟩ . Além da ip, uma porta

muito importante é conhecida como porta de Hadamard, representada pela matriz

H = 1√2

⎛⎜⎝

1 1

1 −1

⎞⎟⎠

(2.40)

que mapeia ∣0⟩ → (∣0⟩ + ∣1⟩)/√

2 e ∣1⟩ → (∣0⟩ − ∣1⟩)/√

2, justamente na `metade do

caminho' entre ∣0⟩ e ∣1⟩ .

2.2.2.1 Reversibilidade

Em geral, em um computador clássico, portas lógicas diferentes da porta NOT

não são reversíveis. Assim, por exemplo, para uma porta AND, é impossível obter

os valores que foram usados na entrada dado o bit de saída:


A B A ∧B

0 0 0

0 1 0

1 0 0

1 1 1

No exemplo, se a saída obtida for o valor 0, não seremos capazes de dizer qual

das três combinações possíveis de entrada a produziu.

Ao contrário das portas clássicas, as portas lógicas quânticas são sempre reversí-

veis: dado que as portas quânticas são unitárias, de forma a manter o somatório de

probabilidades de encontrar cada estado-base após a medição como 100%, e todas as

matrizes unitárias são inversíveis, basta que sejamos capazes de construir a matriz

inversa da matriz que descreve a porta quântica para que tenhamos denido a porta

quântica inversa.

Além disso, notamos em contraste com os circuitos clássicos, que os circuitos

quânticos não permitem `loops', sendo portanto, acíclicos, e também não permitem

a união de os, seja para entrada ou na saída de alguma porta lógica, devido ao

caráter reversível das portas quânticas e à impossibilidade de clonagem de estados

quânticos, regras estas que são quebradas nos circuitos de união ou separação (o que

chamamos de FANIN e FANOUT).

2.2.2.2 A porta CNOT

Assim como as já apresentadas portas quânticas para um único qubit de entrada,

a porta lógica NOT-controlado (CNOT) recebe como entrada mais de um qubit:

especicamente, a porta recebe dois qubits, conhecidos como qubit de controle e

qubit alvo, respectivamente.

A linha no topo da imagem representa o qubit de controle, enquanto a linha

abaixo representa o qubit alvo. A ação da porta pode ser descrita da seguinte

forma: se valor do qubit de controle for 1, então o valor do qubit alvo é alternado;


Figura 2.1: Representação da porta lógica quântica CNOT.

caso contrário nada é feito:

∣00⟩ → ∣00⟩ ;

∣01⟩ → ∣01⟩ ;

∣10⟩ → ∣11⟩ ;

∣11⟩ → ∣10⟩ .

Podemos representá-la também por um operador matricial, que pode ser apli-

cado, através da multiplicação, nas entradas às quais se deseja

UCNOT =

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎝

1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎠

,

em que, como podemos notar, o requisito da conservação de probabilidades é ex-

presso no fato de que UCNOT é uma matriz unitária.

Se denirmos ∣ψ⟩ = a ∣0⟩ + b ∣1⟩ , ou seja

∣ψ⟩ =⎡⎢⎢⎢⎢⎢⎣

a

b

⎤⎥⎥⎥⎥⎥⎦(2.41)

e aplicarmos UCNOT com qubit de controle ∣0⟩ , teremos

UCNOT ( ∣0⟩ ∣ψ⟩) =

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

a

b

0

0

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

=

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

a

b

0

0

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

= ∣0⟩ ∣ψ⟩ . (2.42)

Da mesma forma, se utilizarmos ∣1⟩ como qubit de controle, teremos


UCNOT ( ∣1⟩ ∣ψ⟩) =

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

1 0 0 0

0 1 0 0

0 0 0 1

0 0 1 0

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

0

0

a

b

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

=

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

0

0

0

a

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

+

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

0

0

b

0

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦= a ∣1⟩ ∣1⟩ + b ∣1⟩ ∣0⟩ = ∣1⟩(a ∣1⟩ + b ∣0⟩)

= ∣1⟩∣ψ⟩ , (2.43)

em que ∣ψ⟩ representa a troca das amplitudes das entradas de ∣ψ⟩ , ou seja, por

exemplo, se

∣x⟩ = a ∣0⟩ + b ∣1⟩ , (2.44)

então

∣x⟩ = b ∣0⟩ + a ∣1⟩ . (2.45)

2.2.2.3 A porta de Fredkin

Da mesma forma que a porta CNOT recebe como entrada dois qubits e toma o

qubit de controle para alternar o qubit alvo, a porta de Fredkin receberá três qubits

e baseado no valor do qubit de controle, trocará os valores dos outros dois qubits,

como mostra a gura.

Figura 2.2: Representação da porta lógica quântica de Fredkin.

A ação da porta pode ser representada pela tabela-verdade a seguir:


A B C A′ B′ C ′

0 0 0 0 0 0

0 0 1 0 0 1

0 1 0 0 1 0

0 1 1 0 1 1

1 0 0 1 0 0

1 0 1 1 1 0

1 1 0 1 0 1

1 1 1 1 1 1

Além disso, também podemos representar a porta de Fredkin através do operador

unitário UFredkin:

UFredkin =

⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1

⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

. (2.46)

2.2.3 Circuitos Quânticos

Assim como na computação clássica, dispor portas lógicas quânticas em conjunto

forma um circuito quântico. Os os do circuito não correspondem necessariamente

a os físicos, mas podem representar a passagem do tempo ou a movimentação de

uma particula - como um fóton - de uma posição do espaço à outra.

Acima podemos ver operações bastante importantes e comuns no descrever de

circuitos lógicos quânticos: a porta U controlado e a porta de medição.

Supondo U como qualquer matriz unitária, deniremos a porta U controlado de

forma que exista um qubit de controle para ativar ou não a operação U sobre os


Figura 2.3: Exemplos de portas quânticas comuns em circuitos.

qubits alvo da porta. Isto é, digamos que a representação matricial de U seja

U =⎡⎢⎢⎢⎢⎢⎣

x00 x01

x10 x11

⎤⎥⎥⎥⎥⎥⎦,

então a porta U controlado operará em dois qubits mapeando os estados base de

forma

∣00⟩ → ∣00⟩ ;

∣01⟩ → ∣01⟩ ;

∣10⟩ → ∣1⟩U ∣0⟩ = ∣1⟩(x00 ∣0⟩ + x10 ∣1⟩);

∣11⟩ → ∣1⟩U ∣1⟩ = ∣1⟩(x01 ∣0⟩ + x11 ∣1⟩).

A segunda porta no exemplo representa a medição sobre um qubit, que o con-

verterá de um estado do tipo ∣ψ⟩ = α ∣0⟩ + β ∣1⟩ em um dos estados base com proba-

bilidades iguais ao quadrado das amplitudes do estado.

Circuitos quânticos são modelos úteis para processos quânticos, incluindo com-

putações, comunicação, entre outras aplicações.

2.2.4 Paralelismo Quântico

O grande benefício da utilização dos computadores quânticos é sua capacidade

de cálculo simultâneo de diferentes valores de uma certa função.

Como exemplica Semião [12], suponha uma função f(x) ∶ 0,1→ 0,1 rever-

sível de forma que armazenemos o valor de x conjuntamente com o valor de f(x)

no estado ∣x, y ⊕ f(x)⟩ de forma que o segundo qubit armazene ∣0⟩ , se y = f(x), e


∣1⟩ caso contrário; em que ⊕ representa o operador lógico ou-exclusivo (XOR), cuja

tabela verdade é

A B A⊕B

0 0 0

0 1 1

1 0 1

1 1 0

.

Denotaremos a transformação unitária correspondente à aplicação de f(x) por Uf .

Apliquemos, então, Uf no qubit (∣0⟩ + ∣1⟩)/√

2, obtendo

∣ψ⟩ = Uf∣0,0⟩ + ∣1,0⟩

√2

=∣0, f(0)⟩ + ∣1, f(1)⟩

√2

(2.47)

que é um estado que contém informação tanto sobre f(0) quanto sobre f(1), apesar

de termos aplicado o operador somente uma vez.

Como vimos, um único circuito quântico pôde calcular simultaneamente o valor

da função para múltiplos valores de x, consequência direta da superposição em que

se encontrava o estado de entrada do circuito.

É importante notar, contudo, que o paralelismo quântico não nos fornecerá todos

os valores que f(x) pode assumir, uma vez que será necessária a realização de uma

medição, que resultará imediatamente na obtenção de um dos dois estados ∣0, f(0)⟩

ou ∣1, f(1)⟩ . Podemos, porém, obter informações sobre as propriedades de f(x)

devido à interferência existente entre ambos os estados no instante em que ainda

estão emaranhados.

Enquanto o paralelismo quântico é o que nos capacita a cálculos muito mais

rápidos e algoritmos mais ecientes, é também devido ao fato de que só conseguimos

obter propriedades globais das funções de entrada, ao invés de seus valores, que o

desenvolvimento de aplicações realmente úteis para a computação quântica ainda

caminha a passos lentos.


2.2.5 Transformada de Fourier Quântica

A transformada de Fourier (TF) é uma das ferramentas mais úteis da matemática

na ciência e tecnologia modernas, sendo usada em vários campos de aplicação, entre

eles a redução de ruído de dados, exames de propriedades de cristais e produção

de hologramas. A transformada é especialmente útil quando temos algo com certa

periodicidade, uma vez que nos ajuda a extrair tal periodicidade da função para

analisar os dados limpos.

Deniremos aqui a chamada transformada de Fourier discreta, isto é, a TF que

atua sobre conjuntos de dados discretos. Supondo um vetor de números complexos

(x1,⋯, xn), a transformada gerará um vetor, também complexo, (y1,⋯, yn) de forma

que

yk =1√N

N−1∑j=0

xje2πijk/N . (2.48)

Como os qubits nada mais são do que vetores de números complexos, somos ca-

pazes de lhes aplicar a TF discreta: dado um qubit ∣ψ⟩ = ∑N−1j=0 αj ∣j⟩ , computaremos

sua transformada de Fourier quântica (TFQ) como

F ∣ψ⟩ =N−1∑k=0

⎛⎝

1√N

N−1∑j=0

αje2πijk/N⎞

⎠∣k⟩ . (2.49)

Por exemplo, se o estado tiver dois qubits ∣ψ⟩ = α00 ∣00⟩ + α01 ∣01⟩ + α10 ∣10⟩ +

α11 ∣11⟩ , então N = 4. Assim, βk = 12 ∑

3j=0αje

2πijk/4 e teremos:

β0 =1

2

3

∑j=0αj =

1

2(α00 + α01 + α10 + α11);

β1 =1

2

3

∑j=0αje

2πij/4 = 1

2(α00 + α01e

iπ/2 + α10eiπ + α11e

3iπ/2);

β2 =1

2

3

∑j=0αje

4πij/4 = 1

2(α00 + α01e

iπ + α10e2iπ + α11e

3iπ);

β3 =1

2

3

∑j=0αje

6πij/4 = 1

2(α00 + α01e

3iπ/2 + α10e3iπ + α11e

9iπ/2).

O circuito que implementa a TFQ envolve portas de rotação condicional Rθ e

portas swap, e sua implementação está descrita no Apêndice A.


Muitas das propriedades da TFQ seguem do fato de que é uma transformação

unitária. Dessa forma, teremos também que a inversa da transformada quântica

de Fourier é o adjunto hermitiano da matriz de Fourier, ou seja, F −1 = F . Como

há um sistema que implementa ecientemente a TFQ, o mesmo circuito pode ser

executado em reverso para realizar a TFQ inversa de forma eciente.

Muitos algoritmos quânticos aproveitam-se da aplicação da TFQ seguida de sua

inversa, como é o caso do algoritmo de resolução de sistemas lineares, foco deste

trabalho, uma vez que a TFQ pode ser usada para encontrar períodos e também

extrair autovalores de operadores unitários com alta precisão.

2.2.6 Computação Quântica com Ótica Linear

Uma das formas de implementação dos conceitos em computação quântica vistos

até aqui é a utilização de sistemas óticos, que envolve fótons como portadores de in-

formação, elementos da ótica linear para processar a informação quântica, incluindo

separadores de feixe, comutadores de fase e espelhos, e detectores de fótons para

realizar medições [13], [14].

Entre os sistemas óticos para processamento de informação quântica, a unidade

da luz, o fóton, é usado para representar um qubit, e superposições de estados quân-

ticos podem ser representados, transmitidos e detectados utilizando-os. Além disso,

as operações e portas lógicas quânticas serão implementadas através de elementos de

sistemas óticos, e sua concatenação formará os circuitos quânticos que implementam

os algoritmos desejados [15].

Em geral, os estados ∣0⟩ e ∣1⟩ são representados por fótons em diferentes modos

óticos, que podem ser por exemplo, as polarizações vertical e horizontal, diferentes

canais de frequência, ou até uma combinação destes dois casos. A notação que é

utilizada pelos físicos passa a levar em conta estes modos, por exemplo de forma

∣0⟩V ∣1⟩H , para representar um estado de dois qubits com o fóton 0 na polarização

vertical e o fóton 1 na polarização horizontal. A preparação de estados é feita,

de forma geral, utilizando fontes de fótons únicos (Single-photon generator, SPG,

no inglês), que são fontes de luz que a emitem como partículas separadas, diferen-


temente de fontes de luz incoerente como por exemplo lâmpadas incandescentes e

uorescentes.

Figura 2.4: Representação de qubits através da polarização de fótons, em que V e

H representam a polarização vertical e horizontal, respectivamente.

Os operadores quânticos, por sua vez, são implementados com elementos da

ótica linear. Um exemplo simples é dado pelos espelhos, cuja taxa de reexão é de

100%. Assim, dado um ângulo θ entre o feixe de fótons de entrada e o espelho,

sua utilização é o mesmo que aplicar uma rotação ao estado quântico representado

pelo feixe, sicamente alterando a frente de onda do mesmo, ou matematicamente,

aplicar um operador

R(θ) =⎡⎢⎢⎢⎢⎢⎣

cos θ − sen θ

sen θ cos θ

⎤⎥⎥⎥⎥⎥⎦. (2.50)

Na maioria dos casos, o ângulo θ = 45, mas isto pode variar dependendo do espelho

utilizado. De forma similar, os outros elementos óticos representarão operadores que

podem ser concatenados para simular a ação de portas lógicas quânticas, e estes,

por sua vez, unidos para realizar circuitos completos.

As operações realizadas pelos elementos óticos (separadores de feixe, comutado-

res de fase e espelhos, por exemplo) preservam as características da emissão de luz à

qual são aplicadas. Por exemplo, um feixe de luz coerente colocado como entrada em

um destes elementos produzirá um feixe também coerente como saída; assim como

uma superposição de estados quânticos de entrada produzirá uma superposição de

saída, [16].

Uma das limitações dos sistemas óticos é o fato de que os fótons dicilmente


interagem entre si, causando potencialmente um problema de escalabilidade dos

sistemas, uma vez que operações não-lineares cam difíceis de ser implementadas

e exigem um aumento da complexidade dos operadores, aumentando, portanto, o

número de elementos óticos requeridos para simulação de determinados circuitos

[17].

Capítulo 3

O algoritmo de Harrow, Hassidim e

LLoyd

Sistemas lineares estão presentes em todos os campos da ciência e engenharia nos

dias de hoje, e sua resolução, seja com objetivo de obter os valores das soluções ou

utilizá-las como parte de processos mais complexos, é um problema muito comum.

Com a evolução da tecnologia e o aumento da complexidade dos sistemas utilizados

hoje em dia, o tamanho da massa de dados comumente utilizada como entrada

para estes problemas vem crescendo muito rapidamente, de forma que mesmo os

computadores mais potentes levam bastante tempo para processar soluções.

O algoritmo apresentado a seguir foi desenvolvido em 2009 [8] e mostra como um

computador quântico é capaz de aproximar o valor de funções da solução de sistemas

lineares em tempo polilogarítmico, de forma a prover um aumento exponencial de

eciência sobre os melhores algoritmos clássicos conhecidos hoje. No artigo original,

os autores ainda demonstram que este algoritmo é quase a implementação ótima da

tarefa quântica (a demonstração estará omitida aqui).

3.1. CASO CLÁSSICO 31

3.1 Caso clássico

A resolução de sistemas lineares é um problema presente há muitos anos em

vários campos de aplicação, e várias técnicas de resolução e determinação de solu-

ções foram desenvolvidas. Aqui apresentaremos, sucintamente, duas destas técnicas

comumente utilizadas classicamente, isto é, executáveis por computadores clássicos,

para posterior comparação com o método quântico que é tema deste trabalho.

3.1.1 Eliminação de Gauss

O método de eliminação gaussiana (também chamado método do escalonamento)

é seguramente a mais conhecida ferramenta de resolução de sistemas lineares, e pode

ser usado em várias aplicações, como o cálculo do determinante, do posto e da inversa

de uma matriz quadrada.

Para executar o método de eliminação de linhas, uma sequência de operações

elementares será aplicada para modicar a matriz de coecientes do sistema, até

que a parte inferior esquerda da matriz esteja preenchida com a maior quantidade

de zeros possível. As operações elementares de linha podem ser de três tipos:

Troca de linhas,

Multiplicação de uma linha por um escalar diferente de zero,

Adição do múltiplo de uma linha à outra linha.

Dizemos que a matriz está escalonada quando todas as linhas não-nulas estão

acima de linhas compostas de zeros; o pivô de cada linha está numa coluna à direita

do pivô da linha anterior e todos os elementos abaixo de um pivô são nulos. Neste

caso, o valor das variáveis do sistema linear representado pela matriz de coecientes

poderá ser determinado caso o sistema não seja impossível.

O número de operações aritméticas necessárias para escalonar a matriz de co-

ecientes é uma forma de medir a eciência computacional do algoritmo. Para

resolver um sistema de n equações com n incógnitas, de forma a levar a matriz à


forma escalonada executando operações elementares de linhas e então resolvendo

os valores das incógnitas em ordem reversa, serão necessárias n(n − 1)/2 divisões,

(2n3 +3n2 −5n)/6 multiplicações e (2n3 +3n2 −5n)/6 subtrações, isto é, um total de

aproximadamente 2n3/3 operações [18]. O algoritmo de eliminação Gaussiana tem,

portanto, complexidade aritmética de O(n3).

3.1.2 Método do Gradiente Conjugado

O próximo algoritmo a ser apresentado aplica-se a casos especícos de sistemas

lineares, casos estes similares aos que serão tratados pelo algoritmo quântico apre-

sentado logo a seguir.

O método do gradiente conjugado resolve numericamente sistemas lineares cujas

matrizes são simétricas e denidas positivas, e é usado de forma iterativa como

método de otimização, sendo assim aplicável a sistemas esparsos com dimensão

grande demais para ser tratada por uma implementação direta.

Supondo que A seja uma matriz simétrica e positiva denida, diremos que dois

vetores u e v são conjugados (sobre A) se uTAv = 0, ou seja, se são ortogonais com

relação ao seu produto interno sobre A: ⟨u∣v⟩A = uTAv.

Para iniciar o algoritmo, escolheremos um valor x0 como tentativa de obter a

solução x∗ do sistema. É comum partir da escolha x0 = 0. Buscaremos, então, pela

aproximação da solução em cada iteração i através da minimização de xi, determinar

se nos aproximamos ou distanciamos do valor de x∗ de nossa tentativa.

As condições impostas a A garantem que

f(x) = 1

2xTAx − xT b, x ∈ Rn (3.1)

admita um único ponto de mínimo x∗. Assim, sempre que f(x) diminuir de uma

iteração para outra, saberemos que estamos mais próximos do valor de x∗.

De forma geral, para métodos iterativos de otimização, as iterações são denidas

pela equação

xk+1 = xk + αnpk. (3.2)


No caso do método do gradiente, P = pk ∶ ∀i ≠ k, i, k ∈ [1, n], ⟨pi∣pk⟩ = 0 é

um conjunto de vetores conjugados que formam uma base de Rn. Assim, podemos

expandir a solução x∗ de Ax = b para

x∗ =n

∑i=1αipi, (3.3)

vendo que

b = Ax∗ =n

∑i=1αiApi. (3.4)

Se denirmos o resíduo do k-ésimo passo rk por

rk = −∇f(xk) = b −Axk, (3.5)

a próxima direção de busca será construída através do resíduo atual e de todas as

direções de busca tentadas anteriormente, resultando na expressão

pk = rk −∑i<n

pTi ArkpTi Api

pi. (3.6)

Através da equação 3.2, poderemos calcular a localização do próximo valor ótimo,

em que os valores de αn serão obtidos por

αk =pTk b

pTkApk=pTk (rk−1 +Axk−1)

pTkApk=pTk rk−1

pTkApk. (3.7)

Note que pk e xk−1 são conjugados.

Dessa forma, escolhendo um valor ε pequeno, o algoritmo aproximará x∗ com

precisão ε e terminará se exigirmos que ∥rk∥2 < ε.

Para o método do gradiente conjugado, as operações dominantes durante uma

iteração são produtos matriz-vetor. Em geral, estas multiplicações exigem O(m)

operações, em que m é o número de entradas diferentes de zero na matriz. Se

considerarmos a suposição inicial dos problemas onde o gradiente conjugado será

aplicado, as matrizes de entrada são esparsas e assim m ∈ O(n). O número máximo

de iterações necessárias para atingir o limite ε com uma matriz de coecientes cujo

número de condição é κ, é

i ≤⎡⎢⎢⎢⎢⎢

1

2

√κ ln (2

ε)⎤⎥⎥⎥⎥⎥

(3.8)

e assim, concluímos que a complexidade de tempo para execução do algoritmo do

gradiente conjugado para resolução de sistemas lineares é O(m√κ) [19].

3.2. VISÃO GERAL 34

3.2 Visão Geral

Suponhamos que queremos resolver a equação Ax = b, em que A é uma matriz

N ×N inversível, e b é um vetor com N entradas. O algoritmo mapeará b no vetor

quântico ∣b⟩ e A em um operador quântico de forma que possamos encontrar uma

aproximação dos valores de x fazendo algo similar à inversão matricial que resolveria

o sistema no caso clássico: x = A−1b.

Para execução do algoritmo, também vamos supor que A é esparsa e Hermitiana.

Essas hipóteses poderão ser relaxadas, apesar disto tornar o algoritmo mais com-

plexo, como veremos a seguir. O aumento de eciência exponencial será alcançado

quando o número de condição de A for polilogarítmico em N e a precisão necessária

for da ordem de1

(log(n))k, em que k é um parâmetro de entrada.

O algorítmo mapeará as N entradas de b em log2N qubits para representar o

estado ∣b⟩ e então implementará a transformação eiAt ∣b⟩ através da técnica de es-

timativa de fase de forma que ∣b⟩ estará decomposto na base de autovetores de

A e teremos os autovalores λj correspondentes. Uma vez que tenhamos os auto-

valores emaranhados com seus autovetores correspondentes e o sistema estiver na

forma ∑j (βj ∣ψj⟩) ∣λj⟩ , aplicaremos uma transformação que nos levará ao estado

∑j λ−1j (βj ∣ψj⟩) ∣λj⟩ para então realizarmos medições de forma a obter ∣x⟩ = A−1 ∣b⟩ .

Teremos, então, construído ∣x⟩ como representação quântica do desejado vetor x.

Infelizmente, a leitura de todas as componentes de x demandaria a execução do

algoritmo N vezes. Contudo, se estivermos interessados somente em um valor médio

xTMx (onde M é um operador linear), poderemos mapear M para um operador

quântico e aplicar a medição correspondente a M em ∣x⟩ para obter uma estimativa

desta média, ou seja, obteremos ⟨x∣M ∣x⟩ . Uma grande variedade de propriedades

do vetor x pode ser extraída desta forma, incluindo a normalização, momentos e

pesos em diferentes partes do espaço de estados.

3.3. APLICAÇÕES 35

3.3 Aplicações

A resolução de sistemas lineares pode ser encontrada como problema presente em

várias áreas, desde casos em que a própria resolução é o problema, como também em

casos em que é somente um meio de chegar a um outro resultado. Apresentaremos

aqui aplicações simples em que o algoritmo quântico poderia ser aplicado de forma

que propriedades extraídas da solução do sistema (ao invés da solução em si) são

úteis na resolução de problemas maiores.

3.3.1 Estados estáveis de processos estocásticos

Consideraremos um processo estocástico xt = Axt−1+b, onde a i-ésima coordenada

do vetor xt representa a quantidade de itens do tipo i no tempo t. O estado estável

desta distribuição será dado por ∣x⟩ = (I − A)−1 ∣b⟩ , e deniremos xt = Axt−1 + b e

assim ∣x⟩ = (I − A)−1 ∣b⟩ . Para determinarmos se ∣x⟩ e ∣x⟩ são similares, utilizaremos

o teste SWAP entre eles, como é descrito no apêndice B.

Este método pode ser utilizado por alguém que busque determinar similaridades

entre imagens ou identicar relações entre bancos de dados.

3.3.2 Ajuste Quântico de Dados e Aprendizado de Máquina

Ajuste de dados é o processo de construção e ajuste de modelos a uma série

discreta de dados adquiridos seguido da análise da acurácia do tal ajuste. Enge-

nheiros e cientistas utilizam variadas técnicas de ajuste de dados (data tting, no

inglês), incluindo equações matemáticas e métodos não-paramétricos. Estes ajustes

poderão, por sua vez, ser utilizados como um auxílio para a visualização de dados,

inferência de valores da função estimada para previsão de dados (possibilitando as-

sim o aprendizado de máquina, por exemplo) e para sintetizar as relações entre duas

ou mais variáveis.

Tipicamente, um modelo teórico dependerá de um número de parâmetros e de-

nições das relações entre os dados que dependerão destes parâmetros. Ajustar uma

grande quantidade de dados experimentais a estas relações funcionais permite a ob-

3.3. APLICAÇÕES 36

Figura 3.1: Exemplo de ajuste de curva, com pontos gerados por uma função Seno,

aproximada por curvas polinomiais (vermelho, verde, laranja e azul representam

primeiro, segundo, terceiro e quarto graus, respectivamente) [1]

tenção de estimativas conáveis dos parâmetros. Se a quantidade de dados se torna

muito grande, o ajuste pode se tornar muito custoso, como é o caso de problemas de

física de alta energia com gigabytes de dados produzidos por segundo, como ocorre

no LHC (grande colisor de hádrons). A análise estrutural se inicia com uma ten-

tativa inicial e vai sendo melhorada através de iterações que testam variações dos

parâmetros do modelo. É, portanto, necessário que sejam estimados muitos mode-

los, e comparações entre eles sejam feitas de forma a determinar a aproximação mais

precisa.

O algoritmo apresentado em [20] descreve uma adaptação do algoritmo de reso-

lução de sistemas lineares em destaque neste trabalho para obter, de forma eciente

quanticamente, a qualidade de um ajuste de dados sem que seja necessário determi-

nar os parâmetros de tal ajuste. Assim, o método de comparação de ajustes de dados

pode ser exponencialmente acelerado quando comparado com os métodos clássicos

para conjuntos muito grandes de informação.

Por sua vez, o artigo [21] mostra que um classicador binário otimizado (a cha-

3.4. PREPARAÇÃO DA ENTRADA 37

mada máquina de vetores de suporte) pode ser implementada em um computador

quântico com aceleração exponencial no tamanho dos vetores e no número de da-

dos de treinamento (no caso do aprendizado de máquina supervisionado). Também

aqui, o algoritmo de sistemas lineares é utilizado para, de forma eciente, inverter

a matriz núcleo de dados de treinamento.

3.4 Preparação da entrada

Para adaptar o problema clássico Ax = b ao contexto quântico, normalizaremos

os vetores (de forma que ∥x∥ = ∥b∥ = 1) e aplicaremos uma transformação à matriz

A.

Com isso, a entrada de nosso algoritmo quântico será composta por três sub-

sistemas: um qubit auxiliar inicializado em ∣0⟩ que será usado para determinar o

sucesso do algoritmo, um registrador de n qubits de memória inicializado em ∣0⟩⊗n

e o estado de entrada ∣b⟩ .

3.4.1 Simulação hamiltoniana

Como vimos na seção 2.1.8, a evolução temporal de um estado quântico é descrita

pela equação de Schrödinger

i~ ddt

∣ψ(t)⟩ =H(t) ∣ψ(t)⟩ (3.9)

em que H(t) é o operador hermitiano atuando em n qubits (e, portanto, de di-

mensão 2n × 2n) chamado hamiltoniano. Como o hamiltoniano, em sua denição

matricial, é hermitiano, o estado nal da evolução ∣ψ(t)⟩ e o estado inicial ∣ψ(0)⟩

estão relacionados por uma transformação unitária (e, portanto, reversível) Ut,0:

∣ψ(t)⟩ = Ut,0 ∣ψ(0)⟩ . (3.10)

Aplicando a condição na equação de Schrödinger, temos:

i~ ddt

∣ψ(t)⟩ = i~ ddtUt,0 ∣ψ(0)⟩ =H(t)Ut,0 ∣ψ(0)⟩ . (3.11)

3.4. PREPARAÇÃO DA ENTRADA 38

Como ∣ψ(0)⟩ é um ket constante (representando o estado inicial do sistema, em

t = 0), e como a equação acima é verdadeira para qualquer ket em um espaço de

Hilbert, o operador de evolução sobre o tempo deve satisfazer

i~ ddtUt,0 =H(t)Ut,0. (3.12)

A equação acima é um caso de equação diferencial ordinária com coeciente

matricial, cuja resolução nos dará que

Ut,0 = e−iH(t−t0)/~ = e−iHt/~, (3.13)

se supusermos que o operadorH independe do tempo, como é o caso do Hamiltoniano

do algoritmo de resolução de sistemas lineares aqui apresentado. A solução pode ser

vericada se expandirmos a função exponencial como série de Taylor (como descrito

na seção 2.1.6.2) e diferenciarmos termo a termo com respeito ao tempo t.

Voltando ao contexto do algoritmo a ser exposto, a matriz de entrada A do sis-

tema linear é s-esparsa. Para sermos capazes de simular o Hamiltoniano do sistema,

decomporemos a matriz na forma A = ∑mj=1Aj, onde cada Aj é 1-esparso, isto é, tem

no máximo uma entrada diferente de zero por linha/coluna. Os Aj são chamados

Hamiltonianos locais, e só atuam em O(1) qubits cada [22].

Uma vez com os valores das simulações de cada Aj, é possivel simular, eciente-

mente, a matriz A através do operador e−iAt em tempo O(log(N)s2t) [23].

Poderemos também executar o algoritmo de resolução no caso em que A não é

hermitiana, relaxando a hipótese original. Neste caso, deniremos

C =⎡⎢⎢⎢⎢⎢⎣

0 A

A 0

⎤⎥⎥⎥⎥⎥⎦, (3.14)

que é, por sua vez, uma matriz hermitiana. Tendo obtido C, poderemos resolver a

equação

Cy =⎡⎢⎢⎢⎢⎢⎣

b

0

⎤⎥⎥⎥⎥⎥⎦(3.15)

3.5. O ALGORITMO 39

utilizando o algoritmo de resolução de sistemas lineares e, então, obteremos

y =⎡⎢⎢⎢⎢⎢⎣

0

x

⎤⎥⎥⎥⎥⎥⎦. (3.16)

3.4.2 Codicando b em ∣b⟩

Para produzir o estado de entrada ∣b⟩ , suporemos que existe um operador unitá-

rio B que produzirá o estado esperado, possivelmente com lixo em um registrador

auxiliar. A preparação deste operador pode fazer parte de um algoritmo externo

e mais complexo, assim como ser um procedimento como em [24], que descreve a

criação de uma superposição quântica de forma

∣ψ(pi)⟩ =∑i

√pi ∣i⟩ (3.17)

dada uma distribuição probabilística pi, e em que ∣i⟩ representa um dos vetores

de uma base ortonormal.

É importante notar que, uma vez que a preparação de ∣b⟩ através de B é uma

rotina externa ao algoritmo aqui apresentado, não temos outra forma de produzir

o estado esperado assim como também não é possível executar alguma vericação

sobre a estrutura de ∣b⟩ de forma a detectar e mitigar possíveis erros provenientes de

sua produção. Assim, todo e qualquer erro na produção de ∣b⟩ irá necessariamente

ser propagado em erros no estado nal ∣x⟩ obtido pelo algoritmo de resolução de

sistemas lineares descrito a seguir.

3.5 O algoritmo

Suponhamos que a equação Ax = b tenha sido dada, em que b tem N entradas, e

também que b foi mapeado em um estado quântico ∣b⟩ de log2N qubits e A em um

operador quântico, de modo que possamos nos beneciar do paralelismo quântico ao

avaliar a aplicação de uma certa função em superposição. O algoritmo apresentado a

seguir aplicará a transformação eiAt ∣b⟩ para, através da sub-rotina de estimativa de

fase, decompor o estado quântico ∣b⟩ no conjunto de autovetores de A e encontrar os

3.5. O ALGORITMO 40

autovalores λj associados. Para a inversão da matriz A, bastará que encontremos

o recíproco de cada um dos autovalores. Uma vez que estes autovalores estarão

emaranhados no estado quântico obtido, será necessário aplicar uma operação não-

linear de rotação, controlada por cada autovalor invertido, de forma a modicar

o qubit auxiliar para que possamos determinar o sucesso ou falha da execução do

algoritmo. A seguir, uma medição será feita neste qubit, na tentativa de obter

um resultado bem sucedido. Como o algoritmo é probabilístico, existe sempre a

possibilidade de retornar um estado que não corresponde a uma solução do sistema

dado. Dada a medição esperada, será possível extrair o estado ∣x⟩ = A−1 ∣b⟩ . A

execução do procedimento cresce poli-logarítmicamente com a dimensão N , como

será descrito nas seções a seguir.

O algoritmo produz uma representação mecânico-quântica do vetor buscado x.

Para obter todos os componentes deste vetor, seria necessário executar o algoritmo

N vezes, de forma a ler uma entrada por vez. Porém, quando se está interessado em

obter um valor médio xTMx dado por um operador linear qualquer M , que possa

ser mapeado em um operador quântico, pode-se obter tal estimativa ao realizar

⟨x∣M ∣x⟩ , e, neste caso, o ganho de complexidade em comparação aos algoritmos

clássicos será exponencial, permitindo o processamento de uma grande massa de

dados em um tempo de ordem logarítmica.

Apresentamos a seguir cada passo do algoritmo desenvolvido em [8]. Nas seções

seguintes, detalhamos a análise de complexidade do procedimento, e destacamos

alguns experimentos realizados sobre esta base teórica.

Na gura 3.2, podemos ver em mais detalhes cada etapa do algoritmo represen-

tadas num circuito quântico. Uma vez preparada a entrada do algoritmo, teremos

o estado inicial

∣ψ0⟩ = ∣0⟩ ⊗ ∣0l⟩ ⊗ ∣0m⟩ ⊗ ∣0t⟩⊗ ∣b⟩ , (3.18)

em que temos um qubit auxiliar, além de l, m e t qubits inicializados em ∣0⟩ nos

registradores L, M e C, respectivamente, e o estado de entrada ∣b⟩ inicializado no

registrador B.

3.5. O ALGORITMO 41

Figura 3.2: Circuito para resolução de sistemas lineares, adaptado de [2], em que

REC representa a rotina de cálculo do recíproco dos autovalores λj da matriz A.

O número de qubits que serão utilizados nos registradores L e M é inuenciado

por dois fatores. A precisão desejada para codicar binariamente os autovalores λj

de A e seus recíprocos1

λj. Assim, se a precisão buscada for O(2q), serão necessários

q qubits. Em segundo lugar, o número de qubits depende do número de condição κ

da matriz A, uma vez que o funcionamento do circuito de inversão de autovalores

requer que 2m seja maior do que todos os autovalores de A, isto é, m ≥ ⌈logλmax⌉

e que o registrador L tenha qubits sucientes para que o maior1

λmin

possa ser

codicado, ou seja, l ≥ ⌈logλmin⌉. Reunindo as duas condições, teremos que

m − l ≈ logλmax

λmin

≈ logκ. (3.19)

Para facilitar a descrição do circuito quântico, analisaremos separadamente a

evolução do estado ao longo das várias transformações requeridas pelo algoritmo.

Podemos notar que, inicialmente, os registradores C e B são transformados separa-

damente dos registradores L e M : faremos então a descrição isoladamente até que

seja necessário unir os estados.

3.5. O ALGORITMO 42

Figura 3.3: Etapa inicial de transformação dos registradores C e B.

3.5.1 Registradores C e B

3.5.1.1 Balanceamento de Hadamard

Partiremos do estado

∣η0⟩ = ∣0t⟩ ⊗ ∣b⟩ . (3.20)

A primeira porta a ser aplicada é a porta de Hadamard no registrador C, de forma

a balancear o estado para obtermos

∣η1⟩ =1

(√

2)t2t−1∑σ=0

∣σ⟩ ⊗ ∣b⟩ . (3.21)

O próximo passo é a aplicação da evolução hamiltoniana no registrador B controlada

pelo registrador C.

3.5.1.2 Evolução hamiltoniana

Como vimos, o operador de evolução sobre o tempo, que se utiliza do hamilto-

niano do sistema linear é dado por

U(t) = e−iAt. (3.22)

Introduziremos aqui os autovalores e autovetores do hamiltoniano H que devem

satisfazer

H ∣ψj⟩ = λj ∣ψj⟩ . (3.23)

Este conjunto de autovetores forma uma base ortonormal completa para um

espaço de Hilbert. Portanto, um estado ∣φ(t)⟩ , qualquer, pode ser expandido sobre

eles de acordo com uma combinação linear dos autovetores que formam a base de

3.5. O ALGORITMO 43

autovalores deste espaço, ou seja,

∣φ(t)⟩ =∑j

ϕj(t) ∣µj⟩ , (3.24)

em que ϕj(t) = ⟨µj ∣φ(t)⟩ representa a amplitude para obtenção do valor µj se for

feita uma medição do estado em que foi aplicado H no tempo t, [25], [26].

Vamos, para ns do algoritmo, supor hamiltonianos independentes do tempo e

desta forma, expandir o estado ∣b⟩ sobre a base de autovalores de A, obtendo

∣b⟩ =n

∑j=1βj ∣ψj⟩ , (3.25)

em que ∣ψj⟩ são os autovetores de A e βj é independente do tempo t. Poderemos,

então, escrever o estado ∣η1⟩ como

∣η1⟩ =1

(√

2)t2t−1∑σ=0

∣σ⟩ ⊗n

∑j=1βj ∣ψj⟩ , (3.26)

ou também

∣η1⟩ =1

(√

2)t2t−1∑σ=0

n

∑j=1βj ∣σ⟩ ∣ψj⟩ . (3.27)

3.5. O ALGORITMO 44

Figura 3.4: Aplicação da simulação hamiltoniana controlada.

Como A ∣ψj⟩ = λj ∣ψj⟩ , então, a exponenciação de A aplicado em ∣ψj⟩ resultará

em

eA ∣ψj⟩ =∞∑r=0

Ar

r!∣ψj⟩ =

∞∑r=0

λrjr!

∣ψj⟩ = eλj ∣ψj⟩ , (3.28)

como descrito na seção 2.1.6.2. Estendendo esta denição para o caso estudado,

basta substituirmos o expoente do operador pelo desejado:

e−iAt0

2t ∣b⟩ =n

∑j=1e−iλjt0

2t βj ∣ψj⟩ , (3.29)

em que vamos denir a fase t0 = 2π. Além disso, também precisaremos incluir a

exponenciação do valor da kt-ésima posição da expansão binária de σ nos casos em

que o valor de controle da porta lógica for não-nulo. Unindo todas essas denições,

quando aplicarmos a simulação hamiltoniana em ∣b⟩ , teremos

n

∑j=1e−i2πλj

2tσβj ∣ψj⟩ . (3.30)

Em suma, a aplicação da simulação hamiltoniana controlada pelo registrador C

transformará o estado ∣η1⟩ em

∣η2⟩ =1

(√

2)t2t−1∑σ=0

n

∑j=1βje

2πiλj

2tσ ∣σ⟩ ∣ψj⟩ , (3.31)

que novamente, pode ser reescrito como

∣η2⟩ =1

(√

2)tn

∑j=1βj

⎛⎝

2t−1∑σ=0

e2πiλj

2tσ ∣σ⟩

⎞⎠∣ψj⟩ . (3.32)

3.5.1.3 Transformada de Fourier

O último passo desta etapa é a aplicação da transformada de Fourier inversa

no registrador C, isto é, em ∣σ⟩ . Como vimos na seção 2.2.5, a aplicação da

3.5. O ALGORITMO 45

transformada de Fourier em um estado ∣φ⟩ = ∑µ−1j=0 αj ∣j⟩ , de µ entradas, tem o

seguinte comportamento:

F ∣φ⟩ =µ−1∑k=0

⎛⎝

1√µ

µ−1∑j=0

αje2πijk/µ⎞

⎠∣k⟩ . (3.33)

Aplicando-o ao primeiro registro de ∣η2⟩ , obteremos

F ∣σ⟩ = 1

(√

2)t2t−1∑τ=0

e−2πiτ

2tσ ∣τ⟩ (3.34)

e assim,

∣η3⟩ =1

(√

2)t1

(√

2)tn

∑j=1βj

⎡⎢⎢⎢⎢⎣

2t−1∑σ=0

e2πiλj

2tσ(

2t−1∑τ=0

e−2πiτ

2tσ ∣τ⟩)

⎤⎥⎥⎥⎥⎦∣ψj⟩ , (3.35)

que pode ser reescrito como

∣η3⟩ = ( 1√2)2t n

∑j=1βj

2t−1∑τ=0

(2t−1∑σ=0

e2πiσ2t(λj−τ)) ∣τ⟩ ∣ψj⟩ . (3.36)

3.5.1.4 Simplicação do estado

Antes de seguir adiante com o circuito do algoritmo, vamos denir k = λj − τ .

Podemos notar que o termo

2t−1∑σ=0

e2πiσ2t(λj−τ) =

2t−1∑σ=0

e2πiσ2t

k (3.37)

pode ser reescrito como uma soma de progressão geométrica de razão e2πi2tk, de forma

2t−1∑σ=0

(e2πi2tk)

σ

= 1 + (e2πi2tk) + (e

2πi2tk)

2

+⋯ + (e2πi2tk)

2t−1

. (3.38)

Resolvendo esta soma, teremos que, se k ≠ 0, então

2t−1∑σ=0

(e2πi2tk)

σ

=1 − (e

2πi2tk)

2t−1

(e2πi2tk)

1 − e2πi2tk

= 1 − e2πik

1 − e2πi2tk, (3.39)

que se anula, uma vez que e2πik = 1 pela fórmula de Euler eix = cosx + i senx. Logo,

toda vez que λj ≠ τ o valor deste termo se anulará. Assim, poderemos simplicar a

expressão de ∣η3⟩ para mantermos somente os termos em que τ = λj e

2t−1∑σ=0

e2πiσ2t(λj−τ) =

2t−1∑σ=0

1 = 2t. (3.40)

3.5. O ALGORITMO 46

Agora que temos τ = λj, reescreveremos ∣η3⟩ como

∣η3⟩ = ( 1√2)2t

2tn

∑j=1βj ∣λj⟩ ∣ψj⟩ =

n

∑j=1βj ∣λj⟩ ∣ψj⟩ . (3.41)

Finalizada a etapa inicial dos registradores C e B, é importante notar que a

simulação hamiltoniana é um passo chave do algoritmo, pois é onde está o grande

benefício da utilização de operadores quânticos: o paralelismo quântico colocará o

segundo registro do estado em superposição quântica associada a todos os autova-

lores da matriz A. Além disso, devemos lembrar, que o valor λj obtido em ∣η3⟩

foi codicado por um número nito de qubits, e portanto, não é o valor exato do

autovalor de A, mas sim uma aproximação sob um certo grau de precisão baseado

nos fatores já descritos acima.

3.5.2 Inversão de autovalores

Até o momento, o estado global do sistema que obtemos após a aplicação das

portas nos registradores C e B é

∣ρ⟩ = ∣0⟩ ⊗ ∣0l⟩ ⊗ ∣0m⟩ ⊗ ∣η3⟩ (3.42)

= ∣0⟩ ⊗ ∣0l⟩ ⊗ ∣0m⟩ ⊗n

∑j=1βj ∣λj⟩ ∣ψj⟩ . (3.43)

Neste passo, estamos interessados em extrair os autovalores de A−1 para que possa-

mos calcular a inversão da matriz A pela inversão de seus autovalores. Através da

utilização do método de Newton, descrito no caso geral no apêndice D, calcularemos

a raiz da função

g(x) = 1

x− λ, (3.44)

em que λ é o autovalor cujo recíproco buscamos, uma vez que

g(x) = 0↔ x = 1

λ. (3.45)

A iteração de Newton para a função g será dada por

xi+1 = xi +g(xi)g′(xi)

= xi +1xi− λ1x2i

= 2xi − λx2i . (3.46)

3.5. O ALGORITMO 47

Para cada autovalor λj, em que λj > 1, utilizaremos uma aproximação inicial

x0 ≈ 2−p, de forma que 2p−1 < λj < 2p, ou seja, p é o expoente da potência de 2

imediatamente seguinte a λj. Vale notar que x0 não é exatamente igual a 2−p, uma

vez que sua representação binária é uma aproximação por truncamento em m bits

de precisão do valor real.

O circuito para a estimativa de x0 que aplica a transformação

∣0m⟩ ∣λj⟩ → ∣x0⟩ ∣λj⟩ , se λj > 1 ; (3.47)

∣0m⟩ ∣λj⟩ → ∣0m⟩ ∣λj⟩ , caso contrário (3.48)

está apresentado em [27].

Uma vez obtida a aproximação inicial xj0 para o método de Newton que calculará

o recíproco do autovalor λj, podemos executar as iterações

xi+1 = 2xi − λx2i (3.49)

usando um circuito quântico como o representado na gura 3.5. Este tipo de circuito

pode ser implementado através da concatenação de circuitos quânticos para adição

e multiplicação, como os que estão descritos na literatura [27].

Figura 3.5: Circuito implementando cada passo iterativo do método de Newton,

adaptado de [2].

O estado obtido após a inversão dos autovalores através da aplicação do método

de Newton será

∣υ0⟩ =n

∑j=1βj ∣ϑj⟩ ∣λj⟩ ∣ψj⟩ , (3.50)

em que ∣ϑj⟩ ≈ ∣1/λj⟩ , ou seja, poderíamos escrever

∣υ0⟩ ≈n

∑j=1βj ∣1/λj⟩ ∣λj⟩ ∣ψj⟩ . (3.51)

3.5. O ALGORITMO 48

3.5.3 Rotação controlada

Partindo do estado obtido da inversão de autovalores, adicionaremos um qubit

auxiliar e realizaremos a rotação Ry controlada pelo qubit ∣ϑj⟩ .

Antes, é importante denir a rotação. A matriz de rotação Ry é dada por

Ry =⎡⎢⎢⎢⎢⎢⎣

cos θ2 sen θ2

− sen θ2 cos θ2

⎤⎥⎥⎥⎥⎥⎦= e−i θ2σy , (3.52)

em que σy é a matriz Y de Pauli

σy =⎡⎢⎢⎢⎢⎢⎣

0 −i

i 0

⎤⎥⎥⎥⎥⎥⎦, (3.53)

que mapeia os estados de forma

σy ∣0⟩ → i ∣1⟩ (3.54)

σy ∣1⟩ → − i ∣0⟩ . (3.55)

Então, a aplicação de Ry(θ) terá o mesmo efeito que aplicar a operação

Ry(θ) = e−iθ2σy = cos

θ

21 − i sen

θ

2σy. (3.56)

Finalmente, voltando ao estado do sistema estudado, adicionando o qubit auxi-

liar, caremos com

∣υ1⟩ = ∣0⟩ ⊗n

∑j=1βj ∣ϑj⟩ ∣λj⟩ ∣ψj⟩ , (3.57)

e aplicando a rotação controlada, teremos

∣υ2⟩ =n

∑j=1

( cosϑj21 − i sen

ϑj2σy) ∣0⟩ ⊗ βj ∣ϑj⟩ ∣λj⟩ ∣ψj⟩

=n

∑j=1

( cosϑj2

∣0⟩ − i senϑj2⋅ i ∣1⟩)⊗ βj ∣ϑj⟩ ∣λj⟩ ∣ψj⟩

=n

∑j=1

( cosϑj2

∣0⟩ + senϑj2

∣1⟩)⊗ βj ∣ϑj⟩ ∣λj⟩ ∣ψj⟩

Como sabemos,

sen 2 (ϑj2) + cos2 (

ϑj2) = 1, (3.58)

3.5. O ALGORITMO 49

e então

cos(ϑj2) =

√1 − sen 2 (

ϑj2). (3.59)

Escolhendo a constante C tal que

C

λj= sen (

ϑj2) , (3.60)

podemos reescrever o estado como

∣υ2⟩ =n

∑j=1

(¿ÁÁÀ1 − C

2

λ2j∣0⟩ + C

λj∣1⟩)⊗ βj ∣ϑj⟩ ∣λj⟩ ∣ψj⟩ , (3.61)

em que 0 < C ≤ minjλj, ou seja C = O(1/κ). Unindo os termos do produto

tensorial, obteremos

∣υ2⟩ =n

∑j=1βj(

¿ÁÁÀ1 − C

2

λ2j∣0⟩ + C

λj∣1⟩) ∣ϑj⟩ ∣λj⟩ ∣ψj⟩ . (3.62)

Vale lembrar que, para valores deϑj2

pequenos, teremos sen (ϑj2) ≈

ϑj2, e nestes

casos, C ≈ϑjλj

2.

3.5.4 Computação reversa

Como vimos na seção 2.2.2.2, as portas quânticas unitárias são reversíveis. Por-

tanto, é simples desfazer as operações aplicadas nos passos anteriores: rotações de

ângulo θ, operadores hamiltonianos do tipo e−iAt e a transformada de Fourier serão

revertidas por rotações em −θ, operadores hamiltonianos em eiAt e pela transformada

de Fourier inversa (FT ), respectivamente.

O estado que tínhamos será então alterado de forma que o segundo e terceiro

registradores sejam desemaranhados ao estado 0⊗l e 0⊗m. Assim, terminaremos com

o estado

∣ν⟩ =n

∑j=1βj(

¿ÁÁÀ1 − C

2

λ2j∣0⟩ + C

λj∣1⟩) ∣0l⟩ ∣0m⟩ ∣ψj⟩ . (3.63)

Passando a levar em conta somente o primeiro e último registradores, podemos

escrever o estado ∣ν⟩ na forma

∣ν⟩ =n

∑j=1βj(

¿ÁÁÀ1 − C

2

λ2j∣0⟩ + C

λj∣1⟩) ∣ψj⟩

=n

∑j=1

¿ÁÁÀ1 − C

2

λ2j∣0⟩βj ∣ψj⟩ +

n

∑j=1

C

λj∣1⟩βj ∣ψj⟩ .

3.5. O ALGORITMO 50

Lembrando que ∣b⟩ = ∑nj=1 βj ∣ψj⟩ , vamos utilizar o fato que

A−1 ∣b⟩ = A−1n

∑j=1βj ∣ψj⟩

=n

∑j=1βjA

−1 ∣ψj⟩

=n

∑j=1βj

1

λj∣ψj⟩ ,

e que

A ∣ψj⟩ = λj ∣ψj⟩

∣ψj⟩ = λjA−1

²I

∣ψj⟩ ,

e assim, seguiremos a simplicação de ∣ν⟩ :

∣ν⟩ =n

∑j=1

√λ2j −C2

λj∣0⟩βj ∣ψj⟩ +

n

∑j=1CβjA

−1 ∣1⟩ ∣ψj⟩

=n

∑j=1

√λ2j −C2βjA

−1 ∣0⟩ ∣ψj⟩ +n

∑j=1CβjA

−1 ∣1⟩ ∣ψj⟩

=n

∑j=1

¿ÁÁÀλ2jA

−2

²I2=I

−C2A−2βj ∣0⟩ ∣ψj⟩ +CA−1 ∣1⟩ ∣b⟩

=n

∑j=1

√1 −C2A−2βj ∣0⟩ ∣ψj⟩ +CA−1 ∣1⟩ ∣b⟩

=√1 −C2A−2 ∣0⟩ ∣b⟩ +CA−1 ∣1⟩ ∣b⟩

= ∣0⟩(√1 −C2A−2 ∣b⟩) + ∣1⟩(CA−1 ∣b⟩).

3.5.5 Medição

Condicionaremos o sucesso da execução do algoritmo ao resultado obtido pela

medição do qubit auxiliar que introduzimos juntamente com os dados da entrada

do sistema. Como podemos ver pela descrição de nosso estado atual:

∣ν⟩ = ∣0⟩(√1 −C2A−2 ∣b⟩) + ∣1⟩(CA−1 ∣b⟩), (3.64)

quando a medição do qubit auxiliar resultar na projeção em ∣1⟩ , o estado do sistema

será então transformado em

∣1⟩aux.

n

∑j=1Cβjλ

−1j ∣ψj⟩ , (3.65)

3.5. O ALGORITMO 51

que é proporcional ao estado que buscamos calcular ∣x⟩ = ∑j βjλ−1j ∣ψj⟩ .

Seremos capazes de determinar a constante de normalização a partir da proba-

bilidade de obter ∣1⟩ no último passo. Como o estado nal do algoritmo pode ser

escrito comon

∑j=1

¿ÁÁÀ1 − C

2

λ2j∣0⟩βj ∣ψj⟩ +

n

∑j=1

C

λj∣1⟩βj ∣ψj⟩ , (3.66)

basta exponenciar à segunda potência a amplitude do caso de obtenção de ∣1⟩ ,

obtendo

p(obter ∣1⟩) =n

∑j=1

C2

λ2j× βj2, (3.67)

que é da ordem O(1/κ2) uma vez que C = O(1/κ).

Por outro lado, se a medição do qubit auxiliar for projetada em ∣0⟩ , o estado em

que o sistema colapsará será

∣0⟩aux.

∣b⟩ (3.68)

que é justamente o estado de entrada do algoritmo. Poderemos então utilizar esta

saída como entrada de uma nova iteração do circuito, e executá-lo até que a medição

bem sucedida seja obtida.

Finalmente, faremos uma medição M cujo valor médio (esperança) ⟨x∣M ∣x⟩

corresponde à propriedade de x que gostaríamos de avaliar.

Capítulo 4

Resultados e trabalhos relacionados

Apresentaremos nesta seção uma breve análise da complexidade do algoritmo

de resolução apresentado anteriormente. Além disso, vamos compará-lo com os

algoritmos mais utilizados classicamente, explicitando assim a melhora em eciência

existente nas execuções quânticas.

Serão expostas também referências a trabalhos relacionados no que se refere às

diversas implementações físicas já realizadas e seus resultados, assim como também

às nuances teóricas de cada implementação.

4.1 Comparação de eciência: Clássico × Quântico

A etapa de simulação quântica de e−iAt, em que supomos A s-esparsa, pode ser

feita em tempo linear em t e quadrático em s, [8], [6]. A sub-rotina de estimativa de

fase introduzirá um erro de ordem O(1/t) enquanto estima o autovalor λ, e que será

propagado em um erro relativo de O(1/λt) quando consideramos a inversão λ−1.

Como temos que λ ≥ 1/κ, onde κ é o número de condição da matriz A, se tomarmos

t = O(κ/ε), o erro aproximado ao nal do processo será da ordem O(ε).

Considerando agora a probabilidade de uma medição com sucesso do qubit au-

xiliar introduzido na fase de rotação do algoritmo, como C = O(1/κ) e λ ≤ 1, esta

probabilidade é de pelo menos Ω(1/κ2). Utilizaremos o algoritmo de amplicação

4.2. EXPERIMENTOS 53

de amplitude [28], descrito no apêndice C, para diminuir o número de tentativas de

obtenção do caso de sucesso e concluiremos que serão necessárias no máximo O(κ)

repetições.

Simplicando a análise, teremos então uma complexidade para este algoritmo de

ordem

O( log2 (N)s2t´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

estimativa de fase

) com t = O(κ/ε)

O⎛⎝

log2 (N)s2´¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

estimativa de fase

evol. hamilt. em t©κ

ε

⎞⎠× O(κ)

²repetições

= O⎛⎝

log2 (N)s2κ2ε

⎞⎠. (4.1)

Como vimos nas seções 3.1.1 e 3.1.2, a análise de complexidade dos algoritmos

clássicos exige operações desde ordem O(N3) até O(m√κ) = O(Ns

√κ log (1/ε)) no

melhor caso [8]. Em comparação com o que foi obtido aqui, vemos que a dependência

do algoritmo quântico em N (dimensão da matriz de entrada) é exponencialmente

melhor, sendo a s e κ comparáveis, enquanto a dependência em ε é exponencial-

mente pior (o que faz sentido intuitivamente, levando em consideração a melhora

na dependência em N), [29].

Os autores em [8] demonstram ainda a impossibilidade de melhorar a eciência

do algoritmo quântico na dependência em ε, ao tentar obter uma dependência similar

ao caso clássico de tempo log (1/ε), [30].

4.2 Experimentos

Desde a publicação do artigo original, [8], alguns grupos de pesquisadores in-

vestiram esforços em executá-lo experimentalmente, para comprovar sua corretude

e sobretudo, sua eciência. Destacamos aqui três experimentos realizados quase

concomitantemente.


4.2.1 Barz et. al [3]

A utilização de qubits codicados pela polarização fotônica, com ∣0⟩ e ∣1⟩ deno-

tando a polarização horizontal e vertical, respectivamente, e a aplicação de dois tipos

de portas CNOT adaptadas (o primeiro tipo representa a lógica da porta CNOT, e

o segundo tipo realiza a medição de forma destrutiva através da utilização de um

separador de raios dependente da polarização - ou polarisation-dependent beam split-

ter, PDBS, no inglês), em conjunto com operações locais unitárias, foram capazes

de implementar o circuito do algoritmo.

Nos experimentos relatados em [3], foram variados alguns parâmetros, dentre

eles a matriz de entrada A (mantendo ou alterando seus autovalores) e o estado ∣b⟩ ,

e feita a medição do qubit auxiliar para o estado esperado ∣1⟩ .

Foram obtidos valores de delidade de mais de 90% para os sistemas lineares

selecionados através das matrizes de entrada.

Figura 4.1: Resultados obtidos, adaptado de [3].


4.2.2 Pan et. al [4]

Diferentemente do primeiro experimento, neste foram utilizados um núcleo de

carbono-13 e três núcleos de úor-19 em uma implementação de ressonância nuclear

magnética (a NMR, na sigla em inglês, utiliza o spin das moléculas como qubits)

para representar um sistema de quatro qubits. O sistema é preparado em um estado

pseudo-puro usando o método da transição seletiva por linha, descrito em [31] e [32].

O algoritmo de sistemas lineares é, então aplicado, ao estado preparado usando um

pulso de formato de rádio-frequência e o estado nal é medido para obter a solução

do sistema de equações.

No artigo, foram preparados três diferentes b e, enquanto os erros mensurados

estiveram em torno de 7%, a delidade experimental rondou 96%.


4.2.3 Cai et. al [5]

Assim como no primeiro experimento, aqui são preparados quatro fótons como

qubits de entrada para codicar os qubits lógicos baseados na polarização. A etapa

da estimativa de fase é implementada usando um PDBS para emular as portas

CNOT e a rotação utiliza-se de portas unitárias controladas. O qubit auxiliar é

medido para determinar o sucesso do algoritmo.

São selecionados três vetores de entrada para os experimentos: ∣b1⟩ = (∣H⟩ +

∣V ⟩)/√

2, ∣b2⟩ = (∣H⟩ − ∣V ⟩)/√

2 e ∣b3⟩ = ∣H⟩ , onde ∣H⟩ e ∣V ⟩ representam os estados

de polarização fotônica. O algoritmo é então aplicado para determinar o valor médio


⟨x∣M ∣x⟩ onde M é um operador, sendo este no caso dos experimentos testado com

os valores dos operadores de Pauli. Os estados de saída são medidos com delidade

de 0.993, 0.825 e 0.836 para cada ∣bi⟩ respectivamente.


As diferenças em performance na aplicação do algoritmo para as entradas seleci-

onadas estão ligadas à conguração ótica inicial usada no experimento, por eventos

de decoerência dos fótons e a precisão da simulação das portas CNOT através do

PDBS. Ainda assim, a delidade obtida nos experimentos realizados ca em torno

dos 90%.

Capítulo 5

Implementação

Após a apresentação teórica do algoritmo e de práticas utilizando elementos

da física experimental, apresentaremos aqui uma implementação computacional do

mesmo, utilizando a plataforma gratuita para computação numérica Scilab. O ob-

jetivo deste capítulo é demonstrar o funcionamento do algoritmo, simulando um

computador quântico através da implementação clássica e utilizando um sistema

simplicado de forma a diminuir o número de portas lógicas necessárias para mode-

lar as etapas do circuito quântico.

O sistema linear que será resolvido será de forma Ax = b, em que A é uma matriz

2×2 hermitiana e com autovalores que possam ser representados como potências de

2, e b é um vetor 2 × 1 qualquer.

Para a execução que faremos, a entrada escolhida é

A =⎛⎜⎝

3 1

1 3

⎞⎟⎠

(5.1)

b =⎛⎜⎝

1

0

⎞⎟⎠, (5.2)

que formará então o sistema

⎛⎜⎝

3 1

1 3

⎞⎟⎠

⎛⎜⎝

x1

x2

⎞⎟⎠=⎛⎜⎝

1

0

⎞⎟⎠. (5.3)

58

Podemos notar que A é hermitiana, uma vez que A = A, seus autovalores são

λ1 = 2 = 21 e λ2 = 4 = 22 e sua diagonalização pode ser escrita como

A = S ⋅D ⋅ S−1 =⎛⎜⎝

−1 1

1 1

⎞⎟⎠⋅⎛⎜⎝

2 0

0 4

⎞⎟⎠⋅⎛⎜⎝

−12

12

12

12 .

⎞⎟⎠. (5.4)

Resolvendo classicamente o sistema, é fácil encontrar as entradas de x, que equivalem

a

x =⎛⎜⎝

x1

x2

⎞⎟⎠=⎛⎜⎝

38

−18

⎞⎟⎠. (5.5)

O circuito quântico implementado para resolver este tipo de sistema é uma sim-

plicação do circuito apresentado na gura 3.2, de forma que a etapa de inversão

de autovalores é substituída por portas SWAP. Como os autovalores da matriz de

entrada são potências de 2, e podem ser escritos facilmente através de sua repre-

sentação binária, a troca de posições binárias bastará para inverter os autovalores.

No caso do sistema proposto, em que o registrador C tem três qubits e utilizando a

matriz A escolhida anteriormente, teremos

∣λ1⟩ = ∣2⟩ = ∣010⟩CSWAPÐÐÐ→ ∣001⟩ = ∣4⟩ = ∣12 × 23⟩ ;

∣λ2⟩ = ∣4⟩ = ∣001⟩CSWAPÐÐÐ→ ∣010⟩ = ∣2⟩ = ∣14 × 23⟩ .

O circuito simplicado completo para resolver este sistema está representado na

gura 5.1.

O sistema é inicializado em ∣ψ0⟩ = ∣0000b⟩ em que

∣b⟩ = b1,1 ∣0⟩ + b2,1 ∣1⟩ , (5.6)

e a aplicação das portas lógicas quânticas é representada matematicamente pela

multiplicação dos operadores matriciais que representam cada transformação. A

aplicação das primeiras portas de Hadamard no registrador C, por exemplo, será

representada pela multiplicação

∣ψ1⟩ = (I2×2 ⊗H ⊗H ⊗H ⊗ I2×2) ⋅ ∣ψ0⟩ , (5.7)

em que

H = 1√2

⎛⎜⎝

1 1

1 −1

⎞⎟⎠. (5.8)

59

Figura 5.1: Circuito quântico para resolução do sistema Ax = b com A2×2 e precisão

m na etapa de rotação. De cima para baixo temos o qubit auxiliar, três qubits para

o registrador C e um qubit que armazena ∣b⟩ . Adaptado de [2].

Da mesma forma que na análise teórica do algoritmo, selecionamos t0 = 2π para

aplicação da simulação hamiltoniana, e teremos um parâmetro m que representa a

precisão das rotações Ry aplicadas ao qubit auxiliar do sistema.

A saída do algoritmo, cujo código está reproduzido no apêndice E, para o sistema

linear apresentado acima, tendo selecionado m = 2 como precisão das rotações, está

no apêndice F. O estado resultante da execução do algoritmo imediatamente antes

da medição bem sucedida é dado por

psi_9 = −0.125|00000> + −0.375|00001> + %i *0.375|00010 > + −%i *0.375|00011 > +

−0.125|00100> + 0.125|00101 > + −%i *0.375|00110 > + −%i *0.125|00111 > +

0.375|10000 > + 0.125|10001 > + −%i *0.125|10010 > + %i *0.125|10011 > +

−0.125|10100> + 0.125|10101 > + −%i *0.375|10110 > + −%i *0.125|10111 >

60

que como podemos ver, é uma combinação de estados quânticos cujas amplitudes

variam entre os valores −0.375, −0.125, 0.125 e 0.375 na dimensão real e complexa.

Ora, estes valores são proporcionais justamente aos valores das entradas de x que

calculamos classicamente em 5.5!

Capítulo 6

Trabalhos Futuros

A aplicação do solucionador quântico de equações pode ser estendida para uma

grande variedade de campos do conhecimento como, por exemplo, a resolução de

equações de Poisson na química quântica até aplicações práticas de modelagem,

como descrito na seção 3.3.

Um dos objetivos deste trabalho é justamente motivar experimentalistas com

capacidade de utilizar mais qubits do que o atual estado-da-arte em seus experi-

mentos, de forma a resolver sistemas de equações mais complexas e dessa forma, se

beneciar do aumento exponencial de eciência do método quântico.

A sequência deste trabalho envolve, portanto, a descrição e resolução de sistemas

lineares com número de condição mais alto com as chamadas matrizes mal condici-

onadas [33] e/ou a diminuição da dependência dos circuitos neste parâmetro, o que

permitirá o aumento da dimensão das matrizes em tais sistemas sem a preocupação

tão presente com a dimensão física dos registradores quânticos a serem construídos

para sua execução.

Além disso, seria interessante a investida na implementação demonstrativa de

sistemas de dimensão maior que 2×2, como também o relaxamento das hipóteses da

implementação apresentada no capítulo 5 para as matrizes de entrada do algoritmo.

Exemplos teóricos estão descritos para os casos até dimensão 8 × 8 em [2], e seria

interessante adaptar o código apresentado neste trabalho para dar um suporte mais

62

abrangente à implementação.

Referências

[1] A. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems

of equations, Phys. Rev. Lett., vol. 103, oct 2009.

[2] R. Libo, Introductory quantum mechanics, pp. 450455, 1980.

[3] D. Newell, The 2010 codata recommended values of the fundamental physical

constants, 2011.

[4] T. C. S. I.-C. Association for Computing Machinery (ACM), Computing cur-

ricula 2005: The overview report, 2005.

[5] F. L. S. da Silva, Computação quântica: O algoritmo de Deutsch e o parale-

lismo quântico, Revista Physicae, 2002.

[6] C. Adami and N. J. Cerf, Quantum computation with linear optics, in Lecture

Notes in Computer Science, pp. 391401, Springer Science Business Media,

1999.

[7] E. Knill, R. Laamme, and G. J. Milburn, A scheme for ecient quantum

computation with linear optics, Nature, vol. 409, pp. 4652, jan 2001.

[8] M. Reck and A. Zeilinger, Experimental realization of any discrete unitary

operator, Phys. Rev. Lett., vol. 73, pp. 5861, jul 1994.

[9] P. Kok, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn, Linear

optical quantum computing with photonic qubits, Reviews of Modern Physics,

vol. 79, pp. 135174, jan 2007.

REFERÊNCIAS 64

[10] G. D. Hutchinson and G. J. Milburn, Nonlinear quantum optical computing

via measurement, Journal of Modern Optics, vol. 51, pp. 12111222, may 2004.

[11] R. W. Farebrother, Linear least squares computations (statistics: A series of

textbooks and monographs), 1988.

[12] J. R. Shewchuk, An introduction to the conjugate gradient method without

the agonizing pain, 1994.

[13] Krishnavedala, This graph shows a series of points (generated by a sin function)

approximated by polinomial curves (red curve is linear, green is quadratic,

orange is cubic and blue is 4th degree), 2011.

[14] N. Wiebe, D. Braun, and S. Lloyd, Quantum data-tting, 2012.

[15] P. Rebentrost, M. Mohseni, and S. Lloyd, Quantum support vector machine

for big feature and big data classication, 2013.

[16] S. Lloyd, Universal quantum simulators, Science, New Series, Vol. 273, No.

5278, 1996.

[17] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Ecient quantum

algorithms for simulating sparse hamiltonians, Comm. Math. Phys., 2007.

[18] L. Grover and T. Rudolph, Creating superpositions that correspond to eci-

ently integrable probability distributions, 2008.

[19] Y. Cao, A. Daskin, S. Frankel, and S. Kais, Quantum circuit design for solving

linear systems of equations, 2011.

[20] Introductory quantum mechanics section V: Time de-

pendence. http://ocw.mit.edu/courses/chemistry/

5-73-introductory-quantum-mechanics-i-fall-2005/lecture-notes/

sec5.pdf, 2005. Accesso: 2014-10-01.

[21] Quantum theory of radiation interactions chapter 5: Time evo-

lution. http://ocw.mit.edu/courses/nuclear-engineering/

http://ocw.mit.edu/courses/chemistry/5-73-introductory-quantum-mechanics-i-fall-2005/lecture-notes/sec5.pdf



http://ocw.mit.edu/courses/nuclear-engineering/22-51-quantum-theory-of-radiation-interactions-fall-2012/lecture-notes/MIT22_51F12_Ch5.pdf


REFERÊNCIAS 65

22-51-quantum-theory-of-radiation-interactions-fall-2012/

lecture-notes/MIT22_51F12_Ch5.pdf, 2012. Acesso: 2014-10-01.

[22] N. Wiebe and M. Roetteler, Quantum arithmetic and numerical analysis using

repeat-until-success circuits, 2014.

[23] M. Nielsen and I. Chuang, Quantum computation and quantum information,

2010.

[24] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude ampli-

cation and estimation, Contemporary Mathematics Series Millenium Volume,

2002.

[25] V. Russo, Quantum algorithm for solving systems of linear equations, 2013.

[26] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, A limit on the speed of

quantum computation in determining parity, Physical Review Letters.

[27] K. S. Barz, M. Ringbauer, Y. O. Lipp, B. Dakic, A. A. Guzik, and P. Walther,

Solving systems of linear equations on a quantum computer, 2013.

[28] J. Pan, Y. Cao, X. Yao, Z. Li, C. Ju, X. Peng, S. Kais, and J. Du, Experimental

realization of quantum algorithm for solving linear systems of equations, 2013.

[29] X. Peng, X. Zhu, X. Fang, M. Feng, K. Gao, X. Yang, and M. Liu, Preparation

of pseudo-pure states by line-selective pulses in nuclear magnetic resonance,

Chemical Physics Letters, vol. 340, pp. 509516, jun 2001.

[30] X. Peng, Z. Luo, W. Zheng, S. Kou, D. Suter, and J. Du, Experimental im-

plementation of adiabatic passage between dierent topological orders, Phys.

Rev. Lett., vol. 113, aug 2014.

[31] X. D. Cai, C. Weedbrook, Z. E. Su, and M. C. et al., Experimental quan-

tum computing to solve systems of linear equations, Physical Review Letters,

no. 230501, pp. 110115, 2013.

[32] A. M. Childs, Quantum algorithms: Equation solving by simulation, Nature

Physics, vol. 5, pp. 861861, dec 2009.




REFERÊNCIAS 66

[33] D. B. Trieu, Large-scale simulations of error prone quantum computation de-

vices, 2009.

[34] L. Grover, Quantum computers can search rapidly by using almost any trans-

formation, Phys. Rev. Lett., vol. 80, pp. 43294332, may 1998.

[35] E. Süli and D. F. Mayers, An Introduction to Numerical Analysis. Cambridge

University Press, 2003.

[36] T. Dence, Cubics, chaos and newton's method, The Mathematical Gazette,

vol. 81, pp. 403408, nov 1997.

[37] E. Weisstein, Newton's method.

Apêndice A

Transformada de Fourier Quântica

Neste apêndice, apresentaremos a transformada de Fourier quântica, que é o

ingrediente chave para muitos algoritmos quânticos interessantes, dentre eles os al-

goritmos de fatoração e resolução de sistemas lineares.

A transformada de Fourier quântica é um algoritmo eciente para realizar a

transformada de Fourier das amplitudes da mecânica quântica. Este algoritmo não é

mais rápido na tarefa de calcular estas mesmas transformadas do que sua contraparte

clássica, mas nos habilita a realizar o algoritmo de estimativa de fase, que aproxima

autovalores de operadores unitários. Isso, por sua vez, nos permite resolver uma

série de outros problemas interessantes, como por exemplo a contagem de soluções

de um problema de busca ou o problema do subgrupo oculto, problemas estes antes

pensados como intratáveis em computadores clássicos.

Na notação matemática usual, a transformada de Fourier discreta toma como

entrada um vetor de números complexos x0,⋯, xN−1 de tamanho xo N . Sua saída

são os dados transformados, um vetor de números complexos y0,⋯, yN−1, denido

por

yk =1√N

N−1∑j=0

xje2πijk/N . (A.1)

A transformada quântica é justamente a mesma transformação, embora a no-

tação utilizada seja um pouco diferente: a transformada de Fourier quântica sobre

uma base ortonormal ∣0⟩ ,⋯, ∣N − 1⟩ é um operador linear que atua da seguinte forma

68

nos estados da base:

∣j⟩ → 1√N

N−1∑k=0

e2πijk/N ∣k⟩ . (A.2)

De forma equivalente, a ação da transformada sobre um estado da base pode ser

descrita comoN−1∑j=0

xj ∣j⟩ →N−1∑k=0

yk ∣k⟩ (A.3)

em que as amplitudes yk são as transformadas de Fourier discretas das amplitudes

xj.

Suponhamos que N = 2n, em que n é um inteiro, e que a base ∣0⟩ ,⋯, ∣2n − 1⟩

é a base computacional para um computador quântico de n qubits. É conveniente

escrever o estado ∣j⟩ usando a representação binária j = j1j2j3⋯jn, ou, mais formal-

mente, j = j12n−1+j22n−2+⋯+jn20. Além disso, adotaremos a notação 0, jl⋯jm para

representar a fração binária jl/2 +⋯ + jm/2m−l+1.

Partindo destas denições, podemos reescrever a transformada quântica:

∣j⟩ → 1

2n/2

2n−1∑k=0

e2πijk/2n ∣k⟩

= 1

2n/2

1

∑k1=0

⋯1

∑kn=0

e2πij(∑nl=1 kl2

−l) ∣k1⋯kn⟩

= 1

2n/2

1

∑k1=0

⋯1

∑kn=0

n

⊗l=1e2πijkl2

−l ∣kl⟩

= 1

2n/2

n

⊗l=1

(1

∑kl=0

e2πijkl2−l ∣kl⟩)

= 1

2n/2

n

⊗l=1

( ∣0⟩ + e2πij2−l ∣1⟩)

=( ∣0⟩ + e2πi0,jn ∣1⟩)( ∣0⟩ + e2πi0,jn−1jn ∣1⟩)⋯( ∣0⟩ + e2πi0,j1j2⋯jn ∣1⟩)

2n/2. (A.4)

69

Esta representação torna fácil escrever um circuito eciente para a transformada

de Fourier quântica:

Figura A.1: Circuito quântico que implementa a transformada de Fourier quântica,

omitindo portas SWAP para reversão de ordem de qubits e fatores de normalização

ao nal, adaptado de [6].

Na gura, H representa a porta de Hadamard e Rk representa a transformação

unitária

Rk =⎡⎢⎢⎢⎢⎢⎣

1 0

0 e2πi/2k

⎤⎥⎥⎥⎥⎥⎦. (A.5)

Se aplicarmos o circuito ao estado ∣j1⋯jn⟩ seremos capazes de vericar a com-

putação da transformada: aplicando a porta de Hadamard ao primeiro bit produz

1

21/2 ( ∣0⟩ + e2πi0,j1 ∣1⟩) ∣j2⋯jn⟩ , (A.6)

e a aplicação das portas Rk em sequência multiplicará o estado por uma fase e2πi/2k

em ∣1⟩ para cada k. Obteremos assim, ao nal da aplicação de todas as Rk portas,

o estado1

21/2 ( ∣0⟩ + e2πi0,j1j2⋯jn ∣1⟩) ∣j2⋯jn⟩ . (A.7)

A seguir, executaremos um procedimento similar no segundo qubit: a aplicação da

porta de Hadamard nos dará

1

22/2 ( ∣0⟩ + e2πi0,j1j2⋯jn ∣1⟩)( ∣0⟩ + e2πi0,j2 ∣1⟩) ∣j3⋯jn⟩ , (A.8)

e a aplicação das portas Rk fará o estado tornar-se

1

22/2 ( ∣0⟩ + e2πi0,j1j2⋯jn ∣1⟩)( ∣0⟩ + e2πi0,j2⋯jn ∣1⟩) ∣j3⋯jn⟩ . (A.9)

70

Continuando a aplicação das portas em cada qubit, obteremos um estado nal

1

2n/2( ∣0⟩ + e2π0,j1j2⋯jn ∣1⟩)( ∣0⟩ + e2π0,j2⋯jn ∣1⟩)⋯( ∣0⟩ + e2π0,jn ∣1⟩). (A.10)

Ao m do processo, aplicaremos portas SWAP para reverter a ordem dos qubits e

assim obter o estado desejado como saída da transformada de Fourier

1

2n/2( ∣0⟩ + e2πi0,jn ∣1⟩)( ∣0⟩ + e2πi0,jn−1jn ∣1⟩)⋯( ∣0⟩ + e2πi0,j1j2⋯jn ∣1⟩). (A.11)

Devido ao fato de que todas as portas quânticas do circuito são unitárias, pode-

mos dizer que a operação linear da transformada de Fourier quântica é unitária, e

assim, pode ser revertida, como é o caso em vários algoritmos quânticos modernos.

Levando em consideração que os melhores algoritmos clássicos para o cálculo

da transformada de Fourier discreta em 2n elementos utilizam Θ(n2n) portas [34],

o algoritmo quântico utiliza exponencialmente menos operações: começamos com

uma porta de Hadamard e n−1 rotações condicionais no primeiro qubit, em seguida

teremos mais uma porta de Hadamard e n−2 rotações para o segundo qubit, e assim

seguiremos para um total de n+ (n− 1)+⋯+ 1 = n(n+ 1)/2 portas mais no máximo

n/2 portas SWAP ao m do processo, resultando em um algoritmo Θ(n2) para a

transformada de Fourier.

Apêndice B

Teste SWAP

São muitos os casos em que precisamos comparar dois conjuntos de dados, desde

a determinação de similaridade de imagens até o teste de identidade e autenticidade

de mensagens criptografadas por chaves públicas. Isto é simples no caso clássico,

em que podemos comparar cadeias de bits e vericar se correspondem. Por outro

lado, comparar estados quânticos é mais complicado. Para testar se dois estados

quânticos são o mesmo, será necesário comparar

∣ψ⟩ = ∣ψ′⟩ . (B.1)

Isto é feito com o seguinte circuito quântico, o chamado teste SWAP :

Figura B.1: Circuito quântico que implementa o teste SWAP.

O circuito contém uma porta de Fredkin, uma porta de Hadamard e um qubit

auxiliar que aqui denominamos a. O estado inicial é então

∣φ0⟩ = ∣a⟩ ∣ψ⟩ ∣ψ′⟩ (B.2)

72

em que inicializamos o qubit auxiliar para o estado simétrico

∣a⟩ = 1√2(∣0⟩ + ∣1⟩), (B.3)

e assim, podemos reescrever ∣φ0⟩ :

∣φ0⟩ =1√2(∣0⟩ + ∣1⟩) ∣ψ⟩ ∣ψ′⟩ = 1√

2( ∣0⟩ ∣ψ⟩ ∣ψ′⟩ + ∣1⟩ ∣ψ⟩ ∣ψ′⟩). (B.4)

Após a aplicação da porta de Fredkin, descrita na seção 2.2.2.3, obteremos

∣φ1⟩ =1√2( ∣0⟩ ∣ψ⟩ ∣ψ′⟩ + ∣1⟩ ∣ψ′⟩ ∣ψ⟩), (B.5)

em que, como podemos notar, os qubits do segundo termo foram trocados de posição:

daí o nome teste SWAP (em tradução livre: teste troca). Após a aplicação da porta

de Hadamard no primeiro qubit, vamos obter

∣φ2⟩ =1

2[( ∣0⟩ + ∣1⟩) ∣ψ⟩ ∣ψ′⟩ + ( ∣0⟩ − ∣1⟩) ∣ψ′⟩ ∣ψ⟩], (B.6)

que pode ser reescrito como

∣φ2⟩ =1

2[ ∣0⟩( ∣ψ⟩ ∣ψ′⟩ + ∣ψ′⟩ ∣ψ⟩) + ∣1⟩( ∣ψ⟩ ∣ψ′⟩ − ∣ψ′⟩ ∣ψ⟩)]. (B.7)

Agora é fácil ver que se os estados ∣ψ⟩ = ∣ψ′⟩ , então ∣φ2⟩ = ∣0⟩ ∣ψ⟩ ∣ψ⟩ , que colapsará

para ∣0⟩ quando feita a medição. Caso contrário, o resultado poderá ser medido

tanto para ∣0⟩ quanto para ∣1⟩ .

Como a probabilidade de se observar ∣0⟩ é de 100% no primeiro caso ou de 50%

no segundo caso, repetindo o experimento um número de vezes (usando novas cópias

de ∣ψ⟩ e ∣ψ′⟩), seremos capazes - com quase certeza - de distinguir se ∣ψ⟩ = ∣ψ′⟩ ou

∣ψ⟩ ≠ ∣ψ′⟩ .

Apêndice C

Amplicação de Amplitude

O algoritmo de amplicação de amplitude generaliza a ideia por trás do algoritmo

de busca de Grover [35], em que se busca por uma das entradas de um banco de N

dados em tempo O(√N). O algoritmo pode ser usado para obter um aumento de

velocidade quadrático sobre os melhores algoritmos clássicos.

Para a descrição do algoritmo, suporemos um espaço de Hilbert H de N dimen-

sões representando o espaço de estados de um sistema quântico com base ortonormal

B = ∣0⟩ ,⋯, ∣N − 1⟩, uma função oráculo χ ∶ Z→ 0,1 e uma base ortonormal ope-

racional Bop = ∣ω0⟩ ,⋯, ∣ωN−1⟩ em que um operador hermitiano P ∶ H → H a

descreve de forma

P = ∑χ(k)=1

∣ωk⟩ ⟨ωk∣ . (C.1)

Poderemos utilizar P para particionar o espaço H em dois subespaços mutual-

mente ortogonais H1 e H0, que denominaremos de subespaço bom e subespaço ruim

respectivamente:

⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩

H1 ∶= Imagem(P ), de geradores ∣ωk⟩ ∈ Bop ∣ χ(k) = 1,

H0 ∶= Núcleo(P ), de geradores ∣ωk⟩ ∈ Bop ∣ χ(k) = 0.(C.2)

Dado o estado normalizado ∣ψ⟩ ∈H, com componentes em ambos os subespaços

H1 e H0, poderemos decompô-lo unicamente em

∣ψ⟩ = sen (θ) ∣ψ1⟩ + cos(θ) ∣ψ0⟩ , (C.3)

74

em que θ = arcsen (∣P ∣ψ⟩∣) ∈ [0, π/2] e ∣ψ1⟩ e ∣ψ0⟩ são as projeções de ∣ψ⟩ nos

subespaços H1 e H0 respectivamente. Esta decomposição gera um subespaço de

duas dimensões Hψ com vetores base ∣ψ0⟩ e ∣ψ1⟩ . A probabilidade de encontrar o

sistema em um estado bom quando medido é sen 2(θ).

Deniremos o operador unitário Q(ψ,P ) = −SψSP em que

⎧⎪⎪⎪⎪⎨⎪⎪⎪⎪⎩

Sψ = I − 2 ∣ψ⟩ ⟨ψ∣ e

SP = I − 2P .

(C.4)

Como podemos notar, Sψ inverte a fase do estado inicial ∣ψ⟩ e SP inverte a fase dos

estados que pertencem ao subespaço bom. A ação deste operador em Hψ é dada por

Q ∣ψ0⟩ = −Sψ ∣ψ0⟩ = (2 cos2(θ) − 1) ∣ψ0⟩ + 2 sin(θ) cos(θ) ∣ψ1⟩ , (C.5)

Q ∣ψ1⟩ = Sψ ∣ψ1⟩ = −2 sin(θ) cos(θ) ∣ψ0⟩ + (1 − 2 sin2(θ)) ∣ψ1⟩ . (C.6)

Ou seja, no subespaço Hψ, o operador Q corresponde a uma rotação de ângulo 2θ:

Q =⎡⎢⎢⎢⎢⎢⎣

cos(2θ) sen (2θ)

− sen (2θ) cos(2θ)

⎤⎥⎥⎥⎥⎥⎦. (C.7)

Aplicando Q no estado ∣ψ⟩ por n vezes consecutivas, obteremos

Qn ∣ψ⟩ = cos((2n + 1)θ) ∣ψ0⟩ + sen ((2n + 1)θ) ∣ψ1⟩ , (C.8)

que representa rotações do estado entre os subespaços bom e ruim. Após n iterações,

a probabilidade de encontrar o sistema em um estado bom é sen 2((2n + 1)θ). Esta

probabilidade será maximizada se escolhermos o número de iterações, n, como

n = ⌊ π4θ

⌋ . (C.9)

Assumindo que temos um banco de dados com N entradas, a função χ para

reconhecer os G elementos que buscaremos, e que Bop = B para maior simplicidade,

inicializaremos o sistema quântico na superposição uniforme

∣ψ⟩ = 1√N

N−1∑k=0

∣k⟩ (C.10)

75

de todos os elementos do banco de dados. Neste caso, a interseção de componentes

do estado inicial com o subespaço bom (formado pelos elementos buscados) é

∣P ∣ψ⟩∣ = sen (θ) =√

G

N. (C.11)

Se ∣P ∣ψ⟩∣ ≪ 1, poderemos aproximar o número de iterações necessárias

n = ⌊ π4θ

⌋ ≈ ⌊ π

4 sin(θ)⌋ =

⎢⎢⎢⎢⎢⎣

π

4

√N

G

⎥⎥⎥⎥⎥⎦= O(

√N). (C.12)

Como cada aplicação de SP requer uma chamada à função oráculo, seremos capazes

de encontrar as entradas buscadas com somente O(√N) chamadas, obtendo assim

uma melhora de eciência quadrática sobre os melhores algoritmos clássicos.

Apêndice D

Método de Newton

Uma das formas de encontrar aproximações para as raízes (ou zeros) de funções

reais é a utilização do método de Newton (também conhecido como método de

Newton-Raphson).

Dada uma função f diferenciável, denida sobre os números reais, e sua derivada

f ′, escolheremos um palpite x0 para uma raiz x∗ da função f em que f ′ existe e

seja não-nula. Queremos encontrar um valor x1 em função de x0 que seja uma

aproximação melhor de x∗. Deniremos a equação da reta que passa por (x0, f(x0))

e é tangente à curva em (x0, f(x0)) por

y − f(x0) = f ′(x0)(x − x0). (D.1)

Podemos aplicar o novo palpite (x1,0) para obter a equação completa:

0 − f(x0) = f ′(x0)(x1 − x0), (D.2)

e portanto teremos

x1 = x0 −f(x0)f ′(x0)

. (D.3)

De modo geral, as iterações do método de Newton serão dadas por

xn+1 = xn −f(xn)f ′(xn)

, (D.4)

e poderemos repetir o cálculo das iterações para um n tão grande quanto necessário

para atingir a precisão da aproximação buscada [36].

D.1. CONVERGÊNCIA QUADRÁTICA 77

Em geral, o método de Newton tem convergência quadrática, como veremos

abaixo.

D.1 Convergência Quadrática

Para provar a convergência quadrática do método iterativo de Newton [37], re-

escreveremos a função f , cuja raiz queremos aproximar, através da expansão de

Taylor. Supondo que x∗ é a raiz buscada, a expansão de f(x∗) sobre xn será

f(x∗) = f(xn) + f ′(xn)(x∗ − xn) +R1, (D.5)

em que o resto R1 é um termo que depende de xn e será menor à medida que xn se

aproxima de x∗:

R1 =1

2!f ′′(ψn)(x∗ − xn)2, (D.6)

em que ψn ∈ [xn, x∗]. Reescreveremos a equação acima obtendo

0 = f(x∗) = f(xn) + f ′(xn)(x∗ − xn) +1

2f ′′(ψn)(x∗ − xn)2. (D.7)

Dividindo por f ′(xn) e rearrumando, teremos

f(xn)f ′(xn)

+ (x∗ − xn) =−f ′′(ψn)2f ′(xn)

(x∗ − xn)2. (D.8)

Utilizando a denição de xn+1 na equação D.4, obteremos

x∗ − xn+1 =−f ′′(ψn)2f ′(xn)

(x∗ − xn)2, (D.9)

e se denirmos εn = x∗ − xn, podemos escrever

εn+1 =−f ′′(ψn)2f ′(xn)

ε2n. (D.10)

Tirando o valor absoluto dos dois lados da equação, seremos capazes de ver que

a taxa de convergência é quadrática quando partimos da n-ésima iteração para a

(n + 1)-ésima:

∣εn+1∣ =∣f ′′(ψn)∣2∣f ′(xn)∣

ε2n. (D.11)

D.2. FUNÇÕES COMPLEXAS 78

D.2 Funções Complexas

Quando estamos interessados em aproximar raízes de funções complexas, o mé-

todo de Newton pode ser aplicado de forma similar. Cada um dos n zeros de uma

função do n-ésimo grau terá uma bacia de atração no plano complexo, isto é, uma

região do plano cujos pontos convergem para aquela raiz quando utilizados como

palpite inicial do método. Estes conjuntos de pontos podem ser mapeados como nas

imagens abaixo.

Figura D.1: Os grácos exibem as bacias de atração das funções x2−2x e x3−3x [7].

Figura D.2: Bacias de atração de x5 − 1, em que as zonas mais escuras representam

regiões em que são necessárias mais iterações para a convergência de aproximações.

Em alguns casos, existem regiões do plano complexo que não estão contidas em

D.2. FUNÇÕES COMPLEXAS 79

nenhuma das bacias de atração, signicando que suas iterações não convergem. Por

exemplo, buscar a raiz da função x2+1 partindo de um x0 ∈ R fará com que todas as

iterações seguintes aproximem valores no eixo real, e portanto, como as duas raízes

da função são complexas, não haverá convergência.

Apêndice E

Implementação Scilab para A2×2

function v=q(n)

i f n

v = [ 0 ; 1 ] ;

else

v = [ 1 ; 0 ] ;

end

endfunction

function H = hadamard (n)

// Create n− b i t hadamard matrix .

i f n==1

H = [ 1 1 ; 1 −1]/ sqrt (2 ) ;

else

H1 = hadamard (1) ;

H=1;

for i =1:n

H=kron (H,H1) ;

end

end

endfunction

function phi=dec2vec ( dec , n )

phi=zeros (2^n , 1 ) ;

phi ( dec+1)=1; // compensate f o r s c i l a b index ing wi th +1

81

endfunction

function phi = bin2vec ( bin )

dec=bin2dec ( bin ) ;

phi=dec2vec ( dec , length ( bin ) ) ;

endfunction

function s = vec2 s t ruc t ( phi )

s=s t r u c t ( ' bin ' , ' a lpha ' )

n=log2 ( s ize ( phi , 1 ) ) ;

in=find ( phi~=0) ; //nonzero

for i =1: length ( in )

dec = in ( i ) −1;

s ( i ) . bin = dec2bin ( dec , n ) ;

s ( i ) . alpha = phi ( in ( i ) ) ;

end

endfunction

function s t r = pre t ty ( s , b_dec )

i f argn (2 ) <2,b_dec=0; end

i f ~ i s s t r u c t ( s )

s=vec2 s t ruc t ( s ) ;

end

s t r = [ ] ;

for i =1: length ( s . bin )

i f ~b_dec

s t r =[ s t r + ' ' + string ( s . alpha ( i ) ) + ' | ' + s . bin ( i ) + '>

+' ] ;

else

s t r =[ s t r + ' ' + string ( s . alpha ( i ) ) + ' | ' + string ( bin2dec

( s . bin ( i ) ) ) + '> +' ] ;

end

end

82

s t r=part ( s t r , 1 : length ( s t r ) −1)

endfunction

function m = qf t (q )

// Create QFT matrix wi th q rows and c o l s

w=exp(2*%pi*%i/q ) ;

s = zeros ( q ) ;

row=0:q−1;

for r=1:q

m( r , : )=row *( r −1) ;

end

m = w.^m;

m = m/sqrt ( q ) ;

endfunction

function [ phi , obs ]=measure ( p s i )

p = (abs ( p s i ) ) . ^ 2 ;

[ sp , ip ]=gsort (p , "g" , " i " ) ;

sp=cumsum( sp ) ;

r = rand ( ) ;

i =1;

while r>sp ( i )

i=i +1;

end

obs=ip ( i ) ;

phi=zeros ( s ize ( p s i ) ) ;

phi ( obs )=1;

endfunction

83

function [ I ] = hamSim(A, denomin )

t0 = 2 * %pi

I = expm(%i * A * t0 / denomin )

endfunction

function [R] = Ry( theta )

R = [ cos ( theta /2) , sin ( theta /2) ;− sin ( theta /2) , cos ( theta /2) ]

endfunction

function S = SWAP()

S = [ 1 , 0 , 0 , 0 ; 0 , 0 , 1 , 0 ; 0 , 1 , 0 , 0 ; 0 , 0 , 0 , 1 ]

endfunction

function C = con t r o l l e d (U)

[ dim , i ] = s ize (U)

C = eye (2*dim , 2*dim)

i n i t i a l = dim +1

f i n a l = 2*dim

grp = i n i t i a l : f i n a l

C( grp , grp ) = U

endfunction

function HHL(A, b)

// A = [ 3 , 1 ; 1 , 3 ]

// b = [ 1 , 0 ] '

// x = [3/8 , −1/8]

m = 2 // cons tant t ha t can be determined based on the de s i r ed

accuracy o f the ga te R

quantumB = b (1 , 1 ) *q (0 ) + b (2 , 1 ) * q (1 )

psi_0 = bin2vec ( ' 0000 ' ) . * . quantumB

disp ( '======= HADAMARD =======' )

psi_1 = (eye ( 2 , 2 ) . * . hadamard (3 ) . * . eye ( 2 , 2 ) ) * psi_0

disp ( ' psi_1 = ' + pre t ty ( psi_1 ) )

84

disp ( '======= HAM−SIM =======' )

hamSim1 = eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . c o n t r o l l e d (hamSim(

A, 8 ) )

psi_2 = hamSim1 * psi_1

cHamSim2 = eye ( 2 , 2 ) . * . c o n t r o l l e d (hamSim(A, 4 ) )

hamSim2 = eye ( 2 , 2 ) . * . cHamSim2 . * . eye ( 2 , 2 )


cHamSim3 = con t r o l l e d (eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . hamSim(A, 2 ) )

hamSim3 = eye ( 2 , 2 ) . * . cHamSim3



disp ( '======= INV−QFT =======' )

QFT = eye ( 2 , 2 ) . * . q f t (2^3) ' . * . eye ( 2 , 2 )

psi_3 = QFT * psi_2


disp ( '======= SWAP =======' )

S = SWAP()

S = eye ( 2 , 2 ) . * . S . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 )

psi_4 = S * psi_3


disp ( '======= C−ROT =======' )

psi_5 = psi_4

rot1 = eye ( 4 , 4 )

opR1 = Ry(4*%pi / 2^(m−1) )

r0 = opR1 * q (0 )

r1 = opR1 * q (1 )

rot1 (2 , 2 ) = r0 (1 )

rot1 (4 , 2 ) = r0 (2 )

rot1 (2 , 4 ) = r1 (1 )

rot1 (4 , 4 ) = r1 (2 )

psi_5 = ( rot1 . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 ) ) * psi_5

85

rot2 = eye ( 8 , 8 )

opR2 = Ry(2*%pi / 2^(m−1) )

r0 = opR2 * q (0 )

r1 = opR2 * q (1 )

rot2 (2 , 2 ) = r0 (1 )

rot2 (6 , 2 ) = r0 (2 )

rot2 (4 , 4 ) = r0 (1 )

rot2 (8 , 4 ) = r0 (2 )

rot2 (2 , 6 ) = r1 (1 )

rot2 (6 , 6 ) = r1 (2 )

rot2 (4 , 8 ) = r1 (1 )

rot2 (8 , 8 ) = r1 (2 )

psi_5 = ( rot2 . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 ) ) * psi_5

rot3 = eye (16 ,16)

opR3 = Ry(%pi / 2^(m−1) )

r0 = opR3 * q (0 )

r1 = opR3 * q (1 )

rot3 (2 , 2 ) = r0 (1 )

rot3 (10 ,2 ) = r0 (2 )

rot3 (4 , 4 ) = r0 (1 )

rot3 (12 ,4 ) = r0 (2 )

rot3 (6 , 6 ) = r0 (1 )

rot3 (14 ,6 ) = r0 (2 )

rot3 (8 , 8 ) = r0 (1 )

rot3 (16 ,8 ) = r0 (2 )

rot3 (2 ,10 ) = r1 (1 )

rot3 (10 ,10) = r1 (2 )

rot3 (4 ,12 ) = r1 (1 )

rot3 (12 ,12) = r1 (2 )

rot3 (6 ,14 ) = r1 (1 )

rot3 (14 ,14) = r1 (2 )

rot3 (8 ,16 ) = r1 (1 )

rot3 (16 ,16) = r1 (2 )

psi_5 = ( rot3 . * . eye ( 2 , 2 ) ) * psi_5


86

disp ( '======= SWAP =======' )

S = SWAP()

S = eye ( 2 , 2 ) . * . S . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 )

psi_6 = S * psi_5


disp ( '======= QFT =======' )

QFT = eye ( 2 , 2 ) . * . q f t (2^3) . * . eye ( 2 , 2 )

psi_7 = QFT * psi_6


disp ( '======= INV−HAM−SIM =======' )

psi_8 = psi_7

inVCHamSim3 = con t r o l l e d (eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . hamSim(A, −2) )

invHamSim3 = eye ( 2 , 2 ) . * . inVCHamSim3

psi_8 = invHamSim3 * psi_8

inVCHamSim2 = eye ( 2 , 2 ) . * . c o n t r o l l e d (hamSim(A, −4) )

invHamSim2 = eye ( 2 , 2 ) . * . inVCHamSim2 . * . eye ( 2 , 2 )


invHamSim1 = eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . eye ( 2 , 2 ) . * . c o n t r o l l e d (

hamSim(A, −8) )



disp ( '======= HADAMARD =======' )

hads = eye ( 2 , 2 ) . * . hadamard (3 ) . * . eye ( 2 , 2 )

psi_9 = hads * psi_8


disp ( '======= CLEAN STATE =======' )

disp ( ' psi_9 = ' + pre t ty ( clean ( psi_9 ) ) )

disp ( '======= MEASURE =======' )

psi_10 = measure ( psi_9 )

87

// d i sp ( ' psi_10 = ' + p r e t t y ( psi_10 ) )

disp ( psi_10 )

s t r 10 = vec2 s t ruc t ( psi_10 )

printf ( " = |%s>" , s t r 10 . bin )

endfunction

Apêndice F

Resultado da execução Scilab para

A2×2

======= HADAMARD =======

psi_1 = 0.3535534|00000 > + 0.3535534|00010 > + 0.3535534|00100 > +

0.3535534|00110 > + 0.3535534|01000 > + 0.3535534|01010 > +

0.3535534|01100 > + 0.3535534|01110 >

======= HAM−SIM =======

psi_2 = 0.3535534|00000 > + −0.1767767+% i *0.1767767|00010 > +

−0.1767767−% i *0.1767767|00011 > + −0.1767767+% i *0.1767767|00100 > +

−0.1767767−% i *0.1767767|00101 > + 0.3535534−% i *5 .412D−17|00110> +

−1.082D−17+%i *1 .082D−17|00111> + 0.3535534−% i *1 .299D−16|01000> +

−%i *4 .330D−17|01001> + −0.1767767+% i *0.1767767|01010 > +

−0.1767767−% i *0.1767767|01011 > + −0.1767767+% i *0.1767767|01100 > +

−0.1767767−% i *0.1767767|01101 > + 0.3535534−% i *1 .840D−16|01110> +

−1.082D−17−%i *3 .247D−17|01111>

======= INV−QFT =======

psi_3 = 0.25+% i *0.25|00000 > + −0.25−% i *0.25|00001 > + −4.420D−17−%i

*1 .388D−17|00010> + −5.759D−18−%i *2 .706D−18|00011> + 0.5+% i

*0.25|00100 > + −3.362D−17+%i *0.25|00101 > + −1.205D−16−%i *9 .714D

89

−17|00110> + 3.587D−17−%i *1 .658D−17|00111> + −8.327D−17−%i *2 .264D

−16|01000> + 1.077D−17−%i *5 .097D−17|01001> + 2.339D−17−%i *3 .469D

−16|01010> + 7.515D−17+%i *2 .706D−18|01011> + 0.25−% i *0.5|01100 >

+ 0.25+% i *3 .508D−16|01101> + 9.971D−17+%i *2 .220D−16|01110> +

−2.857D−16−%i *1 .083D−16|01111>

======= SWAP =======

psi_4 = 0.25+% i *0.25|00000 > + −0.25−% i *0.25|00001 > + −4.420D−17−%i

*1 .388D−17|00010> + −5.759D−18−%i *2 .706D−18|00011> + −8.327D−17−%i

*2 .264D−16|00100> + 1.077D−17−%i *5 .097D−17|00101> + 2.339D−17−%i

*3 .469D−16|00110> + 7.515D−17+%i *2 .706D−18|00111> + 0.5+% i

*0.25|01000 > + −3.362D−17+%i *0.25|01001 > + −1.205D−16−%i *9 .714D

−17|01010> + 3.587D−17−%i *1 .658D−17|01011> + 0.25−% i *0.5|01100 >

+ 0.25+% i *3 .508D−16|01101> + 9.971D−17+%i *2 .220D−16|01110> +

−2.857D−16−%i *1 .083D−16|01111>

======= C−ROT =======

psi_5 = 0.25+% i *0.25|00000 > + −0.25−% i *0.25|00001 > + −3.126D−17−%i

*9 .813D−18|00010> + −4.073D−18−%i *1 .914D−18|00011> + −5.099D−33−%i

*1 .386D−32|00100> + 6.592D−34−%i *3 .121D−33|00101> + −1.654D−17+%i

*2 .453D−16|00110> + −5.314D−17−%i *1 .914D−18|00111> + −0.5−% i

*0.25|01000 > + 3.362D−17−%i *0.25|01001 > + 8.523D−17+%i *6 .869D

−17|01010> + −2.537D−17+%i *1 .173D−17|01011> + −4.592D−17+%i *9 .185D

−17|01100> + −4.592D−17−%i *6 .444D−32|01101> + 7.051D−17+%i *1 .570D

−16|01110> + −2.020D−16−%i *7 .659D−17|01111> + 3.126D−17+%i *9 .813D

−18|10010> + 4.073D−18+%i *1 .914D−18|10011> + 8.327D−17+%i *2 .264D

−16|10100> + −1.077D−17+%i *5 .097D−17|10101> + −1.654D−17+%i *2 .453D

−16|10110> + −5.314D−17−%i *1 .914D−18|10111> + −6.123D−17−%i *3 .062D

−17|11000> + 4.117D−33−%i *3 .062D−17|11001> + −8.523D−17−%i *6 .869D

−17|11010> + 2.537D−17−%i *1 .173D−17|11011> + 0.25−% i *0.5|11100 > +

0.25+% i *3 .508D−16|11101> + 7.051D−17+%i *1 .570D−16|11110> +

−2.020D−16−%i *7 .659D−17|11111>

======= SWAP =======

psi_6 = 0.25+% i *0.25|00000 > + −0.25−% i *0.25|00001 > + −3.126D−17−%i

90

*9 .813D−18|00010> + −4.073D−18−%i *1 . 914D−18|00011> + −0.5−% i

*0.25|00100 > + 3.362D−17−%i *0.25|00101 > + 8.523D−17+%i *6 .869D

−17|00110> + −2.537D−17+%i *1 .173D−17|00111> + −5.099D−33−%i *1 .386D

−32|01000> + 6.592D−34−%i *3 .121D−33|01001> + −1.654D−17+%i *2 .453D

−16|01010> + −5.314D−17−%i *1 .914D−18|01011> + −4.592D−17+%i *9 .185D

−17|01100> + −4.592D−17−%i *6 .444D−32|01101> + 7.051D−17+%i *1 .570D

−16|01110> + −2.020D−16−%i *7 .659D−17|01111> + 3.126D−17+%i *9 .813D

−18|10010> + 4.073D−18+%i *1 .914D−18|10011> + −6.123D−17−%i *3 .062D

−17|10100> + 4.117D−33−%i *3 .062D−17|10101> + −8.523D−17−%i *6 .869D

−17|10110> + 2.537D−17−%i *1 .173D−17|10111> + 8.327D−17+%i *2 .264D

−16|11000> + −1.077D−17+%i *5 .097D−17|11001> + −1.654D−17+%i *2 .453D

−16|11010> + −5.314D−17−%i *1 .914D−18|11011> + 0.25−% i *0.5|11100 >

+ 0.25+% i *3 .508D−16|11101> + 7.051D−17+%i *1 .570D−16|11110> +

−2.020D−16−%i *7 .659D−17|11111>

======= QFT =======

psi_7 = −0.0883883+% i *1 .851D−16|00000> + −0.0883883−% i

*0.1767767|00001 > + 0.1767767−% i *0.0883883|00010 > + −7.807D−17−%i

*0.0883883|00011 > + 0.2651650+% i *0.1767767|00100 > + −0.0883883+% i

*8 .792D−17|00101> + 1.342D−16+%i *0.2651650|00110 > + −0.1767767−% i

*0.0883883|00111 > + −0.0883883−% i *3 .018D−17|01000> + −0.0883883−% i

*0.1767767|01001 > + 0.1767767−% i *0.0883883|01010 > + 5.031D−17−%i

*0.0883883|01011 > + 0.2651650+% i *0.1767767|01100 > + −0.0883883−% i

*3 .240D−17|01101> + 2.289D−17+%i *0.2651650|01110 > + −0.1767767−% i

*0.0883883|01111 > + 0.0883883−% i *0.1767767|10000 > + 0.0883883+% i

*9 .999D−17|10001> + −0.1767767−% i *0.0883883|10010 > + 3.968D−17−%i

*0.0883883|10011 > + −0.0883883+% i *0.1767767|10100 > + −0.0883883+% i

*3 .334D−17|10101> + 0.1767767+% i *0.0883883|10110 > + 1.700D−17+%i

*0.0883883|10111 > + 0.0883883−% i *0.1767767|11000 > + 0.0883883+% i

*5 .216D−19|11001> + −0.1767767−% i *0.0883883|11010 > + −1.262D−17−%i

*0.0883883|11011 > + −0.0883883+% i *0.1767767|11100 > + −0.0883883+% i

*1 .149D−16|11101> + 0.1767767+% i *0.0883883|11110 > + 1.380D−16+%i

*0.0883883|11111 >

======= INV−HAM−SIM =======

psi_8 = −0.0883883+% i *1 .851D−16|00000> + −0.0883883−% i

91

*0.1767767|00001 > + −0.0883883−% i *1 .501D−16|00010> + −0.0883883+% i

*0.1767767|00011 > + 5.504D−17+%i *0.2651650|00100 > + −0.1767767−% i

*0.0883883|00101 > + 8.466D−17−%i *0.2651650|00110 > + −0.1767767+% i

*0.0883883|00111 > + −0.0883883−% i *7 .348D−17|01000> + −0.0883883−% i

*0.1767767|01001 > + −0.0883883+% i *3 .293D−17|01010> + −0.0883883+% i

*0.1767767|01011 > + −2.999D−16+%i *0.2651650|01100 > + −0.1767767−% i

*0.0883883|01101 > + 2.372D−16−%i *0.2651650|01110 > + −0.1767767+% i

*0.0883883|01111 > + 0.0883883−% i *0.1767767|10000 > + 0.0883883+% i

*9 .999D−17|10001> + 0.0883883+% i *0.1767767|10010 > + 0.0883883+% i

*2 .022D−16|10011> + 0.1767767+% i *0.0883883|10100 > + −1.887D−17+%i

*0.0883883|10101 > + 0.1767767−% i *0.0883883|10110 > + 6.813D−17−%i

*0.0883883|10111 > + 0.0883883−% i *0.1767767|11000 > + 0.0883883+% i

*4 .382D−17|11001> + 0.0883883+% i *0.1767767|11010 > + 0.0883883−% i

*9 .860D−17|11011> + 0.1767767+% i *0.0883883|11100 > + 5.883D−17+%i

*0.0883883|11101 > + 0.1767767−% i *0.0883883|11110 > + −1.764D−16−%i

*0.0883883|11111 >

======= HADAMARD =======

psi_9 = −0.125+% i *2 .776D−17|00000> + −0.375−% i *1 .353D−16|00001> +

−2.593D−16+%i *0.375|00010 > + 2.984D−16−%i *0.375|00011 > + −0.125−%

i *2 .776D−17|00100> + 0.125+% i *7 .980D−17|00101> + 1.448D−16−%i

*0.375|00110 > + −8.327D−17−%i *0.125|00111 > + 9.848D−17−%i *2 .776D

−17|01000> + 5.551D−17+%i *1 .214D−16|01001> + 3.009D−16+%i *9 .714D

−17|01010> + −3.400D−16+%i *4 .510D−17|01011> + −4.297D−17+%i *8 .327D

−17|01100> + −1.110D−16−%i *6 .592D−17|01101> + −5.111D−17+%i *2 .082D

−16|01110> + −%i *9 .368D−17|01111> + 0.375+% i *1 .665D−16|10000> +

0.125−% i *3 .469D−17|10001> + 2.359D−16−%i *0.125|10010 > + −9.723D

−17+%i *0.125|10011 > + −0.125+% i *2 .255D−16|10100> + 0.125+% i *2 .082

D−16|10101> + 2.012D−16−%i *0.375|10110 > + −2.011D−16−%i

*0.125|10111 > + −4.163D−17+%i *1 .978D−16|11000> + 6.886D−18+%i

*2 .047D−16|11001> + 1.318D−16+%i *1 .665D−16|11010> + −1.387D

−16|11011> + −1.249D−16−%i *3 .123D−17|11100> + −1.110D−16+%i *4 .857D

−17|11101> + 2.637D−16+%i *2 .047D−16|11110> + 9.012D−17−%i *1 .665D

−16|11111>

======= CLEAN STATE =======

92

psi_9 = −0.125|00000> + −0.375|00001> + %i *0.375|00010 > + −%i

*0.375|00011 > + −0.125|00100> + 0.125|00101 > + −%i *0.375|00110 > +

−%i *0.125|00111 > + 0.375|10000 > + 0.125|10001 > + −%i

*0.125|10010 > + %i *0.125|10011 > + −0.125|10100> + 0.125|10101 > +

−%i *0.375|10110 > + −%i *0.125|10111 >

======= MEASURE =======

0 . 0 . 0 . 0 . 0 . 0 . 1 . = |110>

Documents

Algoritmo quântico para equações linearescollier/CursosGrad/QC/Julio_Zynger_Algoritmo... · C Ampli cação de Amplitude 73 D Método de Newton 76 ... O uso de tais estruturas