Computação Quântica: Matemática e Teoria para Iniciantes

1. Introdução à Computação Quântica e Estrutura do Curso [0]

1. Computação Quântica usa princípios da mecânica quântica para processar informações rapidamente [0].
2. O curso oferece base sólida, indo do básico aos algoritmos quânticos populares [1].
3. O curso tem duas seções principais: matemática essencial e mecânica quântica [2].
4. O criador do curso é Michael, da Quantum Source [4].
5. Explicações comuns usam analogias, como Qubits serem zero e um ao mesmo tempo [5].
6. O curso foca em ensinar como computadores quânticos realmente funcionam, sem analogias [7].

1.1. Estrutura do Curso [8]

1. Primeira Seção: Matemática básica necessária para o curso [9].
   1. Inclui introdução a números complexos e álgebra linear básica [9].
2. Próxima Seção: Explora o que é um qubit e sua representação matemática [10].
   1. Discute operações de qubit único e suas propriedades [11].
3. Terceira Seção: Representação matemática de múltiplos qubits e suas operações [12].
   1. Explora fenômenos quânticos como emaranhamento e phase kickback [13].
4. Seção Final: Analisa algoritmos quânticos usando o conhecimento prévio [14].
   1. Mostra por que computadores quânticos são tecnologia revolucionária [15].

2. Matemática Essencial: Números Complexos [16]

2.1. Introdução a Números Imaginários [16]

1. Começa-se com raízes quadradas, como $x^2=4$, resultando em $\pm 2$ [17].
2. Para $x^2=-4$, surgem os números imaginários [18].
3. Se $i=\sqrt{-1}$, então $\sqrt{-4}$ é $\pm 2i$ [19].
4. Um número imaginário contém um fator de $\sqrt{-1}$ [20].

2.2. Números Complexos e Operações Básicas [21]

1. Um número complexo é um número real mais um número imaginário [22].
2. A forma padrão é $a+iB$, onde $A$ é a parte real e $B$ a imaginária [23].
3. Números complexos podem ser representados em outra forma para estados quânticos [24].
4. Adição e subtração somam/subtraem partes reais e imaginárias separadamente [25].
5. Multiplicação exige lembrar que $i^2$ se torna $-1$ [27].
6. O conjugado complexo é obtido invertendo o sinal da parte imaginária [28].
7. Multiplicar um complexo pelo seu conjugado sempre resulta em um número real [31].

2.3. Representação Gráfica e Forma Polar [33]

1. Um número complexo pode ser visto como um vetor no plano [33].
   1. O eixo horizontal é o eixo Real; o vertical é o imaginário [33].
   2. Exemplo: $-2+3i$ é um vetor terminando em $(-2,3)$ [34].
2. A magnitude é a distância do vetor até a origem [35].
   1. Calculada pela fórmula de Pitágoras: $|A+iB|=\sqrt{a^2+b^2}$ [36].
3. Outra representação usa magnitude ($r$) e ângulo ($\theta$) com o eixo $x$ positivo [39].
   1. Isso é chamado de forma polar: $r(\cos \theta +i\sin \theta )$ [40].
   2. $\theta$ é encontrado por $\arctan (b/a)$ [41].
4. Existe também a forma exponencial: $r{e}^{i\theta }$ [43].
5. Em computação quântica, usa-se quase exclusivamente a forma exponencial [45].
   1. Mudar $\theta$ faz rotacionar em um círculo unitário; ângulos se somam na multiplicação [46].

3. Matemática Essencial: Álgebra Linear (Matrizes) [48]

3.1. Definição e Operações Básicas de Matrizes [48]

1. Uma matriz é um arranjo bidimensional de números [48].
2. Uma matriz $M\times N$ tem $M$ linhas e $N$ colunas [50].
   1. Exemplo: uma matriz com 2 linhas e 3 colunas é $2\times 3$ [50].
3. Adição e subtração exigem que as matrizes tenham as mesmas dimensões [52].
4. Multiplicação por um escalar multiplica cada elemento da matriz [56].
5. A multiplicação de matrizes envolve um produto escalar (dot product) [58].
   1. O elemento $(i,j)$ da matriz resultante é o produto escalar da linha $i$ da primeira matriz pela coluna $j$ da segunda [59].
6. A multiplicação só é possível se colunas da primeira matriz igualam linhas da segunda [62].

3.2. Vetores Coluna e Transformações Matriciais [64]

1. Uma matriz $N\times 1$ é chamada de vetor coluna [64].
2. Vetores coluna representam estados na computação quântica [66].
3. Multiplicar uma matriz por um vetor coluna resulta em outro vetor coluna [68].
4. Intuitivamente, a matriz transforma o vetor coluna [69].
   1. Matrizes são usadas para aplicar operações em estados quânticos [71].

3.3. Propriedades Especiais de Matrizes [72]

1. A matriz identidade tem zeros, exceto a diagonal principal com uns [73].
   1. Multiplicar qualquer matriz pela identidade retorna a matriz original [74].
2. A matriz inversa ($A^{-1}$) retorna a identidade quando multiplicada pela matriz original ($A$) [76].
   1. Aplicar $A$ e depois $A^{-1}$ é como aplicar a matriz identidade [79].
3. O conjugado complexo de uma matriz inverte o sinal dos elementos imaginários [80].
4. A transposta ($T$) troca linhas por colunas [84].
5. A combinação de conjugado complexo e transposta é chamada de dagger (${}^{†}$) [86].
6. Matrizes Unitárias ($U$): $U{U}^{†}=I$ (a dagger é a inversa) [88].
   1. Geometricamente, matrizes unitárias rotacionam ou flipam o vetor, mantendo seu comprimento [90].
7. Matrizes Hermitianas ($H$): $H=H^{†}$ [92].

3.4. Autovetores e Autovalores [95]

1. Se a transformação estica/comprime o vetor sem mudar sua direção, ele é um autovetor [95].
2. O fator de estiramento/compressão é chamado de autovalor ($\lambda$) [96].
3. Exemplo: Matriz $\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right)$ aplicada a $\left(\begin{array}{c}0\\ 3\end{array}\right)$ resulta em $\left(\begin{array}{c}0\\ 6\end{array}\right)$ [98].
   1. Isso é $2\times \left(\begin{array}{c}0\\ 3\end{array}\right)$, então $\lambda =2$ e autovetor é $\left(\begin{array}{c}0\\ 3\end{array}\right)$ [99].

4. Qubits, Superposição e Medição [101]

4.1. Representação Matemática de Qubits [101]

1. Computadores clássicos usam bits (0 ou 1); quânticos usam Qubits [101].
2. Um qubit pode ser qualquer partícula quântica em dois estados distintos [106].
   1. Exemplo: polarização horizontal ou vertical de um fóton [106].
3. Os estados 0 e 1 são definidos como vetores coluna: $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ e $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$ [107].
   1. Os colchetes angulares são a Notação Dirac (Ket) [108].
4. Superposição significa que a partícula está em dois estados simultaneamente [109].
   1. Um qubit em superposição está em estado 0 e 1 ao mesmo tempo [111].
5. Matematicamente, um qubit é um vetor coluna com dois elementos: $\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$ [113].
   1. $\alpha$ é a amplitude do estado 0; $\beta$ é a amplitude do estado 1 [114].
6. Se $\alpha$ e $\beta$ são não-nulos, o qubit está em superposição de 0 e 1 [118].

4.2. Medição e Probabilidade [119]

1. Ao medir um sistema quântico, seu estado muda para o estado medido [120].
2. Se medido, um qubit colapsa para 0 ou 1, não para a superposição [121].
3. Após a medição, o estado colapsa permanentemente para o resultado medido [123].
4. As amplitudes ($\alpha ,\beta$) determinam a probabilidade de medição [128].
   1. Probabilidade de medir 0 é $|\alpha {|}^2$; Probabilidade de medir 1 é $|\beta {|}^2$ [129].
5. A soma das probabilidades deve ser 1: $|\alpha {|}^2+|\beta {|}^2=1$ [132].

4.3. Notação Dirac e Esfera de Bloch [136]

1. A notação Dirac (Kets, como $|0⟩$) é o modo convencional de escrever estados quânticos [136].
   1. É preferível a matrizes, pois estas se tornam grandes com mais qubits [144].
2. Um qubit pode ser representado graficamente na Esfera de Bloch [145].
   1. Polo Norte é o estado $|0⟩$; Polo Sul é o estado $|1⟩$ [146].
3. Quanto mais perto do topo, maior a probabilidade de medir 0 [149].
4. O estado $\frac{1}{\sqrt{2}}|0⟩+\frac{1}{\sqrt{2}}|1⟩$ fica no meio (equador) [150].
5. A rotação do qubit na esfera é chamada de fase [152].

5. Portas Quânticas de Qubit Único e Fase [156]

5.1. Portas X, Y e Z (Rotações) [157]

1. Computadores quânticos usam portas para mudar estados de qubits [158].
2. Portas comuns de qubit único são X, Y e Z [159].
3. A Porta X (NOT) inverte o estado: $|0⟩\leftrightarrow |1⟩$ [161].
   1. Ela rotaciona o qubit $180^{\circ }$ ($\pi$ radianos) no eixo X [165].
4. A Porta Y rotaciona o estado $180^{\circ }$ no eixo Y [168].
5. A Porta Z rotaciona o estado $180^{\circ }$ no eixo Z [169].
6. Aplicar a mesma porta duas vezes retorna à posição original; elas são suas próprias inversas [170].
7. Essas portas são representadas por matrizes [172].
8. Aplicar uma porta é multiplicar sua matriz pelo vetor coluna do qubit [175].
9. Para aplicar a porta em notação Dirac, usa-se as colunas da matriz da porta [177].
   1. A primeira coluna mostra onde $|0⟩$ se transforma; a segunda, onde $|1⟩$ se transforma [178].
10. Operações quânticas são lineares, agindo em cada estado de superposição individualmente [180].

5.2. Introdução à Fase (Rotação no Eixo Z) [186]

1. A Fase é a rotação em torno do eixo Z na Esfera de Bloch [187].
2. A fase não afeta a probabilidade de medir 0 ou 1 [189].
3. A fase é representada matematicamente usando números complexos em forma exponencial [191].
4. A Porta Z multiplica o estado $|1⟩$ por $-1$ (fase de $\pi$ radianos) [196].
   1. O número complexo $-1$ é $e^{i\pi }$ [198].
5. O fator $e^{i\varphi }$ rotaciona o qubit em $\varphi$ radianos no eixo Z [203].
6. Existem dois tipos de fase [204]:
   1. Fase Global: Multiplica o qubit inteiro; é fisicamente irrelevante [205].
   2. Fase Relativa: Multiplica apenas a amplitude do estado $|1⟩$; é crucial [207].
7. Se ambas as amplitudes têm fatores complexos, a fase global é descartada [209].

5.3. Estados da Esfera de Bloch e Portas Hadamard, S, T [215]

1. Os estados no equador (Plus, Minus, i, -i) são atalhos para estados com fase relativa específica [216].
   1. $|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$ [220].
   2. $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ (fase relativa de $-1$) [221].
   3. $|i⟩$ tem fase relativa $i$ ($e^{i\pi /2}$) [223].
2. A Porta Hadamard (H) transforma $|0⟩\to |+⟩$ e $|1⟩\to |-⟩$ [226].
   1. $H$ é sua própria inversa [228].
   2. A porta Hadamard demonstra que a fase relativa importa após a aplicação da porta [230].
3. A Porta S adiciona uma fase relativa de $\pi /2$ radianos [236].
4. A Porta T adiciona uma fase relativa de $\pi /4$ radianos [237].
5. A conjugada transposta de uma porta é seu inverso (ex: $S^{†}$ é o inverso de $S$) [238].

6. Múltiplos Qubits, Emaranhamento e Circuitos [242]

6.1. Múltiplos Qubits e Produto Tensorial [242]

1. Múltiplos qubits são representados pelo produto tensorial ($\otimes$) [242].
   1. Dois qubits no estado $|0⟩$ são representados por $|0⟩\otimes |0⟩$, ou $|00⟩$ [243].
2. Superposição de múltiplos qubits expande as combinações possíveis (ex: 4 estados para 2 qubits) [245].
3. A medição segue a mesma regra: probabilidade é a magnitude ao quadrado do coeficiente [248].
4. Adicionar um qubit ao sistema é fazer o produto tensorial com o novo estado [250].

6.2. Circuitos Quânticos [253]

1. Circuitos quânticos diagramam a aplicação de portas em qubits [253].
   1. Linhas verticais representam qubits individuais [255].
   2. Caixas são portas quânticas (ex: X, H); círculos são medições [257].
   3. A aplicação das portas ocorre da esquerda para a direita (ordem temporal) [260].
2. Exemplo de circuito: Estado inicial $|001⟩$ é transformado sequencialmente [264].

