Algoritmo de Shor

Para este módulo Qiskit in Classrooms, os alunos devem ter um ambiente de Python trabalho com os seguintes pacotes instalados:

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

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

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

# 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 1990s, havia um entusiasmo crescente em torno do potencial dos computadores quânticos para resolver problemas que eram difíceis para os computadores clássicos. Alguns cientistas da computação talentosos criaram algoritmos que demonstravam o poder da computação quântica para alguns problemas específicos e artificiais, mas ninguém havia encontrado um único “aplicativo revolucionário” da computação quântica que certamente revolucionaria o campo. Isso até 1994, quando Peter Shor criou o que hoje é chamado de algoritmo de Shor para fatorar números grandes.

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

Neste módulo, exploraremos o algoritmo de Shor. Primeiro, vamos contextualizar um pouco mais o algoritmo, formalizando o problema que ele resolve e explicando sua relevância para a segurança cibernética. A seguir, apresentaremos uma introdução à matemática modular e como aplicá-la ao problema da fatoração, mostrando como a fatoração se reduz a outro problema chamado “localização de ordem” Mostraremos como a Transformada de Fourier Quântica e a Estimativa de Fase Quântica, que aprendemos no módulo anterior, entram em ação e como usá-las para resolver o problema de encontrar a ordem.

Finalmente, vamos executar o algoritmo de Shor em um computador quântico real! No entanto, tenha em mente que esse algoritmo só será realmente útil quando tivermos um computador quântico grande e tolerante a falhas, o que ainda levará alguns anos. Então, vamos apenas fatorar um número pequeno para demonstrar como o algoritmo funciona.

O problema da fatoração

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

No entanto, os computadores clássicos enfrentam dificuldades quando $N$ é ímpar e não é uma potência prima. Este é o caso tratado pelo algoritmo de Shor. 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 segurança cibernética

Muitos esquemas criptográficos foram criados com base no fato de que é difícil fatorar números grandes, incluindo um que é comumente usado hoje em dia, chamado RSA. Na RSA, uma chave pública é criada multiplicando-se dois grandes números primos para obter $N = p\cdot q$. Em seguida, qualquer pessoa pode usar essa chave pública para criptografar dados. Mas apenas alguém com a chave privada, $p$ e $q$, pode descriptografar esses dados.

Se $N$ fosse fácil fatorar, então qualquer pessoa seria capaz de determinar quais são $p$ $q$ e quebrar a criptografia. Mas não é. Este é um problema notoriamente difícil. Na verdade, 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 US$ 100.000 ter sido oferecido para sua fatoração em 1991.

Solução de Shor

Em 1994, Peter Shor percebeu que um computador quântico poderia fatorar um grande número de forma exponencialmente mais eficiente do que um computador clássico. Sua percepção baseava-se na relação entre esse problema de fatoração e a aritmética modular. Vamos fazer uma breve introdução à aritmética modular e, em seguida, veremos como podemos usar isso 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 números inteiros 0, 1, 2, etc., em algum momento, após um período $N$, a contagem recomeça. Vamos ver como isso funciona com um exemplo. Digamos que nosso período seja 5. Então, enquanto estamos contando, onde normalmente chegaríamos a 5, começamos novamente do 0:

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

Isso ocorre porque, no mundo “” modulo-5, 5 é equivalente a 0. Dizemos que $5\bmod 5 \ = 0$. Na verdade, todos os múltiplos de 5 serão equivalentes a $0\bmod 5$.

Verifique sua compreensão

Use aritmética modular para resolver o seguinte problema:

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

• Resposta

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

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

  Então, você chegaria ao seu destino às 20:00, ou 8 da noite.

