Algoritmo de Shor

Agora, voltaremos nossa atenção para o problema de fatoração de números inteiros e veremos como ele pode ser resolvido de forma eficiente em um computador quântico usando a estimativa de fase. O algoritmo que obteremos é o algoritmo de Shor para fatoração de números inteiros. Shor não descreveu seu algoritmo especificamente em termos de estimativa de fase, mas essa é uma maneira natural e intuitiva de explicar como ele funciona.

Começaremos discutindo um problema intermediário conhecido como problema de determinação de ordem e veremos como a estimativa de fase fornece uma solução para esse problema. Em seguida, veremos como uma solução eficiente para o problema de determinação de ordem nos dá uma solução eficiente para o problema de fatoração de números inteiros. (Quando uma solução para um problema fornece uma solução para outro problema como esse, dizemos que o segundo problema se reduz ao primeiro - portanto, nesse caso, estamos reduzindo a fatoração de números inteiros à determinação de ordens) Essa segunda parte do algoritmo de Shor não faz uso da computação quântica; é totalmente clássica. A computação quântica é necessária apenas para solucionar a determinação de ordens.

---

O problema da localização de pedidos

Algumas noções básicas de teoria dos números

Para explicar o problema de determinação de ordem e como ele pode ser resolvido usando a estimativa de fase, será útil começar com alguns conceitos básicos da teoria dos números e introduzir algumas notações úteis ao longo do caminho.

Para começar, para qualquer número inteiro positivo $N$, defina o conjunto $\mathbb{Z}_N$ da seguinte maneira.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Por exemplo, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ e assim por diante.

São conjuntos de números, mas podemos considerá-los como algo mais do que apenas conjuntos. Em particular, podemos pensar em operações aritméticas em $\mathbb{Z}_N$, como adição e multiplicação — e se concordarmos em sempre considerar nossos resultados módulo $N$ (ou seja, dividir por $N$ e tomar o resto como resultado), permaneceremos sempre dentro desse conjunto ao realizarmos essas operações. As duas operações específicas de adição e multiplicação, ambas consideradas módulo $N$, transformam $\mathbb{Z}_N$ em um anel, que é um tipo de objeto de importância fundamental na álgebra.

Por exemplo, $3$ e $5$ são elementos de $\mathbb{Z}_7$, e se os multiplicarmos, obtemos $3\cdot 5 = 15$, o que deixa um resto de $1$ quando dividido por $7$. Às vezes, expressamos isso da seguinte maneira.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Mas também podemos simplesmente escrever $3 \cdot 5 = 1$, desde que tenha ficado claro que estamos trabalhando em $\mathbb{Z}_7$, apenas para manter nossa notação o mais simples possível.

A título de exemplo, aqui estão as tabuadas de adição e multiplicação para o número $\mathbb{Z}_6$.

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Entre os elementos $N$ do conjunto $\mathbb{Z}_N$, os elementos $a\in\mathbb{Z}_N$ que satisfazem a condição $\gcd(a,N) = 1$ são especiais. Frequentemente, o conjunto que contém esses elementos é representado por um asterisco, assim.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Se concentrarmos nossa atenção na operação de multiplicação, o conjunto $\mathbb{Z}_N^{\ast}$ forma um grupo — mais especificamente, um grupo abeliano —, que é outro tipo importante de objeto na álgebra. É um fato básico sobre esses conjuntos (e grupos finitos em geral) que, se escolhermos qualquer elemento $a\in\mathbb{Z}_N^{\ast}$ e multiplicarmos repetidamente $a$ por si mesmo, sempre chegaremos, eventualmente, ao número $1$.

Como primeiro exemplo, vamos considerar $N=6$. Temos que $5\in\mathbb{Z}_6^{\ast}$, pois $\gcd(5,6) = 1$; e, se multiplicarmos $5$ por si mesmo, obtemos $1$, conforme confirma a tabela acima.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Como segundo exemplo, vamos considerar $N = 21$. Se analisarmos os números de $0$ a $20$, aqueles cujo MMC é igual a $1$ com $21$ são os seguintes.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Para cada um desses elementos, é possível elevar esse número a uma potência inteira positiva para obter um número d $1$ o. Aqui estão as menores potências para as quais isso funciona:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Naturalmente, estamos trabalhando no site $\mathbb{Z}_{21}$ para todas essas equações, que não nos preocupamos em escrever - consideramos implícitas para evitar confusão. Continuaremos a fazer isso durante o restante da lição.