6.3. Portas de Múltiplos Qubits [270]

1. A porta mais comum de múltiplos qubits é a CNOT (Controlled-X) [270].
   1. Atua em dois qubits: um controle e um alvo [273].
   2. Aplica a porta X no alvo se o controle for $|1⟩$; faz nada se o controle for $|0⟩$ [274].
2. A Porta Toffoli (Controlled-Controlled-X) tem dois qubits de controle [278].
3. É possível criar versões controladas de outras portas (Y, Z, S, T, H) [282].
   1. A porta controlada aplica a porta se o controle for 1 [283].

6.4. Medição em Múltiplos Qubits e Colapso [285]

1. Para medir um qubit específico, soma-se as probabilidades de todos os estados onde ele tem o valor desejado [285].
2. Quando um qubit é medido, o estado colapsa, removendo estados inconsistentes [288].
3. A probabilidade total do novo estado deve somar 1; usa-se um constante de normalização ($A$) para corrigir [291].

6.5. Emaranhamento (Entanglement) [299]

1. O circuito de exemplo com CNOT em $|+⟩|0⟩$ leva ao estado emaranhado [299].
2. Emaranhamento ocorre quando o estado não pode ser fatorado em produtos tensoriais de estados individuais [306].
   1. Qubits emaranhados dependem um do outro para determinar seu estado [310].
3. Tipos de emaranhamento [311]:
   1. Maximalmente emaranhados (Bell States): Medir um define o estado dos outros [312].
   2. Parcialmente emaranhados: Medir um afeta as probabilidades ou a fase dos outros [316].

6.6. Phase Kickback (Recuo de Fase) [319]

1. Phase Kickback ocorre quando um estado é um autovetor da porta controlada aplicada [320].
2. Se $|V⟩$ é autovetor de $U$ com autovalor $e^{i\theta }$, a porta controlada aplica $e^{i\theta }$ ao qubit de controle [323].
3. O qubit alvo ($V$) permanece inalterado, mas uma fase relativa é aplicada ao qubit de controle [328].
4. Este fenômeno é usado em alguns algoritmos quânticos [330].

6.7. Superdense Coding (Codificação Superdensa) [331]

1. Protocolo que envia dois bits clássicos usando apenas um qubit [331].
2. Requer que Alice e Bob compartilhem dois qubits maximamente emaranhados inicialmente [335].
3. Alice aplica uma operação em seu qubit dependendo dos dois bits que quer enviar [339]:
   1. 00: Nenhuma operação [340].
   2. 01: Aplica porta X [341].
   3. 10: Aplica porta Z [342].
   4. 11: Aplica portas X e Z [343].
4. Alice envia seu qubit para Bob [340].
5. Bob aplica CNOT (controle no qubit de Alice, alvo no seu) [346].
6. Bob aplica Hadamard no qubit de Alice [347].
7. Medindo ambos os qubits, Bob obtém os dois bits originais de Alice [349].

7. Reversibilidade e Funções Quânticas [352]

7.1. Operações Clássicas e Reversibilidade [352]

1. Operações clássicas principais: AND, OR, NOT, XOR (exclusive OR) [353].
2. NOT atua em um bit; AND e OR atuam em dois bits [355].
3. XOR retorna 1 se um dos inputs for 1, e 0 se forem iguais [363].
4. Uma função $f$ é Reversível se, dado $f(x)$, podemos determinar $x$ [367].
   1. A operação OR não é reversível (saída 1 pode vir de 3 inputs) [370].
5. Para tornar uma porta clássica reversível, adiciona-se um bit de entrada $C$ [372].
   1. O output se torna $X$ e $C\oplus f(X)$ [373].
6. Todas as operações quânticas, exceto medição, devem ser reversíveis (unitárias) [378].

7.2. Funções Quânticas e Oráculos de Fase [382]

1. Funções quânticas devem ser reversíveis, usando a técnica de tornar portas clássicas reversíveis [383].
2. A função reversível quântica mapeia $|X⟩|Y⟩\to |X⟩|Y\oplus f(X)⟩$ [385].
3. Se definirmos $Y=|0⟩$, a função se torna $|X⟩|0⟩\to |X⟩|f(X)⟩$ [387].
4. Funções são codificadas em uma Matriz Unitária ($U_f$) [390].
5. Aplicar $U_f$ ao estado $|X⟩|0⟩$ resulta em $|X⟩|f(X)⟩$ [391].
6. Aplicar $U_f$ ao estado $|X⟩|-⟩$ resulta no Oráculo de Fase [393]:
   1. $|X⟩|-⟩\to (-1{)}^{f(X)}|X⟩|-⟩$ [397].
