{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Shor's algorithms\n", "\n", "Qiskit has an implementation of [Shor's algorithm](https://qiskit.org/textbook/ch-algorithms/shor.html).\n", "\n", "The preceding reference has detailed explanations and build-out of circuits whereas this notebook has examples with the pre-built algorithms in Qiskit that you can use for experimentation and education purposes." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import math\n", "import numpy as np\n", "from qiskit import Aer\n", "from qiskit.utils import QuantumInstance\n", "from qiskit.algorithms import Shor" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Shor's Factoring algorithm\n", "\n", "[Shor’s Factoring algorithm](https://qiskit.org/documentation/stubs/qiskit.algorithms.Shor.html) is one of the most well-known quantum algorithms and finds the prime factors for input integer \$N\$ in polynomial time. The algorithm implementation in Qiskit is simply provided a target integer to be factored and run, as follows:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The list of factors of 15 as computed by the Shor's algorithm is [3, 5].\n" ] } ], "source": [ "N = 15\n", "backend = Aer.get_backend('aer_simulator')\n", "quantum_instance = QuantumInstance(backend, shots=1024)\n", "shor = Shor(quantum_instance=quantum_instance)\n", "result = shor.factor(N)\n", "print(f\"The list of factors of {N} as computed by the Shor's algorithm is {result.factors}.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note: this implementation of Shor's algorithm uses \$4n + 2\$ qubits, where \$n\$ is the number of bits representing the integer in binary. So in practice, for now, this implementation is restricted to factorizing small integers. Given the above value of N we compute \$4n +2\$ below and confirm the size from the actual circuit." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Computed of qubits for circuit: 18\n", "Actual number of qubits of circuit: 18\n" ] } ], "source": [ "print(f'Computed of qubits for circuit: {4 * math.ceil(math.log(N, 2)) + 2}')\n", "print(f'Actual number of qubits of circuit: {shor.construct_circuit(N).num_qubits}')" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "

### Version Information

Qiskit SoftwareVersion
QiskitNone
Terra0.18.0.dev0+5920b66
Aer0.9.0
Ignis0.7.0.dev0+8195559
AquaNone
IBM Q ProviderNone
System information
Python3.8.8 (default, Apr 13 2021, 12:59:45) \n", "[Clang 10.0.0 ]
OSDarwin
CPUs2
Memory (Gb)12.0
Thu May 27 11:05:34 2021 EDT
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "