Algoritmo de Shor

Para este módulo do Qiskit in Classrooms, os estudantes precisam ter um ambiente Python funcional com os seguintes pacotes instalados:

• qiskit v2.1.0 ou mais recente
• qiskit-ibm-runtime v0.40.1 ou mais recente
• qiskit-aer v0.17.0 ou mais recente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar os pacotes acima, consulte o guia Instalar o Qiskit. Para executar jobs em computadores quânticos reais, os estudantes precisarão criar uma conta no IBM Quantum® seguindo os passos do guia Configure sua conta IBM Cloud.

Este módulo foi testado e utilizou três segundos de tempo de QPU. Isso é apenas uma estimativa. O uso real pode variar.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introdução

No início da década de 1990, havia uma crescente empolgação em torno do potencial dos computadores quânticos para resolver problemas difíceis para os computadores clássicos. Alguns cientistas da computação talentosos tinham desenvolvido algoritmos que demonstravam o poder da computação quântica para alguns problemas de nicho e artificiais, mas ninguém havia encontrado um único "killer app" da computação quântica que fosse revolucionar a área. Isso foi até 1994, quando Peter Shor desenvolveu o que hoje é chamado de algoritmo de Shor para fatorar números grandes.

Era bem conhecido na época que encontrar os fatores primos de um número grande era extremamente difícil para um computador clássico. De fato, os protocolos de segurança da internet dependiam dessa dificuldade. Shor encontrou uma maneira de encontrar esses fatores de forma exponencialmente mais eficiente, delegando algumas das etapas mais desafiadoras a um futuro computador quântico teórico.

Neste módulo, vamos explorar o algoritmo de Shor. Primeiro, daremos um pouco mais de contexto ao algoritmo, formalizando o problema que ele resolve e explicando a relevância para a cibersegurança. Em seguida, daremos uma introdução à matemática modular e como aplicá-la ao problema de fatoração, mostrando como a fatoração se reduz a outro problema chamado "busca de ordem". Mostraremos como a Transformada Quântica de Fourier e a Estimativa Quântica de Fase, que aprendemos em um módulo anterior, entram em cena e como usá-las para resolver o problema de busca de ordem.

Por fim, vamos executar o algoritmo de Shor em um computador quântico real! Tenha em mente, porém, que este algoritmo só será realmente útil quando tivermos um computador quântico grande e tolerante a falhas, o que ainda está a alguns anos de distância. Por isso, vamos apenas fatorar um número pequeno para demonstrar como o algoritmo funciona.

O problema da fatoração

O objetivo do problema da fatoração é encontrar os fatores primos de um número $N$. Para alguns números $N$, isso é bastante simples. Por exemplo, se $N$ for par, um de seus fatores primos será 2. Se $N$ for uma potência de primo, ou seja, $N=p^k$ para algum número primo $p$, também é relativamente fácil encontrar $p$: basta aproximar a $k^{\text{ésima}}$ raiz de $N$ e procurar primos próximos que possam ser $p$.

Onde os computadores clássicos têm dificuldade, porém, é quando $N$ é ímpar e não é uma potência de primo. É esse o caso que o algoritmo de Shor trata. O algoritmo encontra dois fatores $p$ e $q$ tais que $N=pq$. Ele pode ser aplicado recursivamente até que todos os fatores sejam primos. Nas próximas seções, veremos como esse problema é abordado.

Relevância para a cibersegurança

Muitos esquemas criptográficos foram construídos com base no fato de que fatorar números grandes é difícil, incluindo um amplamente utilizado atualmente, chamado RSA. No RSA, uma chave pública é criada multiplicando-se dois números primos grandes para obter $N = p\cdot q$. Então, qualquer pessoa pode usar essa chave pública para criptografar dados. Mas somente alguém com a chave privada, $p$ e $q$, pode descriptografar esses dados.

Se $N$ fosse fácil de fatorar, qualquer pessoa seria capaz de determinar $p$ e $q$ e quebrar a criptografia. Mas não é. Este é um problema notoriamente difícil. De fato, os fatores primos de um número chamado RSA1024, que tem 1024 dígitos binários e 309 dígitos decimais, ainda não foram encontrados, apesar de um prêmio de $100.000 ter sido oferecido por sua fatoração ainda em 1991.

A solução de Shor

Em 1994, Peter Shor percebeu que um computador quântico poderia fatorar um número grande de forma exponencialmente mais eficiente do que um computador clássico. Sua intuição se baseava na relação entre esse problema de fatoração e a aritmética modular. Vamos fazer uma breve introdução à aritmética modular e depois ver como podemos usá-la para fatorar $N$.

Aritmética modular

A aritmética modular é um sistema de contagem cíclico, o que significa que, embora a contagem comece da maneira usual, com os inteiros 0, 1, 2, etc., em algum momento, após um período $N$, a contagem recomeça. Veja como isso funciona com um exemplo. Digamos que nosso período seja 5. Então, enquanto contamos, onde normalmente chegaríamos ao 5, começamos de novo no 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Isso ocorre porque no mundo "módulo-5", 5 é equivalente a 0. Dizemos que $5\bmod 5 \ = 0$. De fato, todos os múltiplos de 5 serão equivalentes a $0\bmod 5$.

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Use a aritmética modular para resolver o seguinte problema:

Você parte em uma longa viagem de trem transcontinental às 8h. A viagem de trem tem 60 horas de duração. Que horas são quando você chega?

Resposta:

O período é 24, pois há 24 horas em um dia. Portanto, este problema pode ser escrito em aritmética modular como:

$(8+60)\text{mod}(24) = 20$

Portanto, você chegaria ao seu destino às 20h00.

$\mathbb{Z}_N$ e $\mathbb{Z}_N^*$

Muitas vezes é útil introduzir dois conjuntos, $\mathbb{Z}_N$ e $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ é simplesmente o conjunto de números que existem em um mundo "módulo-$N$". Por exemplo, quando contávamos módulo-5, o conjunto seria $\mathbb{Z}_5=\{0,1,2,3,4\}$. Outro exemplo: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Podemos realizar adição e multiplicação (módulo $N$) nos elementos de $\mathbb{Z}_N$, e o resultado de cada uma dessas operações também é um elemento de $\mathbb{Z}_N$, tornando $\mathbb{Z}_N$ um objeto matemático chamado anel.

Há um subconjunto especial de $\mathbb{Z}_N$ que é de particular interesse para o algoritmo de Shor. Trata-se do subconjunto de números em $\mathbb{Z}_N$ tais que o máximo divisor comum entre cada elemento e $N$ é 1, ou seja, cada elemento é "coprimo" com $N$. Se pegarmos o conjunto desses números junto com a operação de multiplicação modular, isso forma outro objeto matemático, chamado grupo. Chamamos esse grupo de $\mathbb{Z}_N^*$. Acontece que com $\mathbb{Z}_N^*$ (e grupos finitos em geral), se escolhermos qualquer elemento $a \in \mathbb{Z}_N^*$ e multiplicarmos $a$ por si mesmo repetidamente, sempre chegaremos ao número $1$. O número mínimo de vezes que se deve multiplicar $a$ por si mesmo para obter $1$ é chamado de ordem de $a$. Esse fato será muito importante para nossa discussão sobre como fatorar números a seguir.

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Qual é $\mathbb{Z}_{15}^*$?

Resposta:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Excluímos os seguintes números:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Qual é a ordem de cada elemento em $\mathbb{Z}_{15}^*$?

Resposta:

A ordem $r$ é o menor número tal que $a^r\text{mod}(15)=1$ para cada elemento $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Observe que, embora tenhamos conseguido encontrar a ordem dos números em $\mathbb{Z}_{15}^*$, essa NÃO é uma tarefa fácil em geral, para $N$ maior. Esse é o cerne do problema da fatoração e por que precisamos de um computador quântico. Veremos o porquê à medida que avançarmos pelo restante do notebook.

Aplicar a aritmética modular ao problema da fatoração

A chave para encontrar os fatores $p$ e $q$ tais que $N=pq$ se resume a encontrar algum outro inteiro $x$ tal que

$x^2 \equiv 1 \bmod N$ e $x \not\equiv \pm 1 \bmod N.$

Como encontrar $x$ nos ajuda a encontrar os fatores $p$ e $q$? Vamos percorrer o argumento agora. Como $x^2 \equiv 1 \bmod N$, isso significa que $x^2 - 1 \equiv 0 \bmod N$. Em outras palavras, $x^2 - 1$ é um múltiplo de $N$. Portanto, para algum inteiro $l$,

$x^2 - 1 = l N$

Podemos fatorar $x^2 - 1$ para obter:

$(x+1)(x-1) = l N$

De nossas suposições iniciais, sabemos que $x \not\equiv \pm 1 \bmod N$, portanto $N$ não divide de forma exata nem $x+1$ nem $x-1$. Assim, os dois fatores de $N$, $p$ e $q$, devem cada um dividir $x-1$ e $x+1$. Ou $p$ é um fator de $x-1$ e $q$ é um fator de $x+1$, ou vice-versa. Portanto, se calcularmos os máximos divisores comuns (MDCs) entre $N$ e tanto $x-1$ quanto $x+1$, isso nos dará os fatores $p$ e $q$. Calcular o MDC entre dois números é uma tarefa classicamente simples que pode ser realizada, por exemplo, usando o algoritmo de Euclides.

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Pode ser difícil entender cada etapa da lógica acima, então tente trabalhar com um exemplo. Use $N=15$ e $x=11$. Primeiro, verifique que $x^2 \equiv 1 \text{mod}(N)$ e $x \not\equiv \pm 1 \bmod N$. Em seguida, continue a verificar cada etapa. Por fim, calcule $\text{GCD}(11\pm1,15)$ e verifique que são os fatores de $15$.

Resposta:

$11^2 = 121$, que é $15*8 + 1$, portanto $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, que não é equivalente a $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, que não é equivalente a $0\bmod 15$. $\checkmark$

Agora, sabemos que $(x+1)(x-1) = l N$ para algum inteiro $l$. Isso é verificado quando substituímos $x$ e $N$: $(12)(10) = l 15$ quando $l = 8$. $\checkmark$

Agora, precisamos calcular $\text{GCD}(12,15)$ e $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Então, encontramos os fatores de $15$!

O algoritmo

Agora que vimos como encontrar algum inteiro $x$ tal que $x^2 \equiv 1\bmod N$ nos ajuda a fatorar $N$, podemos percorrer o algoritmo de Shor. Ele essencialmente se resume a encontrar $x$:

1. Escolha um inteiro aleatório Escolha um inteiro aleatório $a$ tal que $1 < a < N$.

• Calcule $\text{GCD}(a, N)$ de forma clássica.
  • Se $\text{GCD}(a, N) > 1$, você já encontrou um fator. Pare.
  • Caso contrário, continue.

2. Encontre a ordem $r$ de $a$ módulo $N$ Encontre o menor inteiro positivo $r$ que satisfaz $a^r \equiv 1 \pmod N$.

3. Verifique se a ordem é par

• Se $r$ for ímpar, volte ao passo 1 e escolha um novo $a$.
• Se $r$ for par, continue para o passo 4.

4. Calcule $x = a^{r/2} \bmod N$

• Verifique que $x \not\equiv 1 \pmod N$ e $x \not\equiv -1 \pmod N$.
  • Se $x \equiv \pm 1 \pmod N$, volte ao passo 1 e escolha um novo $a$.
• Caso contrário, calcule os MDCs para extrair os fatores:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Esses serão fatores não triviais de $N$.

5. Fatore recursivamente, se necessário

• Se $p$ e/ou $q$ não forem primos, aplique o algoritmo recursivamente para fatorá-los completamente.
• Quando todos os fatores forem primos, a fatoração está completa.

Com base nesse procedimento, pode não ser óbvio por que um computador quântico é necessário para completar essa tarefa. É necessário porque o passo 2, encontrar a ordem de $a$ módulo $N$, é classicamente um problema muito difícil. A complexidade escala exponencialmente com o número $N$. Mas com um computador quântico, basta usar a Estimativa Quântica de Fase para resolvê-lo. O passo 4, encontrar o MDC de dois inteiros, é na verdade algo bastante simples de fazer classicamente. Portanto, o único passo que realmente precisa do poder de um computador quântico é o passo de busca de ordem. Dizemos que o problema da fatoração "se reduz" ao problema de busca de ordem.

A parte difícil: busca de ordem

Agora, vamos ver como podemos usar um computador quântico na busca de ordem. Primeiro, vamos esclarecer o que queremos dizer com "ordem". Claro, já lhe disse o que a ordem significa matematicamente: é o primeiro inteiro não nulo $r$ tal que $a^r = 1 \pmod N.$ Mas vamos ver se conseguimos ter um pouco mais de intuição para esse conceito.

Para $N$ suficientemente pequeno, podemos simplesmente determinar a ordem calculando cada potência de $a$, tomando o módulo $N$ desse número e parando quando encontrarmos a potência $r$ que satisfaz $a^r = 1 \text{mod}(N)$. Foi isso que fizemos com nosso exemplo, $N=15$, acima. Vamos dar uma olhada em alguns gráficos dessas potências modulares para alguns valores de exemplo de $a$ e $N$:

