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 forma.

$$\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.

Esses são conjuntos de números, mas podemos pensar neles como algo mais do que 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 nossas respostas no módulo $N$ (ou seja, dividir por $N$ e tomar o restante como resultado), sempre estaremos dentro desse conjunto quando realizarmos essas operações. As duas operações específicas de adição e multiplicação, ambas tomadas no módulo $N,$, transformam o $\mathbb{Z}_N$ em um anel, que é um tipo de objeto fundamentalmente importante na álgebra.

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

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

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

Como exemplo, aqui estão as tabelas de adição e multiplicação para $\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$ de $\mathbb{Z}_N,$, os elementos $a\in\mathbb{Z}_N$ que satisfazem $\gcd(a,N) = 1$ são especiais. Frequentemente, o conjunto que contém esses elementos é denotado por uma estrela, como a seguir.

$$\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 - 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 ele mesmo, sempre obteremos o número $1.$

Para um primeiro exemplo, vamos pegar $N=6.$ Temos que $5\in\mathbb{Z}_6^{\ast}$ porque $\gcd(5,6) = 1,$ e se multiplicarmos $5$ por ele mesmo, obteremos $1,$ como confirma a tabela acima.

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

Como segundo exemplo, vejamos $N = 21.$ Se analisarmos os números de $0$ a $20,$, os que têm GCD 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 $1.$ 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)$

Como alternativa, em termos da notação que acabamos de introduzir acima, recebemos $a \in \mathbb{Z}_N^{\ast},$ e estamos procurando o menor número inteiro positivo $r$ de modo que $a^r = 1.$ Esse número $r$ é chamado de ordem de $a$ modulo $N.$

Para conectar o problema de determinação de ordem à estimativa de fase, vamos pensar na 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 deixar claro, estamos fazendo a multiplicação em $\mathbb{Z}_N,$, portanto, está implícito que estamos tomando o módulo do produto $N$ dentro do ket no lado direito da equação.

Por exemplo, se tomarmos $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}$$

Essa é uma operação unitária, desde que $\gcd(a,N)=1;$ embaralhe os elementos da base padrão $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ para que, como matriz, seja uma matriz de permutação. É evidente em sua definição que essa operação é determinística, e uma maneira simples de ver que ela é invertível é pensar na ordem $r$ de $a$ modulo $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 o inverso que não requer nenhum conhecimento de $r$ (que, afinal de contas, é o que estamos tentando calcular). Para cada elemento $a\in\mathbb{Z}_N^{\ast}$, há sempre um único elemento $b\in\mathbb{Z}_N^{\ast}$ que satisfaz $ab=1.$ Denotamos esse elemento $b$ por $a^{-1},$ e ele pode ser computado com eficiência; uma extensão do algoritmo GCD de Euclides faz isso com custo quadrático em $\operatorname{lg}(N).$ E assim

$$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 e valores próprios da operação $M_a,$, supondo que $a\in\mathbb{Z}_N^{\ast}.$ Como acabamos de argumentar, essa suposição nos diz que $M_a$ é unitário.

Há $N$ valores próprios de $M_a,$, possivelmente incluindo o mesmo valor próprio repetido várias vezes e, em geral, há alguma liberdade na seleção dos vetores próprios correspondentes, mas não precisaremos nos preocupar com todas as possibilidades. Vamos começar de forma simples e identificar apenas um vetor próprio de $M_a.$

$$\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 do módulo $a$ $N,$ aqui e no restante da lição. O valor próprio associado a esse vetor próprio é $1$ porque ele não é alterado quando multiplicado 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$ é deslocado de volta para $\vert 1\rangle.$ Em termos informais, é como se estivéssemos mexendo lentamente o $\vert \psi_0 \rangle,$, mas ele já está completamente mexido, então nada muda.

Aqui está outro exemplo de um vetor próprio de $M_a.$ Esse é mais interessante no contexto da descoberta de 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 estamos vendo o número complexo $\omega_r = e^{2\pi i/r}$ aparecer naturalmente, devido à forma como a multiplicação por $a$ funciona no módulo $N.$ Desta vez, o valor próprio correspondente é $\omega_r.$ Para ver isso, podemos primeiro calcular da seguinte forma.

$$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,$$

assim $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Usando o mesmo raciocínio, podemos identificar pares adicionais de vetor próprio/valor próprio 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$$

Há outros vetores próprios de $M_a,$, mas não precisamos nos preocupar com eles - vamos nos concentrar apenas 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 de 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 o $M_a$ de forma eficiente com um circuito quântico, mas também o $M_a^2,$ $M_a^4,$ $M_a^8,$ e assim por diante, indo até onde for necessário para obter uma estimativa suficientemente precisa do procedimento de estimativa de fase. Aqui, explicaremos como isso pode ser feito e, posteriormente, descobriremos exatamente quanta precisão é necessária.

Vamos começar com a 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 necessários é

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