7. Se $f(X)=0$, o estado é $|X⟩|-⟩$; se $f(X)=1$, é $-|X⟩|-⟩$ [399].
8. Combinando os casos, o resultado é $(-1{)}^{f(X)}|X⟩|-⟩$ [405].
9. O Oráculo de Fase é usado no Algoritmo de Deutsch [407].

7.3. Teorema da Não-Clonagem [408]

1. Em computadores clássicos, copiar bits é fácil [409].
2. Em computação quântica, não se pode copiar um qubit em estado desconhecido ($\alpha |0⟩+\beta |1⟩$) [409].
   1. Medir o estado revela apenas 0 ou 1, perdendo as amplitudes $\alpha$ e $\beta$ [410].

8. Algoritmos Quânticos Fundamentais [413]

8.1. Algoritmo de Deutsch (1 Qubit) [413]

1. Problema: Determinar se uma função $F:\{0,1\}\to \{0,1\}$ é Constante ou Balanceada [417].
   1. Constante: $F(0)=F(1)$ (ex: sempre 0 ou sempre 1) [418].
   2. Balanceada: Retorna 0 para metade das entradas e 1 para a outra metade [420].
2. Computador clássico precisa de 2 consultas ($F(0)$ e $F(1)$) [425].
3. O algoritmo quântico resolve em uma única consulta [427].
4. Circuito: Começa em $|00⟩$ [430].
   1. Aplica-se Hadamard em ambos os qubits, resultando em $|+⟩|-⟩$ [432].
   2. Aplica-se o Oráculo de Fase $U_f$ no estado [434].
   3. Se $F(0)=F(1)$ (Constante), o estado final é $|+⟩$ [439].
   4. Se $F(0)\ne F(1)$ (Balanceada), o estado final é $|-⟩$ [443].
5. Aplica-se Hadamard no primeiro qubit [446].
   1. Se o resultado da medição for 0, $F$ é constante [449].
   2. Se o resultado for 1, $F$ é balanceada [449].

8.2. Algoritmo de Deutsch-Jozsa (N Qubits) [452]

1. Generaliza o problema de Deutsch para funções que aceitam $N$ bits de entrada [452].
2. Computador clássico precisa de $2^{N-1}+1$ consultas no pior caso [459].
3. O algoritmo quântico resolve em uma única consulta [464].
4. Identidade Chave 1: Aplicar Hadamard em $N$ zeros resulta em superposição uniforme [468].
   1. $|\psi ⟩=\frac{1}{\sqrt{2^N}}{\sum }_x|x⟩$ [479].
5. Identidade Chave 2: Aplicar Hadamard em um estado de superposição geral $|X⟩$ [501].
6. Análise: A amplitude do estado $|00...0⟩$ após a aplicação do Oráculo de Fase é analisada [504].
   1. Se $F$ é Constante, a amplitude de $|0...0⟩$ é $\pm 1$ [512].
   2. Se $F$ é Balanceada, a amplitude de $|0...0⟩$ é 0 [516].
7. Medindo o estado final [517]:
   1. Medir $|0...0⟩$ significa que a função é constante (probabilidade 1) [519].
   2. Medir qualquer outro estado significa que a função é balanceada (probabilidade 0 para $|0...0⟩$) [520].

8.3. Algoritmo de Bernstein-Vazirani [525]

1. Problema: Encontrar uma string secreta $S$ de comprimento $N$ [527].
   1. A função $F(X)$ é o produto escalar de $X$ e $S$ módulo 2: $F(X)=X\cdot S(\mathrm{mod}2)$ [527].
2. Computador clássico precisa de $N$ consultas (uma para cada bit de $S$) [530].
3. O algoritmo quântico resolve em uma única consulta [530].
4. O circuito é similar ao de Deutsch-Jozsa, mas o segundo qubit começa em $|-⟩$ [531].
5. O Oráculo de Fase aplica $(-1{)}^{X\cdot S}$ ao estado $|X⟩|-⟩$ [537].
6. Após aplicar Hadamard em todos os qubits, o estado final é $|S⟩$ [546].
   1. A probabilidade de medir $S$ é 1 [552].
7. O padrão de aplicar Hadamard, aplicar função, aplicar Hadamard é comum em muitos algoritmos [556].

8.4. Transformada Quântica de Fourier (QFT) [558]

1. A QFT é usada em algoritmos como Shor e estimação de fase quântica [557].
2. Intuição: Transforma a codificação binária clássica (bits 0/1) em codificação de fase nos qubits [561].
   1. Para $N$ qubits, o último qubit tem $2^N$ possíveis posições de fase [565].
3. Exemplo: O número 5 (binário 101) é codificado por rotações específicas no eixo Z de cada qubit [568].
4. O circuito QFT usa Portas $R_K$ controladas e Portas Swap [573].
   1. A porta $R_K$ aplica uma fase relativa específica: $|1⟩\to e^{2\pi i/2^K}|1⟩$ [578].
   2. A porta Swap troca os estados de dois qubits [580].
5. A QFT codifica o valor de entrada $J$ na fase dos qubits [596].
6. A fórmula geral para QFT em um estado de base $|J⟩$ envolve uma soma complexa [599].
7. A Transformada Quântica de Fourier Inversa desfaz a QFT [600].

8.5. Algoritmo de Estimação de Fase Quântica (QPE) [602]

1. O QPE encontra o autovalor ($e^{i\theta }$) de um autovetor ($|V⟩$) de uma matriz $U$ [602].
   1. $U|V⟩=e^{i\theta }|V⟩$. O QPE encontra $e^{i\theta }$ com precisão $M$ [604].
2. O QPE é crucial para o Algoritmo de Shor [605].
3. O circuito QPE tem dois registradores: um para armazenar a fase estimada ($M$ zeros) e um para o autovetor $|V⟩$ ($N$ qubits) [607].
4. Processo: Aplica-se Hadamard no primeiro registro [613].
5. Aplica-se $U^{2^k}$ controlado pelo $k$-ésimo qubit do primeiro registro, com $|V⟩$ como alvo [614].
   1. O phase kickback aplica a fase $e^{i{2}^k\theta }$ ao qubit de controle [615].
6. Após aplicar todas as potências de $U$, o primeiro registro contém um estado relacionado a $\theta$ [618].
7. Fazendo $\theta =2\pi J$, onde $J$ é uma string de bits, o estado final do primeiro registro é $|J⟩$ após a QFT Inversa [620].
8. Medindo o primeiro registro, obtemos $J$, que permite calcular $\theta =2\pi J$ [631].

8.6. Algoritmo de Shor (Fatoração) [632]

1. Shor permite encontrar os fatores primos ($P$ e $Q$) de um número $N=PQ$ [633].
2. Requer um computador quântico tolerante a falhas (ainda não disponível) [635].
3. Passo Clássico: Escolher $A$ tal que $\text{GCD}(A,N)=1$ [637].
4. O problema se reduz a encontrar o período ($R$) da exponenciação modular $A^x(\mathrm{mod}N)$ [641].
   1. O período $R$ é o menor inteiro positivo tal que $A^R\equiv 1(\mathrm{mod}N)$ [645].
5. Passo Quântico: Usa-se a QPE para encontrar $R$ [649].
   1. É construída uma porta $U$ que transforma $|X⟩\to |X\cdot A(\mathrm{mod}N)⟩$ [650].
   2. O estado inicial é $|1⟩(\mathrm{mod}N)$ (criado aplicando $U$ ao estado $|0⟩$ repetidamente) [663].
   3. O estado $|1⟩(\mathrm{mod}N)$ é um autovetor de $U$ com autovalor $e^{2\pi iS/R}$ [658].
   4. QPE estima $J=S/R$ com precisão $M$ [670].
6. Passo Clássico Final: Estimar $S$ e $R$ usando frações contínuas em $J$ [673].
   1. O período $R$ deve ter um denominador menor que $N$ [679].
7. Usando $R$, calcula-se $\text{GCD}(A^{R/2}-1,N)$ e $\text{GCD}(A^{R/2}+1,N)$ [682].
   1. Estes GCDs têm alta probabilidade de serem os fatores $P$ e $Q$ [685].
8. Exemplo com $N=15$: Escolhe-se $A=7$. O período $R=4$. Os fatores encontrados são 3 e 5 [687].