Notou algo? São funções periódicas! E a ordem $r$ é a mesma que o período! Portanto, a busca de ordem é equivalente à busca de período.

Os computadores quânticos são muito adequados para encontrar o período de funções. Para isso, podemos usar uma sub-rotina algorítmica chamada Estimativa Quântica de Fase. Discutimos a QPE e sua relação com a Transformada Quântica de Fourier no módulo anterior. Para uma revisão detalhada, acesse o módulo de TQF ou a lição de John Watrous sobre Estimativa Quântica de Fase em seu curso de Algoritmos Quânticos. Vamos percorrer a essência do procedimento agora:

Na Estimativa Quântica de Fase (QPE), começamos com um unitário $U$ e um autoestado desse unitário $|\psi\rangle$. Em seguida, usamos a QPE para aproximar o autovalor correspondente, que, como o operador é unitário, terá a forma $e^{2\pi i \theta}$. Portanto, encontrar o autovalor é equivalente a encontrar o valor de $\theta$ na função periódica. O circuito tem a seguinte aparência:

onde o número de qubits de controle (os $m$ qubits superiores na figura acima) determina a precisão da aproximação.

No algoritmo de Shor, usamos a QPE no operador unitário $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Aqui, $|y\rangle$ denota um estado da base computacional do registrador de múltiplos qubits, onde o valor binário dos qubits corresponde ao inteiro $y$. Por exemplo, se $N=15$ e $y = 2$, então $|y\rangle$ é representado pelo estado de base de quatro qubits $|0010\rangle$, pois são necessários quatro qubits para codificar números até 15. (Se este conceito for desconhecido, consulte o módulo introdutório do Qiskit in Classrooms para uma revisão sobre codificação binária de estados quânticos.)

Agora, precisamos descobrir um autoestado desse unitário. Se começarmos no estado $|1\rangle$, podemos ver que cada aplicação sucessiva de $U$ multiplicará o estado do nosso registrador por $a \pmod N$, e após $r$ aplicações chegaremos novamente ao estado $|1\rangle$. Por exemplo, com $a = 3$ e $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Portanto, superposições dos estados nesse ciclo ($|\psi_j\rangle$) da forma:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

são todos autoestados de $M_a$. (Há mais autoestados além desses. Mas nos importamos apenas com os da forma acima.)

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Encontre um autoestado do unitário correspondente a $a=2$ e $N = 15$.

Resposta:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Portanto, a ordem $r=4$. Os autoestados em que estamos interessados serão uma superposição igual de todos os estados pelos quais passamos acima, com várias fases:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Digamos que conseguíssemos inicializar o estado do nosso qubit em um desses autoestados (spoiler — não conseguimos. Ou, pelo menos, não facilmente. Explicaremos o porquê e o que podemos fazer em vez disso em breve). Então poderíamos usar a QPE para estimar o autovalor correspondente, $\omega_j = e^{2 \pi i \theta_j}$ onde $\theta_j = \frac{j}{r}$. Então, poderemos determinar a ordem $r$ pela simples equação:

$r = \frac{j}{\theta_j}.$

Mas lembre-se, eu disse que a QPE estima $\theta_j$ — ela não nos dá um valor exato. Precisamos que a estimativa seja boa o suficiente para diferenciar entre $r$ e $r+1$. Quanto mais qubits de controle $m$ tivermos, melhor será a estimativa. Nos problemas ao final da lição, você será solicitado a determinar o $m$ mínimo necessário para fatorar um número $N$.

Agora, temos que reconciliar um problema. Toda a explicação acima de como encontrar $r$ começa com a preparação do autoestado $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Mas não sabemos como fazer isso sem já saber o que é $r$. A lógica é circular. Precisamos de uma maneira de estimar o autovalor sem inicializar o autoestado.

Em vez de começar com um autoestado de $M_a$, podemos preparar o estado inicial no estado de $n$ qubits correspondente a $|1\rangle$ em binário (ou seja, $|000...01\rangle$). Embora esse estado em si obviamente não seja um autoestado de $M_a$, ele é uma superposição sobre todos os autoestados $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Verifique que $|1\rangle$ é equivalente à superposição sobre os autoestados que você encontrou para $N=15$ e $a=2$ na questão de verificação anterior.

Resposta:

