{
"cells": [
{
"cell_type": "markdown",
"id": "e72c9e73-98e1-49ae-bc3c-511954eeb15c",
"metadata": {
"tags": [
"remove_cell"
]
},
"source": [
"---\n",
"title: \"Algoritmo de Shor\"\n",
"description: \"Este tutorial se concentra em demonstrar o algoritmo de Shor fatorando 15 em um computador quântico.\"\n",
"---\n",
"\n",
"{/* cspell:ignore textrm */}\n",
"\n",
"\n",
"\n",
"# Algoritmo de Shor\n",
"\n",
"*Estimativa de uso: Três segundos em um processador Eagle r3 (OBSERVAÇÃO: esta é apenas uma estimativa. Seu tempo de execução pode variar)*\n",
"\n",
"\n",
"\n",
"## Resultados do aprendizado\n",
"\n",
"Após concluir este tutorial, os usuários deverão compreender:\n",
"\n",
"* Os fundamentos matemáticos do algoritmo de Shor para a fatoração de números inteiros\n",
"* Como executar uma instância de exemplo deste algoritmo em hardware\n",
"\n",
"\n",
"\n",
"## Pré-requisitos\n",
"\n",
"Recomendamos que os usuários estejam familiarizados com os seguintes tópicos antes de seguir com este tutorial:\n",
"\n",
"* [Fundamentos dos algoritmos quânticos](/learning/courses/fundamentals-of-quantum-algorithms).\n",
"* [Estimativa de fase e fatoração](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction). Abordamos parte desse conteúdo neste tutorial.\n",
"\n",
"\n",
"\n",
"## Segundo plano\n",
"\n",
"[O algoritmo de Shor](https://epubs.siam.org/doi/abs/10.1137/S0036144598347011), desenvolvido por Peter Shor em 1994, é um algoritmo quântico inovador para a fatoração de números inteiros em tempo polinomial. Sua importância reside na capacidade de fatorar grandes números inteiros de forma exponencialmente mais rápida do que qualquer algoritmo clássico conhecido, o que representa uma ameaça à segurança de sistemas criptográficos amplamente utilizados, como o RSA, que se baseiam na dificuldade de fatorar números grandes. Ao resolver esse problema de forma eficiente em um computador quântico suficientemente potente, o algoritmo de Shor poderia revolucionar áreas como a criptografia, a segurança cibernética e a matemática computacional, destacando o poder transformador da computação quântica.\n",
"\n",
"Este tutorial se concentra na demonstração do algoritmo de Shor, fatorando 15 em um computador quântico.\n",
"\n",
"Primeiro, definimos o problema de determinação de ordem e construímos os circuitos correspondentes a partir do protocolo de estimativa de fase quântica. Em seguida, executamos os circuitos de localização de ordens em hardware real usando circuitos de profundidade mais curta que podemos transpilar. A última seção completa o algoritmo de Shor conectando o problema de determinação de ordem à fatoração de números inteiros.\n",
"\n",
"Encerramos o tutorial com uma discussão sobre outras demonstrações do algoritmo de Shor em hardware real, com foco nas implementações genéricas e naquelas adaptadas para fatorar números inteiros específicos, como 15 e 21.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "22f3a6f3-0ba5-4826-a4f3-9dcc62f51c70",
"metadata": {},
"source": [
"Observação: este tutorial se concentra mais na implementação e na demonstração dos circuitos relativos ao algoritmo de Shor. Para obter um recurso educacional aprofundado sobre o material, consulte o curso [Fundamentals of quantum algorithms (Fundamentos de algoritmos qu](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction) ânticos) do Dr. John Watrous e os artigos na seção [Referências](#references).\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "b41b8639-ff72-4cd5-8bd3-3c16c01bedc0",
"metadata": {},
"source": [
"\n",
"\n",
"### Requisitos\n",
"\n",
"Antes de iniciar este tutorial, verifique se você tem os seguintes itens instalados:\n",
"\n",
"* Qiskit SDK v2.0 ou posterior, com suporte [para visualização](/docs/api/qiskit/visualization)\n",
"* Qiskit Runtime v0.40 ou posterior (`pip install qiskit-ibm-runtime`)\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "93dcb213-ddcd-4329-8bcb-7c61fa298ee5",
"metadata": {},
"source": [
"\n",
"\n",
"### Instalação\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0860914d-cf1f-4bee-907d-3c442cd92cc6",
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import pandas as pd\n",
"from fractions import Fraction\n",
"from math import floor, gcd, log\n",
"\n",
"from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister\n",
"from qiskit.circuit.library import QFT, UnitaryGate\n",
"from qiskit.transpiler import CouplingMap, generate_preset_pass_manager\n",
"from qiskit.visualization import plot_histogram\n",
"\n",
"from qiskit_ibm_runtime import QiskitRuntimeService\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler"
]
},
{
"cell_type": "markdown",
"id": "a28eeaa5-2da0-4b6b-8877-547a86fbcd76",
"metadata": {},
"source": [
"\n",
"\n",
"## Passo 1: Mapear entradas clássicas para um problema quântico\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "c09ec908-51ba-4ea3-bc84-142e8f8002bf",
"metadata": {},
"source": [
"O algoritmo de Shor para a fatoração de números inteiros utiliza um problema intermediário conhecido como problema *de determinação de ordem*. Nesta seção, demonstramos como resolver o problema de determinação de ordem usando *a estimativa de fase quântica*.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "e1aa8e70-a760-43ca-bcf2-def23d49ba36",
"metadata": {},
"source": [
"\n",
"\n",
"### Problema de estimativa de fase\n",
"\n",
"No problema de estimativa de fase, recebemos um estado quântico $\\ket{\\psi}$ de $n$ qubits, juntamente com um circuito quântico unitário que atua em $n$ qubits. Prometemos que $\\ket{\\psi}$ é um vetor próprio da matriz unitária $U$ que descreve a ação do circuito, e nosso objetivo é calcular ou aproximar o valor próprio $\\lambda = e^{2 \\pi i \\theta}$ ao qual $\\ket{\\psi}$ corresponde. Em outras palavras, o circuito deve produzir uma aproximação para o número $\\theta \\in [0, 1)$ satisfazendo $U \\ket{\\psi}= e^{2 \\pi i \\theta} \\ket{\\psi}.$ O objetivo do circuito de estimativa de fase é aproximar $\\theta$ em $m$ bits. Em termos matemáticos, gostaríamos de encontrar $y$ de modo que $\\theta \\approx y / 2^m$, onde $y \\in {0, 1, 2, \\dots, 2^{m-1}}$. A imagem a seguir mostra o circuito quântico que estima $y$ em $m$ bits fazendo uma medição em $m$ qubits.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "7ae92a5f-55b4-4597-be58-fe47b450dc39",
"metadata": {},
"source": [
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "c527ff28-8038-44fc-8d62-1c9dda2b600e",
"metadata": {},
"source": [
"No circuito acima, os qubits superiores $m$ são iniciados no estado $\\ket{0^m}$ e os qubits inferiores $n$ são iniciados em $\\ket{\\psi}$, que promete ser um vetor próprio de $U$. O primeiro ingrediente do circuito de estimativa de fase são as operações unitárias controladas, responsáveis por realizar um *retorno de fase* para o qubit de controle correspondente. Essas unidades controladas são exponenciadas de acordo com a posição do qubit de controle, variando do bit menos significativo ao bit mais significativo. Como $\\ket{\\psi}$ é um vetor próprio de $U$, o estado dos qubits inferiores de $n$ não é afetado por essa operação, mas as informações de fase do valor próprio se propagam para os qubits superiores de $m$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "40b4a6e3-6f46-4971-8054-4a7ae9dd535e",
"metadata": {},
"source": [
"Acontece que, após a operação de retrocesso de fase por meio de unitários controlados, todos os estados possíveis dos $m$ qubits superiores são ortonormais entre si para cada vetor próprio $\\ket{\\psi}$ do unitário $U$. Portanto, esses estados são perfeitamente distinguíveis, e podemos girar a base que eles formam de volta para a base computacional para fazer uma medição. Uma análise matemática mostra que essa matriz de rotação corresponde à transformada quântica inversa de Fourier (QFT) no espaço de Hilbert $2^m$ -dimensional. A intuição por trás disso é que a estrutura periódica dos operadores de exponenciação modular está codificada no estado quântico, e o QFT converte essa periodicidade em picos mensuráveis no domínio da frequência.\n",
"\n",
"Para uma compreensão mais aprofundada do motivo pelo qual o circuito QFT é empregado no algoritmo de Shor, recomendamos que o leitor consulte o curso [Fundamentos de algoritmos quânticos](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction).\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "acfa31d3-7980-42ad-b418-77a24d16513a",
"metadata": {},
"source": [
"Agora estamos prontos para usar o circuito de estimativa de fase para encontrar a ordem.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "535674d6-cc8a-45f5-9fc7-f5fd3053f4c4",
"metadata": {},
"source": [
"\n",
"\n",
"### Problema na localização do pedido\n",
"\n",
"Para definir o problema de determinação de ordem, começamos com alguns conceitos da teoria dos números. Primeiro, para qualquer número inteiro positivo $N$, defina o conjunto $\\mathbb{Z}_N$ como $\\mathbb{Z}_N = \\{0, 1, 2, \\dots, N-1\\}.$ Todas as operações aritméticas em $\\mathbb{Z}_N$ são realizadas no módulo $N$. Em particular, todos os elementos $a \\in \\mathbb{Z}_n$ que são coprimos de $N$ são especiais e constituem $\\mathbb{Z}^*_N$ como $\\mathbb{Z}^*_N = \\{ a \\in \\mathbb{Z}_N : \\mathrm{gcd}(a, N)=1 \\}.$ Para um elemento $a \\in \\mathbb{Z}^*_N$, o menor número inteiro positivo $r$ tal que $a^r \\equiv 1 \\; (\\mathrm{mod} \\; N)$ é definido como a *ordem* de $a$ módulo $N$. Como veremos mais adiante, encontrar a ordem de um $a \\in \\mathbb{Z}^*_N$ nos permitirá fatorar $N$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "6de4cbed-6591-40da-a994-2ff139c9f064",
"metadata": {},
"source": [
"Para construir o circuito de determinação de ordem a partir do circuito de estimativa de fase, precisamos de duas considerações. Primeiro, precisamos definir o unitário $U$ que nos permitirá encontrar a ordem $r$ e, segundo, precisamos definir um vetor próprio $\\ket{\\psi}$ de $U$ para preparar o estado inicial do circuito de estimativa de fase.\n",
"\n",
"Para conectar o problema de determinação de ordem à estimativa de fase, consideramos a operação definida em um sistema cujos estados clássicos correspondem a $\\mathbb{Z}_N$, em que multiplicamos por um elemento fixo $a \\in \\mathbb{Z}^*_N$. Em particular, definimos esse operador de multiplicação $M_a$ de modo que $M_a \\ket{x} = \\ket{ax \\; (\\mathrm{mod} \\; N)}$ para cada $x \\in \\mathbb{Z}_N$. Observe que está implícito que estamos tomando o produto módulo $N$ dentro do ket no lado direito da equação. Uma análise matemática mostra que $M_a$ é um operador unitário. Além disso, verifica-se que $M_a$ tem pares de vetores e valores próprios que nos permitem conectar a ordem $r$ de $a$ ao problema de estimativa de fase. Especificamente, para qualquer opção de $j \\in \\{0, \\dots, r-1\\}$, temos que $\\ket{\\psi_j} = \\frac{1}{\\sqrt{r}} \\sum^{r-1}_{k=0} \\omega^{-jk}_{r} \\ket{a^k}$ é um vetor próprio de $M_a$ cujo valor próprio correspondente é $\\omega^{j}_{r}$, onde $\\omega^{j}_{r} = e^{2 \\pi i \\frac{j}{r}}.$\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "57942d8d-b2fc-4863-bfdd-f99aa941e0c0",
"metadata": {},
"source": [
"Por observação, vemos que um par de autovetor/valor próprio conveniente é o estado $\\ket{\\psi_1}$ com $\\omega^{1}_{r} = e^{2 \\pi i \\frac{1}{r}}$. Portanto, se pudéssemos encontrar o vetor próprio $\\ket{\\psi_1}$, poderíamos estimar a fase $\\theta=1/r$ com nosso circuito quântico e, portanto, obter uma estimativa da ordem $r$. Entretanto, não é fácil fazer isso, e precisamos considerar uma alternativa.\n",
"\n",
"Vamos considerar o resultado do circuito se prepararmos o estado computacional $\\ket{1}$ como o estado inicial. Esse não é um estado próprio de $M_a$, mas é a superposição uniforme dos estados próprios que acabamos de descrever acima. Em outras palavras, a relação a seguir é válida. $\\ket{1} = \\frac{1}{\\sqrt{r}} \\sum^{r-1}_{k=0} \\ket{\\psi_k}$ A implicação da equação acima é que, se definirmos o estado inicial como $\\ket{1}$, obteremos exatamente o mesmo resultado de medição como se tivéssemos escolhido $k \\in \\{ 0, \\dots, r-1\\}$ uniformemente de forma aleatória e usado $\\ket{\\psi_k}$ como um vetor próprio no circuito de estimativa de fase. Em outras palavras, uma medição dos $m$ qubits superiores produz uma aproximação $y / 2^m$ do valor $k / r$ em que $k \\in \\{ 0, \\dots, r-1\\}$ é escolhido uniformemente de forma aleatória. Isso nos permite aprender $r$ com um alto grau de confiança após várias execuções independentes, que era o nosso objetivo.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "c037fd9d-2ad6-4258-a11d-bd91944e7f01",
"metadata": {},
"source": [
"\n",
"\n",
"### Operadores de exponenciação modular\n",
"\n",
"Até agora, vinculamos o problema de estimativa de fase ao problema de determinação de ordem definindo $U = M_a$ e $\\ket{\\psi} = \\ket{1}$ em nosso circuito quântico. Portanto, o último ingrediente restante é encontrar uma maneira eficiente de definir exponenciais modulares de $M_a$ como $M_a^k$ para $k = 1, 2, 4, \\dots, 2^{m-1}$. Para realizar esse cálculo, descobrimos que, 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, em vez disso, calculando $b = a^k \\; \\mathrm{mod} \\; N$ e, em seguida, usando o circuito para $M_b$. Como precisamos apenas das potências que são potências de 2, podemos fazer isso de forma classicamente eficiente usando o quadrado iterativo.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "09d93ee7-ab42-43a8-a44f-ad303c9407c7",
"metadata": {},
"source": [
"\n",
"\n",
"## Etapa 2: Otimizar o problema para execução em hardware quântico\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "80d39ec2-715f-4014-9dbc-37db001528b1",
"metadata": {},
"source": [
"\n",
"\n",
"### Exemplo específico com $N = 15$ e $a=2$\n",
"\n",
"Podemos fazer uma pausa aqui para discutir um exemplo específico e construir o circuito de determinação de ordem para $N=15$. Observe que os possíveis $a \\in \\mathbb{Z}_N^*$ não triviais para $N=15$ são $a \\in \\{2, 4, 7, 8, 11, 13, 14 \\}$. Para este exemplo, escolhemos $a=2$. Construiremos o operador $M_2$ e os operadores de exponenciação modular $M_2^k$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "5fcd0c79-0c62-42f1-b6fa-c0f4c58e1994",
"metadata": {},
"source": [
"A ação de $M_2$ nos estados da base computacional é a seguinte. $M_2 \\ket{0} = \\ket{0} \\quad M_2 \\ket{5} = \\ket{10} \\quad M_2 \\ket{10} = \\ket{5}$ $M_2 \\ket{1} = \\ket{2} \\quad M_2 \\ket{6} = \\ket{12} \\quad M_2 \\ket{11} = \\ket{7}$ $M_2 \\ket{2} = \\ket{4} \\quad M_2 \\ket{7} = \\ket{14} \\quad M_2 \\ket{12} = \\ket{9}$ $M_2 \\ket{3} = \\ket{6} \\quad M_2 \\ket{8} = \\ket{1} \\quad M_2 \\ket{13} = \\ket{11}$ $M_2 \\ket{4} = \\ket{8} \\quad M_2 \\ket{9} = \\ket{3} \\quad M_2 \\ket{14} = \\ket{13}$ Por observação, podemos ver que os estados da base são embaralhados, portanto, temos uma matriz de permutação. Podemos construir essa operação em quatro qubits com portas de troca. A seguir, construímos as operações $M_2$ e $M_2$ controladas.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "ec5d416b-7fc9-43f3-b291-e0edc8ad195f",
"metadata": {},
"outputs": [],
"source": [
"def M2mod15():\n",
" \"\"\"\n",
" M2 (mod 15)\n",
" \"\"\"\n",
" b = 2\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(2, 3)\n",
" U.swap(1, 2)\n",
" U.swap(0, 1)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
"\n",
" return U"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "0a8885f1-91d4-40bd-912d-dc5eea05f5bd",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the M2 operator\n",
"M2 = M2mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(4)\n",
"circ.compose(M2, inplace=True)\n",
"circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "d0ae7456-053a-4389-8653-a1c9c8ff757c",
"metadata": {},
"outputs": [],
"source": [
"def controlled_M2mod15():\n",
" \"\"\"\n",
" Controlled M2 (mod 15)\n",
" \"\"\"\n",
" b = 2\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(2, 3)\n",
" U.swap(1, 2)\n",
" U.swap(0, 1)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
" c_U = U.control()\n",
"\n",
" return c_U"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "ab7fe331-2f9e-47ca-ba3b-f5d67992062a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the controlled-M2 operator\n",
"controlled_M2 = controlled_M2mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(5)\n",
"circ.compose(controlled_M2, inplace=True)\n",
"circ.decompose(reps=1).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "139b6d31-33d0-49ea-82b1-5bb50b5b6c9e",
"metadata": {},
"source": [
"As portas que atuam em mais de dois qubits serão decompostas em portas de dois qubits.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "13b4841d-a4ac-46bd-b4d0-d111b3017189",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "e361cc09-e357-4ba7-950b-9fa83898fa88",
"metadata": {},
"source": [
"Agora precisamos construir os operadores de exponenciação modular. Para obter precisão suficiente na estimativa de fase, usaremos oito qubits para a medição da estimativa. Portanto, precisamos construir $M_b$ com $b = a^{2^k} \\; (\\mathrm{mod} \\; N)$ para cada $k = 0, 1, \\dots, 7$.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "72d989c8-ef62-44d7-887c-5fa13db818e9",
"metadata": {},
"outputs": [],
"source": [
"def a2kmodN(a, k, N):\n",
" \"\"\"Compute a^{2^k} (mod N) by repeated squaring\"\"\"\n",
" for _ in range(k):\n",
" a = int(np.mod(a**2, N))\n",
" return a"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "69fa8c9f-4107-4339-96db-c6f950a71261",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 4, 1, 1, 1, 1, 1, 1]\n"
]
}
],
"source": [
"k_list = range(8)\n",
"b_list = [a2kmodN(2, k, 15) for k in k_list]\n",
"\n",
"print(b_list)"
]
},
{
"cell_type": "markdown",
"id": "e28ed7e5-f7ca-4b7b-b875-f14c5229588c",
"metadata": {},
"source": [
"Como podemos ver na lista de valores de $b$, além de $M_2$ que construímos anteriormente, também precisamos construir $M_4$ e $M_1$. Observe que o $M_1$ atua trivialmente nos estados da base computacional, portanto, é simplesmente o operador de identidade.\n",
"\n",
"$M_4$ atua sobre os estados da base computacional da seguinte forma. $M_4 \\ket{0} = \\ket{0} \\quad M_4 \\ket{5} = \\ket{5} \\quad M_4 \\ket{10} = \\ket{10}$ $M_4 \\ket{1} = \\ket{4} \\quad M_4 \\ket{6} = \\ket{9} \\quad M_4 \\ket{11} = \\ket{14}$ $M_4 \\ket{2} = \\ket{8} \\quad M_4 \\ket{7} = \\ket{13} \\quad M_4 \\ket{12} = \\ket{3}$ $M_4 \\ket{3} = \\ket{12} \\quad M_4 \\ket{8} = \\ket{2} \\quad M_4 \\ket{13} = \\ket{7}$ $M_4 \\ket{4} = \\ket{1} \\quad M_4 \\ket{9} = \\ket{6} \\quad M_4 \\ket{14} = \\ket{11}$\n",
"\n",
"Portanto, essa permutação pode ser construída com a seguinte operação de troca.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "4f3a5fe4-5449-4869-ae94-6fdefd6765f0",
"metadata": {},
"outputs": [],
"source": [
"def M4mod15():\n",
" \"\"\"\n",
" M4 (mod 15)\n",
" \"\"\"\n",
" b = 4\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(1, 3)\n",
" U.swap(0, 2)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
"\n",
" return U"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "be041e3d-28b1-453e-983e-184c2366aeb9",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the M4 operator\n",
"M4 = M4mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(4)\n",
"circ.compose(M4, inplace=True)\n",
"circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "0efb7000-7d13-4b73-95d4-f9f747ec5119",
"metadata": {},
"outputs": [],
"source": [
"def controlled_M4mod15():\n",
" \"\"\"\n",
" Controlled M4 (mod 15)\n",
" \"\"\"\n",
" b = 4\n",
" U = QuantumCircuit(4)\n",
"\n",
" U.swap(1, 3)\n",
" U.swap(0, 2)\n",
"\n",
" U = U.to_gate()\n",
" U.name = f\"M_{b}\"\n",
" c_U = U.control()\n",
"\n",
" return c_U"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "8d943b00-a502-4157-8a0d-13fb1f55e705",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the controlled-M4 operator\n",
"controlled_M4 = controlled_M4mod15()\n",
"\n",
"# Add it to a circuit and plot\n",
"circ = QuantumCircuit(5)\n",
"circ.compose(controlled_M4, inplace=True)\n",
"circ.decompose(reps=1).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "7d2a4f30-afb1-49fc-abbb-b9070b58fe8d",
"metadata": {},
"source": [
"As portas que atuam em mais de dois qubits serão decompostas em portas de dois qubits.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "68399eef-5e55-4c95-a8a4-c8efaebd34b9",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"circ.decompose(reps=2).draw(output=\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "1f12fb24-257b-4b12-b7c5-e01b975e3216",
"metadata": {},
"source": [
"Vimos que os operadores $M_b$ para um determinado $b \\in \\mathbb{Z}^*_N$ são operações de permutação. Devido ao tamanho relativamente pequeno do problema de permutação que temos aqui, já que o $N=15$ requer apenas quatro qubits, conseguimos sintetizar essas operações diretamente com as portas do `SWAP` por inspeção. Em geral, essa pode não ser uma abordagem dimensionável. Em vez disso, talvez seja necessário construir a matriz de permutação explicitamente e usar a classe `UnitaryGate` e os métodos de transpilação do Qiskit para sintetizar essa matriz de permutação. No entanto, isso pode resultar em circuitos significativamente mais profundos. A seguir é fornecido um exemplo.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "33a328b8-11d8-4b0c-a277-5d76b2c07c5e",
"metadata": {},
"outputs": [],
"source": [
"def mod_mult_gate(b, N):\n",
" \"\"\"\n",
" Modular multiplication gate from permutation matrix.\n",
" \"\"\"\n",
" if gcd(b, N) > 1:\n",
" print(f\"Error: gcd({b},{N}) > 1\")\n",
" else:\n",
" n = floor(log(N - 1, 2)) + 1\n",
" U = np.full((2**n, 2**n), 0)\n",
" for x in range(N):\n",
" U[b * x % N][x] = 1\n",
" for x in range(N, 2**n):\n",
" U[x][x] = 1\n",
" G = UnitaryGate(U)\n",
" G.name = f\"M_{b}\"\n",
" return G"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "c184f6dd-9f80-4487-ac0b-0dd94170b0f0",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"qubits: 4\n",
"2q-depth: 94\n",
"2q-size: 96\n",
"Operator counts: OrderedDict({'cx': 45, 'swap': 32, 'u': 24, 'u1': 7, 'u3': 4, 'unitary': 3, 'circuit-335': 1, 'circuit-338': 1, 'circuit-341': 1, 'circuit-344': 1, 'circuit-347': 1, 'circuit-350': 1, 'circuit-353': 1, 'circuit-356': 1, 'circuit-359': 1, 'circuit-362': 1, 'circuit-365': 1, 'circuit-368': 1, 'circuit-371': 1, 'circuit-374': 1, 'circuit-377': 1, 'circuit-380': 1})\n"
]
},
{
"data": {
"text/plain": [
""
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Let's build M2 using the permutation matrix definition\n",
"M2_other = mod_mult_gate(2, 15)\n",
"\n",
"# Add it to a circuit\n",
"circ = QuantumCircuit(4)\n",
"circ.compose(M2_other, inplace=True)\n",
"circ = circ.decompose()\n",
"\n",
"# Transpile the circuit and get the depth\n",
"coupling_map = CouplingMap.from_line(4)\n",
"pm = generate_preset_pass_manager(coupling_map=coupling_map)\n",
"transpiled_circ = pm.run(circ)\n",
"\n",
"print(f\"qubits: {circ.num_qubits}\")\n",
"print(\n",
" f\"2q-depth: {transpiled_circ.depth(lambda x: x.operation.num_qubits==2)}\"\n",
")\n",
"print(f\"2q-size: {transpiled_circ.size(lambda x: x.operation.num_qubits==2)}\")\n",
"print(f\"Operator counts: {transpiled_circ.count_ops()}\")\n",
"transpiled_circ.decompose().draw(\n",
" output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False\n",
")"
]
},
{
"cell_type": "markdown",
"id": "fe8caaf6-4bb6-4d27-8177-71f1b530556d",
"metadata": {},
"source": [
"Vamos comparar essas contagens com a profundidade do circuito compilado de nossa implementação manual da porta $M_2$.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "0235c931-0adb-4972-9fce-32a0341822bf",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"qubits: 4\n",
"2q-depth: 9\n",
"2q-size: 9\n",
"Operator counts: OrderedDict({'cx': 9})\n"
]
},
{
"data": {
"text/plain": [
""
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the M2 operator from our manual construction\n",
"M2 = M2mod15()\n",
"\n",
"# Add it to a circuit\n",
"circ = QuantumCircuit(4)\n",
"circ.compose(M2, inplace=True)\n",
"circ = circ.decompose(reps=3)\n",
"\n",
"# Transpile the circuit and get the depth\n",
"coupling_map = CouplingMap.from_line(4)\n",
"pm = generate_preset_pass_manager(coupling_map=coupling_map)\n",
"transpiled_circ = pm.run(circ)\n",
"\n",
"print(f\"qubits: {circ.num_qubits}\")\n",
"print(\n",
" f\"2q-depth: {transpiled_circ.depth(lambda x: x.operation.num_qubits==2)}\"\n",
")\n",
"print(f\"2q-size: {transpiled_circ.size(lambda x: x.operation.num_qubits==2)}\")\n",
"print(f\"Operator counts: {transpiled_circ.count_ops()}\")\n",
"transpiled_circ.draw(\n",
" output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False\n",
")"
]
},
{
"cell_type": "markdown",
"id": "c3f0f349-a26c-4176-aa9d-407e17184b91",
"metadata": {},
"source": [
"Como podemos ver, a abordagem da matriz de permutação resultou em um circuito significativamente profundo, mesmo para uma única porta $M_2$, em comparação com nossa implementação manual. Portanto, continuaremos com nossa implementação anterior das operações do $M_b$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "0dafd632-797b-402c-a88a-821a62c7265a",
"metadata": {},
"source": [
"Agora, estamos prontos para construir o circuito de determinação de ordem completa usando nossos operadores de exponenciação modular controlada definidos anteriormente. No código a seguir, também importamos o [circuito QFT](/docs/api/qiskit/qiskit.circuit.library.QFT) da biblioteca Qiskit Circuit, que usa portas Hadamard em cada qubit, uma série de portas controlled-U1 (ou Z, dependendo da fase) e uma camada de portas de troca.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "0e854aed-c11b-494c-8c80-adeb8eb0e8fe",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Order finding problem for N = 15 with a = 2\n",
"N = 15\n",
"a = 2\n",
"\n",
"# Number of qubits\n",
"num_target = floor(log(N - 1, 2)) + 1 # for modular exponentiation operators\n",
"num_control = 2 * num_target # for enough precision of estimation\n",
"\n",
"# List of M_b operators in order\n",
"k_list = range(num_control)\n",
"b_list = [a2kmodN(2, k, 15) for k in k_list]\n",
"\n",
"# Initialize the circuit\n",
"control = QuantumRegister(num_control, name=\"C\")\n",
"target = QuantumRegister(num_target, name=\"T\")\n",
"output = ClassicalRegister(num_control, name=\"out\")\n",
"circuit = QuantumCircuit(control, target, output)\n",
"\n",
"# Initialize the target register to the state |1>\n",
"circuit.x(num_control)\n",
"\n",
"# Add the Hadamard gates and controlled versions of the\n",
"# multiplication gates\n",
"for k, qubit in enumerate(control):\n",
" circuit.h(k)\n",
" b = b_list[k]\n",
" if b == 2:\n",
" circuit.compose(\n",
" M2mod15().control(), qubits=[qubit] + list(target), inplace=True\n",
" )\n",
" elif b == 4:\n",
" circuit.compose(\n",
" M4mod15().control(), qubits=[qubit] + list(target), inplace=True\n",
" )\n",
" else:\n",
" continue # M1 is the identity operator\n",
"\n",
"# Apply the inverse QFT to the control register\n",
"circuit.compose(QFT(num_control, inverse=True), qubits=control, inplace=True)\n",
"\n",
"# Measure the control register\n",
"circuit.measure(control, output)\n",
"\n",
"circuit.draw(\"mpl\", fold=-1)"
]
},
{
"cell_type": "markdown",
"id": "78cf31ef-b2e7-4256-996a-5f89500efb52",
"metadata": {},
"source": [
"Observe que omitimos as operações de exponenciação modular controlada dos qubits de controle restantes porque $M_1$ é o operador de identidade.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "792a5cb7-2ac0-4964-b747-2780193a0401",
"metadata": {},
"source": [
"Observe que, mais adiante neste tutorial, executaremos esse circuito no backend `ibm_marrakesh` . Para isso, transpilamos o circuito de acordo com esse backend específico e informamos a profundidade do circuito e a contagem de portas.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "95925dd5-7ba9-4746-b96e-ba50400fa5ac",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2q-depth: 187\n",
"2q-size: 260\n",
"Operator counts: OrderedDict({'sx': 521, 'rz': 354, 'cz': 260, 'measure': 8, 'x': 4})\n"
]
},
{
"data": {
"text/plain": [
""
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"service = QiskitRuntimeService()\n",
"backend = service.backend(\"ibm_marrakesh\")\n",
"pm = generate_preset_pass_manager(optimization_level=2, backend=backend)\n",
"\n",
"transpiled_circuit = pm.run(circuit)\n",
"\n",
"print(\n",
" f\"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}\"\n",
")\n",
"print(\n",
" f\"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}\"\n",
")\n",
"print(f\"Operator counts: {transpiled_circuit.count_ops()}\")\n",
"transpiled_circuit.draw(\n",
" output=\"mpl\", fold=-1, style=\"clifford\", idle_wires=False\n",
")"
]
},
{
"cell_type": "markdown",
"id": "f96a2a7e-0363-49d6-bc21-f0f207a84610",
"metadata": {},
"source": [
"\n",
"\n",
"## Passo 3: Execute usando Qiskit primitives\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "a3fd5248-11f2-40b6-857a-6efc25e31bdb",
"metadata": {},
"source": [
"Primeiro, discutimos o que teoricamente obteríamos se executássemos esse circuito em um simulador ideal. Abaixo, temos um conjunto de resultados de simulação do circuito acima usando 1024 fotos. Como podemos ver, obtemos uma distribuição aproximadamente uniforme em quatro cadeias de bits sobre os qubits de controle.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "c8720362-684f-4114-8abb-83d71d21c0df",
"metadata": {},
"outputs": [],
"source": [
"# Obtained from the simulator\n",
"counts = {\"00000000\": 264, \"01000000\": 268, \"10000000\": 249, \"11000000\": 243}"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "0d6d2702-02e4-47de-8f7e-0b256657ef0f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plot_histogram(counts)"
]
},
{
"cell_type": "markdown",
"id": "5ddd6952-fb4d-447c-8781-968ca5bb88a3",
"metadata": {},
"source": [
"Ao medir os qubits de controle, obtemos uma estimativa de fase de oito bits do operador $M_a$. Podemos converter essa representação binária em decimal para encontrar a fase medida. Como podemos ver no histograma acima, quatro cadeias de bits diferentes foram medidas, e cada uma delas corresponde a um valor de fase, como segue.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "59ae21fc-e3d0-48e3-8cc6-dbce59c747ca",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Register Output Phase\n",
"0 00000000(bin) = 0(dec) 0/256 = 0.00\n",
"1 01000000(bin) = 64(dec) 64/256 = 0.25\n",
"2 10000000(bin) = 128(dec) 128/256 = 0.50\n",
"3 11000000(bin) = 192(dec) 192/256 = 0.75\n"
]
}
],
"source": [
"# Rows to be displayed in table\n",
"rows = []\n",
"# Corresponding phase of each bitstring\n",
"measured_phases = []\n",
"\n",
"for output in counts:\n",
" decimal = int(output, 2) # Convert bitstring to decimal\n",
" phase = decimal / (2**num_control) # Find corresponding eigenvalue\n",
" measured_phases.append(phase)\n",
" # Add these values to the rows in our table:\n",
" rows.append(\n",
" [\n",
" f\"{output}(bin) = {decimal:>3}(dec)\",\n",
" f\"{decimal}/{2 ** num_control} = {phase:.2f}\",\n",
" ]\n",
" )\n",
"\n",
"# Print the rows in a table\n",
"headers = [\"Register Output\", \"Phase\"]\n",
"df = pd.DataFrame(rows, columns=headers)\n",
"print(df)"
]
},
{
"cell_type": "markdown",
"id": "f0ca65bb-abb4-4f4b-bc32-4749f36e5780",
"metadata": {},
"source": [
"Lembre-se de que qualquer fase medida corresponde a $\\theta = k / r$, em que $k$ é amostrado uniformemente de forma aleatória a partir de $\\{0, 1, \\dots, r-1 \\}$. Portanto, podemos usar o algoritmo de frações contínuas para tentar encontrar $k$ e a ordem $r$. Python tem essa funcionalidade incorporada. Podemos usar o módulo `fractions` para transformar um float em um objeto `Fraction` , por exemplo:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "999f04bc-f912-465f-9cba-90d08bda3758",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(5998794703657501, 9007199254740992)"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Fraction(0.666)"
]
},
{
"cell_type": "markdown",
"id": "c5452b79-967f-4fe9-86d7-f9797987a8b5",
"metadata": {},
"source": [
"Como isso fornece frações que retornam exatamente o resultado (nesse caso, `0.6660000...`), isso pode gerar resultados desagradáveis como o acima. Podemos usar o método `.limit_denominator()` para obter a fração que mais se assemelha ao nosso float, com um denominador abaixo de um determinado valor:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "1352aa9e-7c98-4862-8ac6-8d17fce61f3d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Fraction(2, 3)"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get fraction that most closely resembles 0.666\n",
"# with denominator < 15\n",
"Fraction(0.666).limit_denominator(15)"
]
},
{
"cell_type": "markdown",
"id": "ab1ce9d5-7a24-4717-a94b-576f8c940ec2",
"metadata": {},
"source": [
"Isso é muito mais agradável. A ordem (r) deve ser menor que N, portanto, definiremos o denominador máximo como sendo `15`:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "6c20bff2-29b7-45ea-b1ed-e802e0d1a0f9",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" Phase Fraction Guess for r\n",
"0 0.00 0/1 1\n",
"1 0.25 1/4 4\n",
"2 0.50 1/2 2\n",
"3 0.75 3/4 4\n"
]
}
],
"source": [
"# Rows to be displayed in a table\n",
"rows = []\n",
"\n",
"for phase in measured_phases:\n",
" frac = Fraction(phase).limit_denominator(15)\n",
" rows.append(\n",
" [phase, f\"{frac.numerator}/{frac.denominator}\", frac.denominator]\n",
" )\n",
"\n",
"# Print the rows in a table\n",
"headers = [\"Phase\", \"Fraction\", \"Guess for r\"]\n",
"df = pd.DataFrame(rows, columns=headers)\n",
"print(df)"
]
},
{
"cell_type": "markdown",
"id": "7590599a-bb21-4d9c-8a78-2ff406acc4af",
"metadata": {},
"source": [
"Podemos ver que dois dos valores próprios medidos nos forneceram o resultado correto: $r=4$, e podemos ver que o algoritmo de Shor para encontrar a ordem tem uma chance de falhar. Esses resultados ruins ocorrem porque $k = 0$, ou porque $k$ e $r$ não são coprimos - e, em vez de $r$, recebemos um fator de $r$. A solução mais fácil para isso é simplesmente repetir o experimento até obter um resultado satisfatório para $r$.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "174b446c-ca09-4816-8983-33f61eaecfa6",
"metadata": {},
"source": [
"Até agora, implementamos o problema de localização de ordem para $N=15$ com $a=2$ usando o circuito de estimativa de fase em um simulador. A última etapa do algoritmo de Shor será relacionar o problema de determinação de ordem ao problema de fatoração de números inteiros. Essa última parte do algoritmo é puramente clássica e pode ser resolvida em um computador clássico após as medições de fase terem sido obtidas em um computador quântico. Portanto, adiamos a última parte do algoritmo para depois de demonstrarmos como podemos executar o circuito de localização de ordens em um hardware real.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "7c826de7-0caa-4337-826e-3e81024ce125",
"metadata": {},
"source": [
"\n",
"\n",
"### Execução de hardware\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "a8d6d6a9-9494-4733-89a2-790ac8adf929",
"metadata": {},
"source": [
"Agora podemos executar o circuito de localização de ordens que transpilamos anteriormente para `ibm_marrakesh`. Aqui, recorremos ao [desacoplamento dinâmico](/docs/guides/error-mitigation-and-suppression-techniques#dynamical-decoupling) (DD) para supressão de erros e ao [giro de porta](/docs/guides/error-mitigation-and-suppression-techniques#pauli-twirling) para fins de atenuação de erros. O DD envolve a aplicação de sequências de pulsos de controle precisamente cronometrados a um dispositivo quântico, reduzindo efetivamente a média das interações ambientais indesejadas e da decoerência. O giro de porta, por outro lado, randomiza portas quânticas específicas para transformar erros coerentes em erros de Pauli, que se acumulam linearmente em vez de quadraticamente. Ambas as técnicas são frequentemente combinadas para aumentar a coerência e a fidelidade dos cálculos quânticos.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "af61f1de-be24-4fc6-b2bb-af6845163c3c",
"metadata": {},
"outputs": [],
"source": [
"# Sampler primitive to obtain the probability distribution\n",
"sampler = Sampler(backend)\n",
"\n",
"# Turn on dynamical decoupling with sequence XpXm\n",
"sampler.options.dynamical_decoupling.enable = True\n",
"sampler.options.dynamical_decoupling.sequence_type = \"XpXm\"\n",
"# Enable gate twirling\n",
"sampler.options.twirling.enable_gates = True\n",
"\n",
"# Assign tags before executing\n",
"sampler.options.environment.job_tags = [\"TUT_SA\"]\n",
"\n",
"pub = transpiled_circuit\n",
"job = sampler.run([pub], shots=1024)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"id": "e5f53a20-40a4-440f-a6ea-349c20efbc95",
"metadata": {},
"outputs": [],
"source": [
"result = job.result()[0]\n",
"counts = result.data[\"out\"].get_counts()"
]
},
{
"cell_type": "code",
"execution_count": 26,
"id": "559d7030-1f67-44e8-afa7-6afc7a334677",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"plot_histogram(counts, figsize=(35, 5))"
]
},
{
"cell_type": "markdown",
"id": "3614aa7e-0410-4e9e-b33a-3caf407e086a",
"metadata": {},
"source": [
"Como podemos ver, obtivemos as mesmas cadeias de bits com contagens mais altas. Como o hardware quântico tem ruído, há algum vazamento para outras cadeias de bits, que podemos filtrar estatisticamente.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 27,
"id": "f9cf9a07-5251-47bc-9713-c802f8f1a37c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{'00000000': 58, '01000000': 41, '11000000': 42, '10000000': 40}\n"
]
}
],
"source": [
"# Dictionary of bitstrings and their counts to keep\n",
"counts_keep = {}\n",
"# Threshold to filter\n",
"threshold = np.max(list(counts.values())) / 2\n",
"\n",
"for key, value in counts.items():\n",
" if value > threshold:\n",
" counts_keep[key] = value\n",
"\n",
"print(counts_keep)"
]
},
{
"cell_type": "markdown",
"id": "c32cca67-9c9d-4373-9a0a-3174e884dd91",
"metadata": {},
"source": [
"\n",
"\n",
"## Etapa 4: Pós-processamento e retorno do resultado no formato clássico desejado\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "5a7b116b-02d0-47dc-8cab-e792ba36d868",
"metadata": {},
"source": [
"\n",
"\n",
"### Fatoração de números inteiros\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "691df180-6ac3-49ac-ad4d-2d78348ceea7",
"metadata": {},
"source": [
"Até agora, discutimos como podemos implementar o problema de determinação de ordem usando um circuito de estimativa de fase. Agora, conectamos o problema de determinação de ordem à fatoração de números inteiros, o que completa o algoritmo de Shor. Observe que essa parte do algoritmo é clássica.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "fe3472a3-f8cd-4db9-8178-c025ccf2ec55",
"metadata": {},
"source": [
"Agora demonstramos isso usando nosso exemplo de $N = 15$ e $a = 2$. Lembre-se de que a fase que medimos é $k / r$, em que $a^r \\; (\\textrm{mod} \\; N) = 1$ e $k$ é um número inteiro aleatório entre $0$ e $r - 1$. A partir dessa equação, temos $(a^r - 1) \\; (\\textrm{mod} \\; N) = 0,$, o que significa que $N$ deve dividir $a^r-1$. Se $r$ também for par, podemos escrever $a^r -1 = (a^{r/2}-1)(a^{r/2}+1).$. Se $r$ não for par, não podemos ir adiante e devemos tentar novamente com um valor diferente para $a$; caso contrário, há uma grande probabilidade de que o maior divisor comum de $N$ e $a^{r/2}-1$ ou $a^{r/2}+1$ seja um fator próprio de $N$.\n",
"\n",
"Como algumas execuções do algoritmo falharão estatisticamente, repetiremos esse algoritmo até que pelo menos um fator de $N$ seja encontrado.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "dda4ad11-ef2b-4bfb-ba3c-5cb1f5810871",
"metadata": {},
"source": [
"A célula abaixo repete o algoritmo até que pelo menos um fator de $N=15$ seja encontrado. Usaremos os resultados da execução de hardware acima para adivinhar a fase e o fator correspondente em cada iteração.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 28,
"id": "5d67cd71-8651-4a10-a913-a5bdaa6d6b38",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"ATTEMPT 0:\n",
"Phase: theta = 0.0\n",
"Order of 2 modulo 15 estimated as: r = 1\n",
"\n",
"ATTEMPT 1:\n",
"Phase: theta = 0.25\n",
"Order of 2 modulo 15 estimated as: r = 4\n",
"*** Non-trivial factor found: 3 ***\n"
]
}
],
"source": [
"a = 2\n",
"N = 15\n",
"\n",
"FACTOR_FOUND = False\n",
"num_attempt = 0\n",
"\n",
"while not FACTOR_FOUND:\n",
" print(f\"\\nATTEMPT {num_attempt}:\")\n",
" # Here, we get the bitstring by iterating over outcomes\n",
" # of a previous hardware run with multiple shots.\n",
" # Instead, we can also perform a single-shot measurement\n",
" # here in the loop.\n",
" bitstring = list(counts_keep.keys())[num_attempt]\n",
" num_attempt += 1\n",
" # Find the phase from measurement\n",
" decimal = int(bitstring, 2)\n",
" phase = decimal / (2**num_control) # phase = k / r\n",
" print(f\"Phase: theta = {phase}\")\n",
"\n",
" # Guess the order from phase\n",
" frac = Fraction(phase).limit_denominator(N)\n",
" r = frac.denominator # order = r\n",
" print(f\"Order of {a} modulo {N} estimated as: r = {r}\")\n",
"\n",
" if phase != 0:\n",
" # Guesses for factors are gcd(a^{r / 2} ± 1, 15)\n",
" if r % 2 == 0:\n",
" x = pow(a, r // 2, N) - 1\n",
" d = gcd(x, N)\n",
" if d > 1:\n",
" FACTOR_FOUND = True\n",
" print(f\"*** Non-trivial factor found: {x} ***\")"
]
},
{
"cell_type": "markdown",
"id": "00f31b56-e1a9-479e-8a82-bb708263f1a3",
"metadata": {},
"source": [
"\n",
"\n",
"## Discussão\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "69189c94-6e78-410d-a365-8649d4c69163",
"metadata": {},
"source": [
"\n",
"\n",
"### Trabalhos relacionados\n",
"\n",
"Nesta seção, discutiremos outros trabalhos importantes que demonstraram o algoritmo de Shor em hardware real.\n",
"\n",
"O trabalho seminal [\\[3\\]](#references) de IBM® demonstrou o algoritmo de Shor pela primeira vez, fatorando o número 15 em seus fatores primos 3 e 5 usando um computador quântico de ressonância magnética nuclear (NMR) de sete qubits. Outro experimento [\\[4\\]](#references) fatorou 15 usando qubits fotônicos. Empregando um único qubit reciclado várias vezes e codificando o registro de trabalho em estados de dimensões mais altas, os pesquisadores reduziram o número necessário de qubits para um terço do protocolo padrão, utilizando um algoritmo compilado de dois fótons. Um artigo importante na demonstração do algoritmo de Shor é [\\[5\\]](#references), que usa a técnica de estimativa de fase iterativa de Kitaev [\\[8\\]](#references) para reduzir o requisito de qubit do algoritmo. Os autores usaram sete qubits de controle e quatro qubits de cache, juntamente com a implementação de multiplicadores modulares. Essa implementação, no entanto, exige medições no meio do circuito com operações de avanço e reciclagem de qubit com operações de reinicialização. Essa demonstração foi feita em um computador quântico de armadilha de íons.\n",
"\n",
"Um trabalho mais recente [\\[6\\]](#references) concentrou-se na fatoração de 15, 21 e 35 no hardware IBM Quantum®. Semelhante ao trabalho anterior, os pesquisadores usaram uma versão compilada do algoritmo que empregou uma transformada quântica de Fourier semiclássica, conforme proposto por Kitaev, para minimizar o número de qubits e portas físicas. Um trabalho mais recente [\\[7\\]](#references) também realizou uma demonstração de prova de conceito para fatorar o inteiro 21. Essa demonstração também envolveu o uso de uma versão compilada da rotina de estimativa de fase quântica e se baseou na demonstração anterior de [\\[4\\]](#references). Os autores foram além desse trabalho, usando uma configuração de portas Toffoli aproximadas com mudanças de fase residuais. O algoritmo foi implementado em processadores quânticos IBM usando apenas cinco qubits, e a presença de emaranhamento entre o controle e os qubits de registro foi verificada com sucesso.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "2dab9ac1-d3e4-4b4e-babe-472d69b026ab",
"metadata": {},
"source": [
"\n",
"\n",
"### Escalonamento do algoritmo\n",
"\n",
"Observamos que a criptografia RSA normalmente envolve tamanhos de chave da ordem de 2048 a 4096 bits. A tentativa de fatorar um número de 2048 bits com o algoritmo de Shor resultará em um circuito quântico com milhões de qubits, incluindo a sobrecarga de correção de erros e uma profundidade de circuito da ordem de um bilhão, o que está além dos limites de execução do hardware quântico atual. Portanto, o algoritmo de Shor exigirá métodos otimizados de construção de circuitos ou correção robusta de erros quânticos para ser praticamente viável na quebra de sistemas criptográficos modernos. Consulte [\\[9\\]](#references) para obter uma discussão mais detalhada sobre a estimativa de recursos para o algoritmo de Shor.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "cb53f62c-e560-43cf-a614-d31f266a569c",
"metadata": {},
"source": [
"\n",
"\n",
"## Desafio\n",
"\n",
"Parabéns por ter concluído o tutorial! Agora é um ótimo momento para testar sua compreensão. Você poderia tentar construir o circuito para fatorar 21? Você pode selecionar um $a$ de sua preferência. Você precisará decidir sobre a precisão de bits do algoritmo para escolher o número de qubits, e precisará projetar os operadores de exponenciação modular $M_a$. Recomendamos que você experimente fazer isso por conta própria e depois leia sobre as metodologias mostradas na Fig. 9 de [\\[6\\]](#references) e na Fig. 2 de [\\[7\\]](#references).\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "09d347b8-51a4-4eb5-8422-76508f7ba1ad",
"metadata": {},
"outputs": [],
"source": [
"def M_a_mod21():\n",
" \"\"\"\n",
" M_a (mod 21)\n",
" \"\"\"\n",
"\n",
" # Your code here\n",
" pass"
]
},
{
"cell_type": "markdown",
"id": "dc16f509-7441-4221-8113-e09b118397a0",
"metadata": {},
"source": [
"\n",
"\n",
"## Referências\n",
"\n",
"1. Shor, Peter W. \" [Algoritmos de tempo polinomial para fatoração de primos e logaritmos discretos em um computador quântico](https://epubs.siam.org/doi/abs/10.1137/S0036144598347011).\" SIAM review 41.2 (1999): 303-332.\n",
"2. IBM Quantum Curso [“Fundamentos dos Algoritmos Quânticos”,](/learning/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/introduction) ministrado pelo Dr. John Watrous.\n",
"3. Vandersypen, Lieven MK, et al. \" [Realização experimental do algoritmo de fatoração quântica de Shor usando ressonância magnética nuclear](https://www.nature.com/articles/414883a).\" Nature 414.6866 (2001): 883-887.\n",
"4. Martin-Lopez, Enrique, et al. \"[Realização experimental do algoritmo de fatoração quântica de Shor usando reciclagem de qubit](https://www.nature.com/articles/nphoton.2012.259) \" Nature photonics 6.11 (2012): 773-776.\n",
"5. Monz, Thomas, et al. \"[Realização de um algoritmo Shor escalável](https://www.science.org/doi/full/10.1126/science.aad9480) \" Science 351.6277 (2016): 1068-1070.\n",
"6. Amico, Mirko, Zain H. Saleem e Muir Kumph. \"[Estudo experimental do algoritmo de fatoração de Shor usando o IBM Q Experience](https://journals.aps.org/pra/abstract/10.1103/PhysRevA.100.012305).\" Physical Review A 100.1 (2019): 012305.\n",
"7. Skosana, Unathi e Mark Tame. \"[Demonstração do algoritmo de fatoração de Shor para N=21 em processadores quânticos IBM](https://www.nature.com/articles/s41598-021-95973-w).\" Relatórios científicos 11.1 (2021): 16599.\n",
"8. Kitaev, A. Yu. \"[Medições quânticas e o problema do estabilizador abeliano](https://arxiv.org/abs/quant-ph/9511026) \" arXiv preprint quant-ph/9511026 (1995).\n",
"9. Gidney, Craig e Martin Ekerå. \"[Como fatorar números inteiros RSA de 2048 bits em 8 horas usando 20 milhões de qubits ruidosos](https://doi.org/10.22331/q-2021-04-15-433).\" Quantum 5 (2021): 433.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3"
},
"hours": 1,
"qpuSeconds": 3
},
"nbformat": 4,
"nbformat_minor": 4
}