Descrição do problema e conexão com a estimativa de fase

Agora, podemos definir o problema de determinação de ordem.

Entrada: inteiros positivos $N$ e $a$ que satisfazem $\gcd(N,a) = 1$\ Saída: o menor inteiro positivo $r$ tal que $a^r \equiv 1$ $(\textrm{mod } N)$

Alternativamente, utilizando a notação que acabamos de apresentar acima, temos $a \in \mathbb{Z}_N^{\ast}$ e estamos procurando o menor inteiro positivo $r$ tal que $a^r = 1$. Esse número $r$ é chamado de ordem de $a$ módulo $N$.

Para relacionar o problema da determinação da ordem à estimativa de fase, vamos considerar a operação definida em um sistema cujos estados clássicos correspondem a $\mathbb{Z}_N$, onde multiplicamos por um elemento fixo $a\in\mathbb{Z}_N^{\ast}$.

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

Para ficar claro, estamos fazendo a multiplicação em um $\mathbb{Z}_N$ o; portanto, está implícito que estamos calculando o produto módulo $N$ dentro do ket no lado direito da equação.

Por exemplo, se considerarmos $N = 15$ e $a=2$, a ação de $M_2$ na base padrão $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ é a seguinte.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Esta é uma operação unitária, desde que $\gcd(a,N)=1$; ela embaralha os elementos da base padrão $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$; portanto, como matriz, trata-se de uma matriz de permutação. Fica evidente, a partir de sua definição, que essa operação é determinística, e uma maneira simples de perceber que ela é invertível é pensar na ordem $r$ de $a$ módulo $N$ e reconhecer que o inverso de $M_a$ é $M_a^{r-1}$.

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Há outra maneira de pensar sobre a inversa que não requer nenhum conhecimento sobre o “ $r$ ” (que, afinal, é o que estamos tentando calcular). Para cada elemento $a\in\mathbb{Z}_N^{\ast}$, existe sempre um elemento único $b\in\mathbb{Z}_N^{\ast}$ que satisfaz $ab=1$. Denotamos esse elemento $b$ por $a^{-1}$, e ele pode ser calculado de forma eficiente; uma extensão do algoritmo do MMC de Euclides realiza isso com custo quadrático em $\operatorname{lg}(N)$. E, portanto,

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Portanto, a operação $M_a$ é determinística e invertível. Isso implica que ela é descrita por uma matriz de permutação e, portanto, é unitária.

Agora, vamos pensar nos vetores próprios e nos valores próprios da operação $M_a$, supondo que $a\in\mathbb{Z}_N^{\ast}$. Conforme acabamos de argumentar, essa suposição nos indica que $M_a$ é unitária.

Existem $N$ valores próprios de $M_a$, podendo incluir o mesmo valor próprio repetido várias vezes, e, em geral, há certa liberdade na escolha dos vetores próprios correspondentes — mas não precisamos nos preocupar com todas as possibilidades. Vamos começar de forma simples e identificar apenas um vetor próprio d $M_a$ o.

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

O número $r$ é a ordem de $a$ módulo $N$, aqui e ao longo do restante da aula. O autovalor associado a esse autovetor é $1$, pois ele não sofre alteração quando o multiplicamos por $a$.

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Isso acontece porque $a^r = 1$; portanto, cada estado da base padrão $\vert a^k \rangle$ é deslocado para $\vert a^{k+1} \rangle$ para $k\leq r-1$, e $\vert a^{r-1} \rangle$ volta a $\vert 1\rangle$. Em termos informais, é como se estivéssemos mexendo lentamente $\vert \psi_0 \rangle$, mas ele já está completamente misturado, então nada muda.

Aqui está outro exemplo de vetor próprio de um $M_a$ o. Este, por acaso, é mais interessante no contexto da determinação da ordem e da estimativa de fase.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Como alternativa, podemos escrever esse vetor usando um somatório da seguinte forma.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Aqui, vemos o número complexo $\omega_r = e^{2\pi i/r}$ surgir naturalmente, devido à forma como a multiplicação por $a$ funciona módulo $N$. Desta vez, o autovalor correspondente é $\omega_r$. Para comprovar isso, podemos primeiro fazer o seguinte cálculo.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Então, como $\omega_r^{-r} = 1 = \omega_r^0$ e $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$, vemos que

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

Então, $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$.