Os quatro autoestados foram:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Portanto,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Como isso nos permite encontrar a ordem $r$? Como o estado inicial é uma superposição sobre todos os autoestados da forma listada acima, então o algoritmo QPE estima simultaneamente cada um dos $\theta_k$ correspondentes a esses autoestados. Assim, a medição dos $m$ qubits de controle no final produzirá uma aproximação do valor $k/r$ onde $k \in \{0,1,2,...,r-1\}$ é um dos autovalores escolhidos aleatoriamente. Se repetirmos esse circuito algumas vezes e obtivermos algumas amostras com diferentes valores de $k$, seremos capazes de deduzir $r$ rapidamente.

Implementar no Qiskit

Como mencionamos anteriormente, o nosso hardware ainda não está no ponto de fatorar números enormes como RSA1024. Vamos apenas fatorar um número pequeno para demonstrar como o algoritmo funciona. Nessa demonstração, usaremos uma versão simplificada do código apresentado no tutorial do algoritmo de Shor. Se você quiser mais detalhes, visite o tutorial.

Vamos executar o algoritmo usando o nosso framework padrão para resolver problemas quânticos, chamado framework de padrões Qiskit. Ele consiste em quatro etapas:

1. Mapear o seu problema para um circuito quântico
2. Otimizar o circuito para ser executado em hardware quântico
3. Executar o seu circuito no computador quântico
4. Pós-processar as medições

1. Mapear

Vamos fatorar $N=15$, escolhendo $a=2$ como nosso inteiro co-primo.

Primeiro, precisamos construir o circuito que implementará a unitária de multiplicação modular, $M_a$. Essa é, na verdade, a parte mais complicada de toda a implementação, e pode ser computacionalmente bastante cara, dependendo de como é feita. Para isso, vamos trapacear um pouco: sabemos que estamos começando no estado $|1\rangle$, e a partir de uma questão de verificação anterior,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Portanto, vamos construir uma unitária que realiza as operações corretas nesses quatro estados, mas deixa todos os outros estados inalterados. Isso é uma trapaça porque estamos usando o nosso conhecimento da ordem de $2\bmod 15$ para simplificar a unitária. Se estivéssemos realmente tentando fatorar um número cujos fatores fossem desconhecidos para nós, não poderíamos fazer isso.

Teste seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e então clique no triângulo para revelar a solução.

Com seu conhecimento de como o operador $M_2$ transforma os estados acima, construa o operador a partir de uma série de portas SWAP, que trocam os estados de dois qubits. (Dica: escrever cada estado $|i\rangle$ em binário ajudará.)

Resposta:

Vamos reescrever a ação de $M_2$ sobre os estados em binário:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Cada uma dessas ações pode ser realizada com um SWAP simples. $M_2|0001\rangle$ é obtido trocando os estados do qubit $0$ e $1$. $M_2|0010\rangle$ é obtido trocando os estados do qubit $1$ e $2$. E assim por diante. Portanto, podemos decompor a matriz $M_2$ na seguinte série de portas SWAP:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Lembrando que os operadores atuam da direita para a esquerda, vamos verificar que isso tem o efeito desejado em cada um dos estados:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Agora podemos codificar o circuito equivalente a esse operador no Qiskit.

Primeiro, importamos os pacotes necessários:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Em seguida, construímos o operador $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

O algoritmo QPE usa uma porta $U$ controlada. Então, agora que temos um circuito $M_2$, precisamos torná-lo um circuito controlado-$M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Agora temos nossa porta $U$ controlada. Mas para executar o algoritmo de Estimativa de Fase Quântica, precisaremos de $U^2$ controlado, $U^4$ controlado, até $U^{2^{m-1}}$ controlado, onde $m$ é o número de qubits usados para estimar a fase. Quanto mais qubits, mais precisa será a estimativa de fase. Usaremos $m=8$ qubits de controle para o nosso procedimento de estimativa de fase. Portanto, precisamos de:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

onde o índice $k$, com $0 \le k \le m-1 = 7$, corresponde ao qubit de controle. Agora vamos calcular $a^{2^k}\bmod N$ para cada valor de $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Como $a^{2^k} \bmod N = 1$ para $k \ge 2$, todos os operadores correspondentes ($M_8$ e superiores) são equivalentes à identidade. Portanto, só precisamos construir mais uma matriz, $M_4.$