$\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 estávamos contando modulo-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 em $\mathbb{Z}_N$, e o resultado de cada uma dessas operações também é um elemento em $\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 nós no algoritmo de Shor. Esse é o subconjunto de números em $\mathbb{Z}_N$ tal que o maior divisor comum entre cada elemento e $N$ é 1, portanto, cada elemento é “coprimo” a $N$. Se considerarmos o conjunto desses números juntamente com a operação de multiplicação modular, isso forma outro objeto matemático, chamado grupo. Chamamos esse grupo $\mathbb{Z}_N^*$ de. Acontece que, com $\mathbb{Z}_N^*$ (e grupos finitos em geral), se escolhermos qualquer elemento $a \in \mathbb{Z}_N^*$ e multiplicarmos repetidamente $a$ por ele mesmo, sempre obteremos o número $1$. O número mínimo de vezes que se deve multiplicar $a$ por ele mesmo para obter $1$ é chamado de ordem de $a$. Esse fato será muito importante para nossa discussão sobre como fatorar números abaixo.

Verifique sua compreensão

O que é $\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 um dos elementos 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}^*$, isso NÃO é uma tarefa fácil em geral, para valores maiores de $N$. Esse é o cerne do problema da fatoração e a razão pela qual precisamos de um computador quântico. Veremos o motivo à medida que avançarmos pelo restante do caderno.

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

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

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

Como é que encontrar nos ajuda $x$ a encontrar os fatores $p$ e $q$? Vamos agora analisar o argumento. 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$

A partir das nossas suposições iniciais, sabemos que $x \not\equiv \pm 1 \bmod N$, portanto, $N$ não divide uniformemente nem $x+1$ nem $x-1$. Assim, os dois fatores de $N$, $p$ e, $q$ devem dividir $x-1$ e $x+1$, respectivamente. Ou $p$ é um fator de $x-1$ e $q$ é um fator de $x+1$, ou vice-versa. Portanto, se calcularmos os maiores divisores comuns (MDCs) entre $N$ e ambos $x-1$ e $x+1$, isso nos dará os fatores $p$ e $q$. Calcular o MDC entre dois números é uma tarefa clássica fácil que pode ser realizada, por exemplo, usando o algoritmo de Euclides.

Verifique sua compreensão

Pode ser complicado entender cada etapa da lógica acima, então tente trabalhar com um exemplo. Use $N=15$ e $x=11$. Primeiro, verifique se $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 se eles 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 número inteiro $l$. Isso é verificado quando inserimos $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 nossos fatores de $15$!

O algoritmo

Agora que vimos como encontrar um número inteiro $x$ tal que nos $x^2 \equiv 1\bmod N$ ajuda a fatorar $N$, podemos passar pelo algoritmo de Shor. Essencialmente, resume-se a encontrar $x$ :

1. Escolha um número inteiro aleatório Escolha um número 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$ do $a$ módulo $N$ Encontre o menor número inteiro positivo $r$ que satisfaz $a^r \equiv 1 \pmod N$.

3. Verifique se o pedido está correto

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

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

• Verifique se $x \not\equiv 1 \pmod N$ e $x \not\equiv -1 \pmod N$.
  • Se $x \equiv \pm 1 \pmod N$, volte à etapa 1 e escolha um novo $a$.
• Caso contrário, calcule os gcds para extrair os fatores:

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

5. Fatorar recursivamente, se necessário

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

Com base nesse procedimento, pode não ser óbvio por que um computador quântico é necessário para realizar essa tarefa. Isso é necessário porque a etapa 2, encontrar a ordem do $a$ módulo $N$, é classicamente um problema muito difícil. A complexidade aumenta exponencialmente com o número $N$. Mas, com um computador quântico, basta usar a Estimativa de Fase Quântica para resolvê-la. O passo 4, encontrar o MDC de dois números inteiros, é na verdade algo bastante fácil de fazer de forma clássica. Portanto, a única etapa que realmente precisa do poder de um computador quântico é a etapa de localização de pedidos. Dizemos que o problema da fatoração “se reduz” ao problema de encontrar a ordem.

A parte difícil: encontrar o pedido

Agora, vamos ver como podemos usar um computador quântico para encontrar resultados. Primeiro, vamos esclarecer o que entendemos por “ordem” É claro que já expliquei o que a ordem significa matematicamente: é o primeiro número inteiro $r$ diferente de zero tal que $a^r = 1 \pmod N.$ Mas vamos ver se conseguimos entender melhor esse conceito.

Para valores suficientemente pequenos $N$, podemos simplesmente determinar a ordem calculando cada potência de $a$, obtendo 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 o nosso exemplo, $N=15$, acima. Vamos dar uma olhada em alguns gráficos dessas potências modulares para alguns valores de amostra de $a$ e $N$ :

Percebeu alguma coisa? Estas são funções periódicas! E a ordem $r$ é a mesma do período! Portanto, encontrar a ordem é equivalente a encontrar o período.

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

Na Estimativa de Fase Quântica (QPE), começamos com uma unidade $U$ e um estado próprio dessa unidade $|\psi\rangle$. Em seguida, usamos a QPE para aproximar o valor próprio correspondente, que, como o operador é unitário, terá a forma $e^{2\pi i \theta}$. Portanto, encontrar o valor próprio é 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 qubits $m$ superiores na figura acima) determina a precisão da aproximação.

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

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

Aqui, $|y\rangle$ denota um estado de base computacional do registro multi-qubit, onde o valor binário dos qubits corresponde ao número inteiro $y$. Por exemplo, se $N=15$ e $y = 2$, então $|y\rangle$ é representado pelo estado de base de quatro $|0010\rangle$ qubits, uma vez que são necessários quatro qubits para codificar números até 15. (Se este conceito não lhe for familiar, consulte o módulo introdutório Qiskit nas salas de aula para uma atualização sobre a codificação binária dos estados quânticos.)

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

Portanto, as superposições dos estados neste 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 estados próprios de $M_a$. (Existem mais estados próprios além destes. Mas só nos interessam os que têm a forma acima.)

Verifique sua compreensão

Encontre um estado próprio da unidade 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 estados próprios que nos interessam serão uma superposição igual de todos os estados que foram percorridos 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 conseguimos inicializar nosso estado qubit em um desses estados próprios (spoiler — não conseguimos). Ou, pelo menos, não facilmente. Explicaremos em breve por que e o que podemos fazer em vez disso. Então, poderíamos usar QPE para estimar o valor próprio correspondente, $\omega_j = e^{2 \pi i \theta_j}$ onde $\theta_j = \frac{j}{r}$. Assim, poderemos determinar a ordem $r$ pela equação simples:

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

Mas lembre-se, eu disse que o QPE estima$\theta_j$ — ele 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 $m$ controle tivermos, melhor será a estimativa. Nos problemas no final da lição, você será solicitado a determinar o mínimo $m$ necessário para fatorar um número $N$.

Agora, temos que resolver um problema. Todas as explicações acima sobre como encontrar $r$ começam com a preparação do estado próprio $|\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 valor próprio sem inicializar o estado próprio.

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

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

Verifique sua compreensão

Verifique se $|1\rangle$ é equivalente à superposição sobre os estados próprios que você encontrou para $N=15$ e $a=2$ na questão anterior.

• Resposta

  Os quatro estados próprios eram:

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

  Então,

  $$\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 estados próprios da forma listada acima, o algoritmo QPE estima simultaneamente cada um dos $\theta_k$ correspondentes a esses estados próprios. Portanto, a medição dos qubits $m$ de controle no final produzirá uma aproximação do valor $k/r$, onde $k \in \{0,1,2,...,r-1\}$ é um dos valores próprios escolhidos aleatoriamente. Se repetirmos esse circuito algumas vezes e obtivermos algumas amostras com valores diferentes de $k$, poderemos deduzir rapidamente $r$.

Implementar no Qiskit

Como mencionamos anteriormente, nosso hardware ainda não está em condições de processar números enormes como RSA1024. Vamos apenas fatorar um número pequeno para demonstrar como o algoritmo funciona. Para esta demonstração, usaremos uma versão simplificada do código apresentado no tutorial do algoritmo de Shor. Se desejar mais detalhes, visite o tutorial.

Executaremos o algoritmo usando nossa estrutura padrão para resolver problemas quânticos, chamada estrutura de padrões Qiskit. Isso consiste em quatro etapas:

1. Mapeando seu problema para um circuito quântico
2. Otimize o circuito para ser executado em hardware quântico
3. Execute seu circuito no computador quântico
4. Pós-processamento das medições

1. Mapa

Vamos fatorar $N=15$, selecionando $a=2$ como nosso inteiro coprimo.

Primeiro, precisamos construir o circuito que implementará a unidade de multiplicação modular. $M_a$ Essa é, na verdade, a parte mais complicada de toda a implementação e pode ser muito dispendiosa em termos computacionais, dependendo de como for feita. Para isso, vamos trapacear um pouco: sabemos que estamos começando no estado $|1\rangle$ e, a partir de uma pergunta anterior,

Portanto, construiremos uma unidade que execute as operações corretas nesses quatro estados, mas deixe todos os outros estados inalterados. Isso é trapaça, porque estamos usando nosso conhecimento da ordem de $2\bmod 15$ para simplificar a unitária. Se estivéssemos realmente tentando fatorar um número cujos fatores nos eram desconhecidos, não seríamos capazes de fazer isso.

Verifique sua compreensão

Com o seu conhecimento sobre como o $M_2$ operador 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$ nos 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 uma simples troca (SWAP). $M_2|0001\rangle$ é obtido trocando-se os estados dos qubits $0$ e $1$. $M_2|0010\rangle$ é obtido trocando-se os estados dos qubits $1$ e $2$. E assim por diante. Assim, podemos decompor a $M_2$ matriz 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 se 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, criamos o $M_2$ operador:

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)

Output:

O algoritmo QPE utiliza um portão $U$ controlado. Então, agora que temos um $M_2$ circuito, precisamos torná-lo um circuito $M_2$* controlado* :

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)

Output:

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

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)

Output:

[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 acima) 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$ (portanto, $2^k = 4$ ), cada potência subsequente do operador é a identidade. Em geral, para números maiores $N$ ou diferentes escolhas de $a$, você não pode pular a construção das potências mais altas. Essa é uma das razões pelas quais isso é considerado um exemplo simplificado : os números pequenos permitem atalhos que não funcionariam em 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)

Output:

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

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)

Output:

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)

Output:

2. Otimizar

Agora que mapeamos 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 em sua conta ou quiser usar um simulador por qualquer motivo, execute 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)

Output:

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))

Output:

Observamos quatro picos claros em 00000000, 01000000, 10000000 e 11000000, com algumas contagens em outras cadeias de bits devido ao ruído no computador quântico. Vamos ignorar esses e manter apenas os quatro dominantes, impondo um limite: apenas contagens acima desse limite 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-processamento

No algoritmo de Shor, grande parte do algoritmo é executada de forma clássica. Então, colocaremos o restante na etapa de “pós-processamento”, depois de obtermos nossas medições do computador quântico. Cada uma das medidas acima pode ser convertida em números inteiros que, após dividirmos por $2^m$, são 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} ***")

Output:

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

Depois de concluir o módulo, você poderá ficar impressionado com a genialidade de Peter Shor por ter criado um algoritmo tão inteligente. Mas espero que você também tenha alcançado um novo nível de compreensão sobre sua simplicidade enganosa. Embora o algoritmo possa parecer impressionantemente (ou intimidadoramente) complexo, se você o dividir em cada etapa lógica e analisá-lo lentamente, 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 ficando melhores a cada dia e, assim que um limite chamado tolerância a falhas for atingido, algoritmos como esses logo surgirão. É um momento emocionante para aprender sobre computação quântica!

Problemas

Conceitos críticos:

• Os sistemas criptográficos modernos dependem da dificuldade clássica de fatorar números 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 número inteiro $N$ pode ser reduzido ao problema de encontrar a ordem de um número módulo $N$.
• A localização de ordem quântica utiliza 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 localização da ordem quântica e, em seguida, 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 de forma eficiente 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 fundamental.
4. V/F A parte clássica do algoritmo de Shor envolve o cálculo do maior 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 ameaça potencial 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 desafiadores:

1. Quantos qubits de controle $m$ precisamos para um determinado número $N$ que estamos tentando fatorar para obter a precisão no 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.