Seguindo o mesmo raciocínio, podemos identificar outros pares de vetores próprios e valores próprios para $M_a$. Para qualquer escolha de $j\in\{0,\ldots,r-1\}$, temos que

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

é um vetor próprio de $M_a$ cujo valor próprio correspondente é $\omega_r^j$.

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Existem outros vetores próprios de $M_a$, mas não precisamos nos preocupar com eles — vamos nos concentrar exclusivamente nos vetores próprios $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ que acabamos de identificar.

---

Localização de ordem por meio de estimativa de fase

Para resolver o problema de determinação da ordem para uma determinada escolha de $a\in\mathbb{Z}_N^{\ast}$, podemos aplicar o procedimento de estimativa de fase à operação $M_a$.

Para isso, precisamos implementar não apenas $M_a$ de forma eficiente com um circuito quântico, mas também $M_a^2$, $M_a^4$, $M_a^8$ e assim por diante, indo tão longe quanto for necessário para obter uma estimativa suficientemente precisa a partir do procedimento de estimativa de fase. Aqui, vamos explicar como isso pode ser feito e, mais adiante, vamos determinar exatamente qual o nível de precisão necessário.

Vamos começar pela operação “ $M_a$ ” por si só. Naturalmente, como estamos trabalhando com o modelo de circuito quântico, usaremos a notação binária para codificar os números entre $0$ e $N-1$. O maior número que precisamos codificar é $N-1$, portanto, o número de bits de que precisamos é

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Por exemplo, se $N = 21$, temos $n = \operatorname{lg}(N-1) = 5$. Veja a seguir como fica a codificação dos elementos de $\mathbb{Z}_{21}$ como cadeias binárias de comprimento $5$.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

E agora, aqui está uma definição precisa de como $M_a$ é definido como uma operação de $n$ -qubit.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

A questão é que, embora nos importemos apenas com o funcionamento de $M_a$ para $\vert 0\rangle,\ldots,\vert N-1\rangle$, precisamos especificar como isso funciona para os demais estados da base padrão $2^n - N$ — e precisamos fazer isso de forma que ainda nos proporcione uma operação unitária. Isso é conseguido definindo-se a função “ $M_a$ ” de forma que ela não altere os demais estados da base padrão.

Utilizando os algoritmos de multiplicação e divisão de números inteiros discutidos na lição anterior, juntamente com a metodologia para implementações reversíveis e sem resíduos desses algoritmos, podemos construir um circuito quântico que execute a operação “ $M_a$ ”, para qualquer escolha de $a\in\mathbb{Z}_N^{\ast}$, com custo $O(n^2)$. Aqui está uma maneira de fazer isso.

1. Construa um circuito para realizar a operação

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

em que

$$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

utilizando o método descrito na aula anterior. Isso nos dá um circuito de tamanho $O(n^2)$.

2. Troque os dois sistemas de $n$ -qubit usando $n$ swap gates para trocar os qubits individualmente.

3. De forma semelhante à primeira etapa, construa um circuito para a operação

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

onde $a^{-1}$ é a inversa de $a$ em $\mathbb{Z}_N^{\ast}$.

Ao inicializar os $n$ qubits inferiores e compor as três etapas, obtemos essa transformação:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

O método requer qubits do espaço de trabalho, mas eles são retornados ao seu estado inicializado ao final, o que nos permite usar esses circuitos para a estimativa de fase. O custo total do circuito que obtemos é $O(n^2)$ es.

Para executar $M_a^2$, $M_a^4$, $M_a^8$ e assim por diante, podemos usar exatamente o mesmo método, exceto que substituímos $a$ por $a^2$, $a^4$, $a^8$ e assim por diante, como elementos de $\mathbb{Z}_N^{\ast}$. Ou seja, para qualquer potência $k$ que escolhermos, podemos criar um circuito para $M_a^k$ não iterando $k$ vezes o circuito para $M_a$, mas sim calculando $b = a^k \in \mathbb{Z}_N^{\ast}$ e, em seguida, usando o circuito para $M_b$.

O cálculo de potências $a^k \in \mathbb{Z}_N$ corresponde ao problema da exponenciação modular mencionado na aula anterior. Esse cálculo pode ser feito de forma clássica, utilizando o algoritmo de exponenciação modular mencionado na aula anterior (frequentemente chamado de algoritmo da potência na teoria computacional dos números). Na verdade, precisamos apenas das potências d power-of-2 de $a$, em particular $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$, e podemos obter essas potências elevando $m-1$ ao quadrado repetidamente. Cada elevação ao quadrado pode ser realizada por um circuito booleano de tamanho $O(n^2)$.