Observação: Essa simplificação só funciona aqui porque a ordem de $2 \bmod 15$ é $4$. Uma vez que $k=2$ (ou seja, $2^k = 4$), toda potência subsequente do operador é a identidade. Em geral, para números $N$ maiores ou escolhas diferentes de $a$, você não pode pular a construção das potências superiores. Essa é uma das razões pelas quais isso é considerado um exemplo simplificado: os números pequenos permitem atalhos que não funcionariam para casos maiores.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

E, como antes, tornamos isso um operador controlado-$M_4$:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Agora podemos juntar tudo para encontrar a ordem de $2\bmod 15$ com um circuito quântico, usando estimativa de fase:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Otimizar

Agora que mapeamos o nosso circuito, o próximo passo é otimizá-lo para ser executado em um computador quântico específico. Primeiro, precisamos carregar o backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Se você não tiver tempo disponível na sua conta ou quiser usar um simulador por qualquer motivo, pode executar a célula abaixo para configurar um simulador que imitará o dispositivo quântico que selecionamos acima:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Executar

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Vemos quatro picos claros em 00000000, 01000000, 10000000 e 11000000, com algumas contagens em outras sequências de bits devido ao ruído no computador quântico. Vamos ignorá-las e manter apenas as quatro dominantes impondo um limiar: somente contagens acima desse limiar são consideradas um sinal verdadeiro acima do ruído.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Pós-processar

Para o algoritmo de Shor, boa parte do algoritmo é executada classicamente. Portanto, colocaremos o restante na etapa de "pós-processamento", após obtermos as nossas medições do computador quântico. Cada uma das medições acima pode ser convertida em inteiros que, após dividirmos por $2^m$, são as nossas aproximações para $\frac{k}{r}$, onde $k$ é aleatório a cada vez.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Conclusão

Após percorrer o módulo, você pode ter desenvolvido uma nova admiração pela brilhantismo de Peter Shor ao ter criado um algoritmo tão engenhoso. Mas espera-se que você também tenha alcançado um novo nível de compreensão da sua simplicidade enganosa. Embora o algoritmo possa parecer impressionantemente (ou intimidadoramente) complexo, se você o decompuser em cada etapa lógica e percorrê-lo com calma, você também será capaz de executar o algoritmo de Shor.

Embora ainda estejamos longe de usar esse algoritmo para fatorar números como RSA1024, nossos computadores quânticos estão melhorando a cada dia, e quando um limite chamado tolerância a falhas for alcançado, algoritmos como esses logo virão a seguir. É um momento empolgante para aprender sobre computação quântica!

Problemas

Conceitos fundamentais:

• Os sistemas criptográficos modernos dependem da dificuldade clássica de fatorar inteiros grandes.
• A aritmética modular — incluindo as estruturas $\mathbb{Z}_N$ e $\mathbb{Z}_N^*$ — fornece a base matemática para o algoritmo de Shor.
• O problema de fatorar um inteiro $N$ pode ser reduzido ao problema de encontrar a ordem de um número módulo $N$.
• A busca de ordem quântica usa técnicas de estimativa de fase quântica para determinar o período da função $a^x \mod N$.
• O algoritmo de Shor consiste em um fluxo de trabalho híbrido clássico-quântico que seleciona uma base, realiza a busca de ordem quântica e então calcula classicamente os fatores a partir do resultado.

Verdadeiro/Falso:

1. V/F A eficiência do algoritmo de Shor ameaça a segurança da criptografia RSA.
2. V/F O algoritmo de Shor pode ser executado eficientemente em qualquer computador quântico moderno.
3. V/F O algoritmo de Shor usa a estimativa de fase quântica (QPE) como uma sub-rotina central.
4. V/F A parte clássica do algoritmo de Shor envolve o cálculo do máximo divisor comum (MDC).
5. V/F O algoritmo de Shor só funciona para fatorar números pares.
6. V/F Uma execução bem-sucedida do algoritmo de Shor sempre garante os fatores corretos.

Resposta curta:

1. Por que o algoritmo de Shor é considerado uma potencial ameaça futura à criptografia RSA?
2. Por que encontrar o período, ou ordem, de uma função exponencial modular é útil para fatorar um número no algoritmo de Shor?

Problemas desafio:

1. Quantos qubits de controle $m$ precisamos para um dado número $N$ que estamos tentando fatorar, a fim de obter a precisão na QPE necessária para encontrar o valor correto da ordem $r$?

2. Seguindo o procedimento que descrevemos aqui para fatorar 15, tente agora fatorar 21.