Por exemplo, se $N = 21$ tivermos $n = \operatorname{lg}(N-1) = 5.$ Esta é a aparência da 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 só nos importemos com o funcionamento do $M_a$ para o $\vert 0\rangle,\ldots,\vert N-1\rangle,$, temos que especificar como ele funciona para os estados restantes da base padrão do $2^n - N$ - e precisamos fazer isso de uma forma que ainda nos dê uma operação unitária. A definição de $M_a$ de modo que ele não faça nada aos estados de base padrão restantes permite isso.

Usando os algoritmos para multiplicação e divisão de números inteiros discutidos na lição anterior, juntamente com a metodologia para implementações reversíveis e livres de lixo, podemos construir um circuito quântico que execute $M_a,$ para qualquer escolha de $a\in\mathbb{Z}_N^{\ast},$ a 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}$$

usando o método descrito na lição 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$$

em que $a^{-1}$ é o inverso 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 de espaço de trabalho, mas eles retornam ao seu estado inicializado no final, o que nos permite usar esses circuitos para estimativa de fase. O custo total do circuito que obtemos é $O(n^2).$

Para executar $M_a^2,$ $M_a^4,$ $M_a^8,$ e assim por diante, podemos usar exatamente o mesmo método, exceto pelo fato de substituirmos $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 computando $b = a^k \in \mathbb{Z}_N^{\ast}$ e, em seguida, usando o circuito para $M_b.$

O cálculo das potências $a^k \in \mathbb{Z}_N$ é o problema de exponenciação modular mencionado na lição anterior. Esse cálculo pode ser feito de forma clássica, usando o algoritmo para exponenciação modular mencionado na lição anterior (geralmente chamado de algoritmo de potência na teoria dos números computacionais). De fato, exigimos apenas power-of-2 potências 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$ vezes ao quadrado de forma iterativa. Cada quadratura pode ser realizada por um circuito booleano de tamanho $O(n^2).$

Em essência, o que estamos fazendo aqui é transferir o problema de iterar $M_a$ até $2^{m-1}$ vezes para uma computação clássica eficiente. E é uma boa sorte que isso seja possível! Para uma escolha arbitrária de um circuito quântico no problema de estimativa de fase, é provável que isso não seja possível e, nesse caso, o custo resultante da estimativa de fase cresce exponencialmente no número de qubits de controle $m.$

Solução dada um vetor próprio conveniente

Para entender como podemos resolver o problema de determinação de ordem usando a estimativa de fase, vamos começar supondo que executamos o procedimento de estimativa de fase na operação $M_a$ usando o vetor próprio $\vert\psi_1\rangle.$ Obter esse vetor próprio não é fácil, como se vê, portanto, esse não será o fim da história, 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 executarmos o procedimento de estimativa de fase em $M_a$ usando o vetor próprio $\vert\psi_1\rangle,$, obteremos uma aproximação para $1/r.$ Ao calcular o recíproco, poderemos aprender $r$ - desde que nossa aproximação seja boa o suficiente.

Em mais detalhes, quando executamos o procedimento de estimativa de fase usando $m$ qubits de controle, 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 é $1/r$ no caso em questão. Para descobrir o que é $r$ a partir dessa aproximação, o mais natural é calcular o recíproco de nossa aproximação e arredondar para o número inteiro mais próximo.

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

Por exemplo, vamos supor que $r = 6$ e nós realizamos a estimativa de fase em $M_a$ com o vetor próprio $\vert\psi_1\rangle$ usando os bits de controle de $m = 5$. A melhor aproximação de $5$ bits para $1/r = 1/6$ é $5/32,$ e temos uma boa chance (cerca de $68\%$ nesse caso) de obter o resultado $y=5$ a partir da estimativa de fase. Temos

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

e arredondando para o número 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 obtenhamos a resposta correta. Por exemplo, se usarmos $m = 4$ qubits de controle na estimativa de fase, poderemos obter a melhor aproximação de $4$ -bit para $1/r = 1/6,$, que é $3/16.$ Tomando a recíproca, obtém-se

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

e o arredondamento para o número inteiro mais próximo dá uma resposta incorreta de $5.$

Então, qual é a precisão necessária para obter a resposta correta? Sabemos que a ordem $r$ é um número inteiro e, intuitivamente, o que precisamos é de precisão suficiente para distinguir $1/r$ das 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 de $y/2^m$ para $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),$, então $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 $r,$, portanto, como esperado, receberemos $r$ quando chegarmos.

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,$, poderemos aprender $r$ por meio da estimativa de fase, desde que usemos qubits de controle suficientes para fazer isso com precisão suficiente. Infelizmente, não é fácil colocar as mãos no vetor próprio $\vert\psi_1\rangle,$, portanto, precisamos descobrir como proceder.

Vamos supor momentaneamente que procedamos exatamente como acima, exceto com o vetor próprio $\vert\psi_k\rangle$ no lugar de $\vert\psi_1\rangle,$ para qualquer opção de $k\in\{0,\ldots,r-1\}$ que escolhermos pensar. O resultado que obtivermos 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 conhecemos $k$ ou $r,$, isso pode ou não nos permitir identificar $r.$ Por exemplo, se $k = 0$ for uma aproximação de $y/2^m$ para $0,$, o que, infelizmente, não nos diz nada. Esse, no entanto, é um caso incomum; para outros valores de $k,$, pelo menos poderemos 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.

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

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

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

Observe, em particular, que não aprendemos necessariamente $k$ e $r,$; aprendemos apenas $k/r$ em termos mais baixos.

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

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 uniformemente de forma aleatória, é muito provável que consigamos recuperar $r$ após apenas algumas amostras. Em particular, se nossa estimativa para $r$ for o menor 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 são ocultados de nós quando aprendemos $u$ e $v.$ Porém, as escolhas aleatórias de $k$ provavelmente não ocultarão os fatores de $r$ por muito tempo, e a probabilidade de não adivinharmos $r$ corretamente, tomando o menor múltiplo comum dos denominadores que observamos, cai exponencialmente com o 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!

Em vez disso, executaremos o procedimento de estimativa de fase no estado $\vert 1\rangle,$, ou seja, a codificação binária de $n$ bits do número $1,$ no lugar de um vetor próprio $\vert\psi\rangle$ de $M_a.$ Até agora, falamos apenas sobre a execução do procedimento de estimativa de fase em um autovetor específico, mas nada nos impede de executar o procedimento em um estado de entrada que não seja um autovetor de $M_a,$ e é isso que estamos fazendo aqui com o estado $\vert 1\rangle.$ (Esse não é um vetor próprio de $M_a$, a menos que $a=1,$ seja uma escolha que não nos interessa)

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, vamos imaginar que executamos o procedimento de estimativa de fase com o estado $\vert 1\rangle$ no lugar de um dos vetores próprios $\vert\psi_k\rangle.$ Depois que a transformada quântica inversa de Fourier é executada, ficamos 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 unitária controlada $M_a^k$ é $O(n^2).$ Há $m$ operações unitárias controladas e temos $m = O(n),$, portanto, o custo total das operações unitárias controladas é $O(n^3).$ Além disso, temos $m$ Hadamard gates (que contribuem com $O(n)$ para o custo), e a transformação quântica inversa de Fourier contribui com $O(n^2)$ para o custo. Assim, o custo das operações unitárias controladas domina 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 caminho. Isso inclui o cálculo das potências $a^k$ em $\mathbb{Z}_N$ para $k = 2, 4, 8, \ldots, 2^{m-1},$, que são necessárias para criar as portas unitárias controladas, bem como o algoritmo de fração contínua 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.

Esta é a ideia básica. 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 dois inteiros quaisquer $b,c\geq 2$ para os quais $N = bc.$ Isso não é possível se $N$ for um número primo, mas podemos testar com eficiência para ver se $N$ é primo usando um algoritmo de teste de primalidade primeiro e, se $N$ não for primo, tentaremos dividi-lo. Depois de dividirmos $N,$, podemos simplesmente recursar em $b$ e $c$ até que todos os nossos fatores sejam primos e obtenhamos a fatoração de primos de $N.$

A divisão de números inteiros pares é fácil: basta exibir $2$ e $N/2.$

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

É bom que possamos fazer essas duas coisas porque a determinação da ordem não nos ajudará a fatorar números pares ou potências primais, onde o número $s$ é primo. No entanto, se $N$ for ímpar e não for uma potência prima, a determinação da ordem nos permite dividir $N.$

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

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

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

4. Seja $r$ a ordem de $a$ modulo $N.$ (É aqui que precisamos encontrar a ordem)

5. Se $r$ estiver empatado:

   5.1 Calcular $x = a^{r/2} - 1$ modulo $N$ \ 5.2 Computar $d = \gcd(x,N).$ \ 5.3 Se for $d>1$, então, produza $b=d$ e $c = N/d$ e pare.

6. Se esse ponto for atingido, o algoritmo não conseguiu encontrar um fator de $N.$

Uma execução desse algoritmo pode não conseguir encontrar um fator de $N.$ Especificamente, isso acontece em duas situações:

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

Usando a teoria básica dos números, é possível provar que, para uma escolha aleatória de $a,$ com probabilidade mínima de $1/2$, nenhum desses eventos acontece. De fato, a probabilidade de qualquer um dos eventos acontecer é de no máximo $2^{-(m-1)}$ para $m$ sendo o número de fatores primos distintos de $N,$ razão pela qual a suposição de que $N$ não é uma potência prima é necessária. (A suposição de que $N$ é ímpar também é necessária para que esse fato seja verdadeiro)

Isso significa que cada execução tem pelo menos 50% de chance de ser dividida $N.$ Portanto, se executarmos o algoritmo $t$ vezes, escolhendo aleatoriamente $a$ a cada vez, conseguiremos dividir $N$ com 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).$$

Usando 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.$$

Agora, sabemos que $a^r \; (\textrm{mod}\; N) = 1$ pela definição da ordem - que é outra maneira de dizer que $N$ divide igualmente $a^r - 1.$ Isso significa que $N$ divide igualmente 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.