Em essência, o que estamos fazendo aqui, na prática, é transferir o problema de iterar $M_a$ tantas vezes quanto $2^{m-1}$ para um cálculo clássico eficiente. E é uma sorte que isso seja possível! Para uma escolha arbitrária de um circuito quântico no problema da estimativa de fase, é improvável que isso seja possível — e, nesse caso, o custo resultante para a estimativa de fase cresce exponencialmente em função do número de qubits de controle $m$.

Solução dada um vetor próprio conveniente

Para entender como podemos resolver o problema da determinação da ordem usando a estimativa de fase, vamos começar supondo que executemos o procedimento de estimativa de fase na operação $M_a$ usando o vetor próprio $\vert\psi_1\rangle$. Conseguir esse vetor próprio não é fácil, como veremos, então a história não termina aqui — mas é útil começar por aqui.

O valor próprio de $M_a$ correspondente ao vetor próprio $\vert \psi_1\rangle$ é

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Ou seja, $\omega_r = e^{2\pi i \theta}$ para $\theta = 1/r$. Portanto, se aplicarmos o procedimento de estimativa de fase em $M_a$ usando o vetor próprio $\vert\psi_1\rangle$, obteremos uma aproximação de $1/r$. Ao calcular o recíproco, poderemos determinar $r$ — desde que nossa aproximação seja boa o suficiente.

Mais detalhadamente, quando executamos o procedimento de estimativa de fase utilizando qubits de control $m$, o que obtemos é um número $y\in\{0,\ldots,2^m-1\}$. Em seguida, tomamos $y/2^m$ como uma estimativa para $\theta$, que, no caso em questão, é $1/r$. Para determinar qual é o valor de $r$ a partir dessa aproximação, o mais natural a se fazer é calcular o recíproco da nossa aproximação e arredondar para o inteiro mais próximo.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Por exemplo, suponhamos que $r = 6$ e realizemos a estimativa de fase em $M_a$ com o vetor próprio $\vert\psi_1\rangle$ utilizando $m = 5$ bits de controle. A melhor aproximação de $5$ -bit para $1/r = 1/6$ é $5/32$, e temos uma chance bastante boa (cerca de $68\%$ neste caso) de obter o resultado $y=5$ a partir da estimativa de fase. Temos

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

e, ao arredondar para o inteiro mais próximo, obtém-se $6$, que é a resposta correta.

Por outro lado, se não usarmos precisão suficiente, talvez não cheguemos à resposta correta. Por exemplo, se considerarmos qubits de control $m = 4$ es na estimativa de fase, poderemos obter a melhor aproximação de $4$ bits para $1/r = 1/6$, que é $3/16$. Calculando o recíproco, obtém-se

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

e, ao arredondar para o inteiro mais próximo, obtém-se uma resposta incorreta de $5$.

Então, qual é o nível de precisão necessário para chegarmos à resposta correta? Sabemos que a ordem $r$ é um número inteiro e, intuitivamente, o que precisamos é de precisão suficiente para distinguir $1/r$ de possibilidades próximas, incluindo $1/(r+1)$ e $1/(r-1)$. O número mais próximo de $1/r$ com o qual precisamos nos preocupar é $1/(r+1)$, e a distância entre esses dois números é

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Portanto, se quisermos ter certeza de que não confundiremos $1/r$ com $1/(r+1)$, basta usar precisão suficiente para garantir que a melhor aproximação $y/2^m$ de $1/r$ esteja mais próxima de $1/r$ do que de $1/(r+1)$. Se usarmos precisão suficiente para que

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

de modo que o erro seja menor que a metade da distância entre $1/r$ e $1/(r+1)$; nesse caso, $y/2^m$ estará mais próximo de $1/r$ do que de qualquer outra possibilidade, incluindo $1/(r+1)$ e $1/(r-1)$.

Podemos verificar isso da seguinte forma. Suponha que

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

para $\varepsilon$ satisfazendo

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Quando tomamos a recíproca, obtemos

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Ao maximizar no numerador e minimizar no denominador, podemos limitar a distância que estamos de $r$ da seguinte forma.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Estamos a menos de $1/2$ de distância de $r$, então, como era de se esperar, chegaremos a $r$ ao arredondar.

Infelizmente, como ainda não sabemos o que é $r$, não podemos usá-lo para nos dizer de quanta precisão precisamos. O que podemos fazer é usar o fato de que $r$ deve ser menor que $N$ para garantir que usemos precisão suficiente. Em particular, se usarmos precisão suficiente para garantir que a melhor aproximação $y/2^m$ para $1/r$ satisfaça

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

então teremos precisão suficiente para determinar corretamente $r$ quando tomarmos a recíproca. O site $m = 2\operatorname{lg}(N)+1$ garante que temos uma grande chance de obter uma estimativa com essa precisão usando o método descrito anteriormente. (O site $m = 2\operatorname{lg}(N)$ é bom o suficiente se estivermos confortáveis com um limite inferior de 40% na probabilidade de sucesso)

Solução geral

Como acabamos de ver, se tivermos o vetor próprio $\vert \psi_1 \rangle$ de $M_a$, podemos determinar $r$ por meio da estimativa de fase, desde que utilizemos um número suficiente de qubits de controle para realizar isso com precisão adequada. Infelizmente, não é fácil obter o vetor próprio $\vert\psi_1\rangle$, por isso precisamos descobrir como proceder.

Suponhamos, por um instante, que procedamos exatamente como acima, exceto que utilizaremos o vetor próprio $\vert\psi_k\rangle$ em vez de $\vert\psi_1\rangle$, para qualquer escolha de $k\in\{0,\ldots,r-1\}$ que decidirmos considerar. O resultado que obtemos do procedimento de estimativa de fase será uma aproximação

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Partindo do pressuposto de que não sabemos nem $k$ nem $r$, isso pode ou não nos permitir identificar $r$. Por exemplo, se $k = 0$, obteremos uma aproximação $y/2^m$ para $0$, o que, infelizmente, não nos diz nada. Este, no entanto, é um caso incomum; para outros valores de $k$, poderemos, pelo menos, aprender algo sobre $r$.

Podemos usar um algoritmo conhecido como algoritmo de fração contínua para transformar nossa aproximação $y/2^m$ em frações próximas - incluindo $k/r$ se a aproximação for boa o suficiente. Não explicaremos o algoritmo de fração contínua aqui. Em vez disso, aqui está uma declaração de um fato conhecido sobre esse algoritmo.

Dados um número inteiro $N\geq 2$ e um número real $\alpha\in(0,1)$, há, no máximo, uma escolha de números inteiros $u,v\in\{0,\ldots,N-1\}$ tais que $v\neq 0$ e $\gcd(u,v)=1$ satisfaçam $\vert \alpha - u/v\vert < \frac{1}{2N^2}$. Dados $\alpha$ e $N$, o algoritmo de frações contínuas encontra $u$ e $v$, ou informa que eles não existem. Esse algoritmo pode ser implementado como um circuito booleano com tamanho $O((\operatorname{lg}(N))^3)$.

Se tivermos uma aproximação muito próxima $y/2^m$ para $k/r$ e aplicarmos o algoritmo da fração contínua para $N$ e $\alpha = y/2^m$, obteremos $u$ e $v$, conforme descrito no enunciado. Uma análise dos fatos nos permite concluir que

$$\frac{u}{v} = \frac{k}{r}.$$

Observe, em particular, que não aprendemos necessariamente que $k$ e $r$; aprendemos apenas que $k/r$ na forma mais simples possível.

Por exemplo, e como já percebemos, não vamos aprender nada com $k=0$. Mas esse é o único valor de $k$ em que isso ocorre. Quando $k$ é diferente de zero, pode ter fatores comuns com $r$, mas o número $v$ que obtemos a partir do algoritmo da fração contínua deve, no mínimo, dividir $r$.

Isso está longe de ser óbvio, mas é verdade que, se tivermos a capacidade de aprender $u$ e $v$ para $u/v = k/r$ para $k\in\{0,\ldots,r-1\}$, escolhidos aleatoriamente de maneira uniforme, então é muito provável que consigamos recuperar $r$ após apenas algumas amostras. Em particular, se nossa suposição para $r$ for o mínimo múltiplo comum de todos os valores do denominador $v$ que observamos, estaremos certos com alta probabilidade. Intuitivamente falando, alguns valores de $k$ não são bons porque compartilham fatores comuns com $r$, e esses fatores comuns ficam ocultos para nós quando aprendemos $u$ e $v$. Mas escolhas aleatórias de $k$ provavelmente não ocultarão por muito tempo os fatores de $r$, e a probabilidade de não adivinharmos $r$ corretamente ao calcular o mínimo múltiplo comum dos denominadores que observamos diminui exponencialmente com o aumento do número de amostras.

Resta abordar a questão de como obter um vetor próprio $\vert\psi_k\rangle$ de $M_a$ para executar o procedimento de estimativa de fase. Acontece que, na verdade, não precisamos criá-los!

O que faremos, em vez disso, é aplicar o procedimento de estimativa de fase ao estado $\vert 1\rangle$, ou seja, a codificação binária de $n$ bits do número $1$, em vez de um vetor próprio $\vert\psi\rangle$ de $M_a$. Até agora, falamos apenas sobre aplicar o procedimento de estimativa de fase a um vetor próprio específico, mas nada nos impede de aplicar o procedimento a um estado de entrada que não seja um vetor próprio de $M_a$, e é isso que estamos fazendo aqui com o estado $\vert 1\rangle$. (Isso não é um vetor próprio de $M_a$, a menos que $a=1$, o que não é uma possibilidade que nos interesse.)

A justificativa para escolher o estado $\vert 1\rangle$ em vez de um vetor próprio de $M_a$ é que a equação a seguir é verdadeira.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Uma maneira de verificar essa equação é comparar os produtos internos dos dois lados com cada estado da base padrão, usando as fórmulas mencionadas anteriormente na lição para ajudar a avaliar os resultados do lado direito. Como consequência, obteremos exatamente os mesmos resultados de medição como se tivéssemos escolhido $k\in\{0,\ldots,r-1\}$ uniformemente de forma aleatória e usado $\vert\psi_k\rangle$ como um vetor próprio.

Mais detalhadamente, imaginemos que executemos o procedimento de estimativa de fase com o estado $\vert 1\rangle$ no lugar de um dos vetores próprios $\vert\psi_k\rangle$. Após a realização da transformada de Fourier quântica inversa, isso nos deixa com o estado

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

em que

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

O vetor $\vert\gamma_k\rangle$ representa o estado dos $m$ qubits superiores depois que o inverso da transformação quântica de Fourier foi realizado neles.

Assim, em virtude do fato de que $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ é um conjunto ortonormal, descobrimos que uma medição dos principais $m$ qubits superior produz uma aproximação $y/2^m$ do valor $k/r$ em que $k\in\{0,\ldots,r-1\}$ é escolhido uniformemente de forma aleatória. Como já discutimos, isso nos permite aprender $r$ com um alto grau de confiança após várias execuções independentes, que era o nosso objetivo.

Custo total

O custo para implementar cada operação controlada-unitária $M_a^k$ é $O(n^2)$. Existem $m$ operações controladas-unitárias, e temos $m = O(n)$, portanto, o custo total das operações controladas-unitárias é $O(n^3)$. Além disso, temos $m$ portas de Hadamard (que contribuem com $O(n)$ para o custo), e a transformada de Fourier quântica inversa contribui com $O(n^2)$ para o custo. Assim, o custo das operações unitárias controladas predomina sobre o custo de todo o procedimento — que é, portanto, $O(n^3)$.

Além do próprio circuito quântico, há alguns cálculos clássicos que precisam ser realizados ao longo do processo. Isso inclui o cálculo das potências $a^k$ em $\mathbb{Z}_N$ para $k = 2, 4, 8, \ldots, 2^{m-1}$, necessárias para criar as portas unitárias controladas, bem como o algoritmo de frações contínuas que converte aproximações de $\theta$ em frações. Esses cálculos podem ser realizados por circuitos booleanos com um custo total de $O(n^3)$.

Como é típico, todos esses limites podem ser aprimorados usando algoritmos assintoticamente rápidos; esses limites pressupõem que estamos usando algoritmos padrão para operações aritméticas básicas.

---

Factoring por encomenda

A última coisa que precisamos discutir é como a solução do problema de determinação de ordem nos ajuda a fatorar. Essa parte é totalmente clássica - não tem nada a ver especificamente com a computação quântica.

A ideia básica é a seguinte. Queremos fatorar o número $N$ e podemos fazer isso de forma recursiva. Especificamente, podemos nos concentrar na tarefa de dividir $N$, o que significa encontrar quaisquer dois números inteiros $b,c\geq 2$ para os quais $N = bc$. Isso não é possível se $N$ for um número primo, mas podemos verificar de forma eficiente se $N$ é primo usando primeiro um algoritmo de teste de primalidade; e, se $N$ não for primo, tentaremos dividi-lo. Depois de dividir $N$, basta aplicar a recursão em $b$ e $c$ até que todos os nossos fatores sejam primos e obtenhamos a fatoração em números primos de $N$.

Dividir números inteiros pares é fácil: basta exibir $2$ e $N/2$.

Também é fácil dividir potências perfeitas, ou seja, números da forma $N = s^j$ para inteiros $s,j\geq 2$, simplesmente aproximando as raízes $N^{1/2}$, $N^{1/3}$, $N^{1/4}$ e assim por diante, e verificando os inteiros próximos como possíveis candidatos para $s$. Não precisamos ir além de $\log(N)$ passos nessa sequência, pois, nesse ponto, a raiz fica abaixo de $2$ e não revelará candidatos adicionais.

É bom que possamos fazer essas duas coisas, pois a busca de ordem não nos ajudará a fatorar números pares nem no caso de potências de números primos, em que o número $s$ por acaso é primo. No entanto, se $N$ for ímpar e não for uma potência de um número primo, a determinação da ordem nos permite dividir $N$.

1. Escolha aleatoriamente $a\in\{2,\ldots,N-1\}$.

2. Calcule $d=\gcd(a,N)$.

3. Se $d > 1$, então exiba $b = d$ e $c = N/d$ e encerre a execução. Caso contrário, prossiga para a próxima etapa, sabendo que $a\in\mathbb{Z}_N^{\ast}$.

4. Seja $r$ a ordem de $a$ módulo $N$. (É aqui que precisamos da localização de pedidos.)

5. Se $r$ estiver empatado:

   5.1 Calcule$x = a^{r/2} - 1$ módulo$N$

   5.2
   Calcule$d = \gcd(x,N)$ . 5.3
   Se$d>1$ , então exiba$b=d$ e$c = N/d$ e pare.

6. Se esse ponto for alcançado, significa que o algoritmo não conseguiu encontrar um fator de $N$.

É possível que uma execução deste algoritmo não consiga encontrar um fator de $N$. Mais especificamente, isso ocorre em duas situações:

• A ordem de $a$ modulo $N$ é ímpar.
• A ordem de $a$ módulo $N$ é par e $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$.

Utilizando-se da teoria básica dos números, é possível provar que, para uma escolha aleatória de $a$, com probabilidade de pelo menos $1/2$, nenhum desses eventos ocorre. De fato, a probabilidade de que qualquer um dos eventos ocorra é, no máximo, $2^{-(m-1)}$, sendo $m$ o número de fatores primos distintos de $N$, e é por isso que é necessária a suposição de que $N$ não seja uma potência de um número primo. (Para que esse fato seja verdadeiro, também é necessário supor que $N$ seja ímpar.)

Isso significa que cada execução tem pelo menos 50% de chance de dividir $N$. Portanto, se executarmos o algoritmo $t$ vezes, escolhendo aleatoriamente $a$ a cada vez, conseguiremos dividir $N$ com uma probabilidade de pelo menos $1 - 2^{-t}$.

A ideia básica por trás do algoritmo é a seguinte. Se tivermos uma opção de $a$ para a qual a ordem $r$ de $a$ modulo $N$ seja par, então $r/2$ é um número inteiro e podemos considerar os números

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Utilizando a fórmula $Z^2 - 1 = (Z+1)(Z-1)$, concluímos que

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Ora, sabemos que $a^r \; (\textrm{mod}\; N) = 1$, pela definição da ordem — o que é outra forma de dizer que $N$ divide inteiramente $a^r - 1$. Isso significa que $N$ divide inteiramente o produto

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Para que isso seja verdade, todos os fatores primos de $N$ também devem ser fatores primos de $a^{r/2} - 1$ ou $a^{r/2} + 1$ (ou ambos) - e, para uma seleção aleatória de $a$, é improvável que todos os fatores primos de $N$ dividam um dos termos e nenhum divida o outro. Caso contrário, desde que alguns dos fatores primos de $N$ dividam o primeiro termo e alguns dividam o segundo termo, poderemos encontrar um fator não trivial de $N$ calculando o GCD com o primeiro termo.