Note

This page was generated from tutorials/algorithms/08_factorizers.ipynb.

Run interactively in the IBM Quantum lab.

Shor’s algorithms

Qiskit has an implementation of Shor’s algorithm.

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.

import math
import numpy as np
from qiskit import Aer
from qiskit.utils import QuantumInstance
from qiskit.algorithms import Shor

Shor’s Factoring algorithm

Shor’s Factoring algorithm 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:

N = 15
backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
shor = Shor(quantum_instance=quantum_instance)
result = shor.factor(N)
print(f"The list of factors of {N} as computed by the Shor's algorithm is {result.factors[0]}.")

The list of factors of 15 as computed by the Shor's algorithm is [3, 5].

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.

print(f'Computed of qubits for circuit: {4 * math.ceil(math.log(N, 2)) + 2}')
print(f'Actual number of qubits of circuit: {shor.construct_circuit(N).num_qubits}')

Computed of qubits for circuit: 18
Actual number of qubits of circuit: 18

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	None
Terra	0.18.0.dev0+5920b66
Aer	0.9.0
Ignis	0.7.0.dev0+8195559
Aqua	None
IBM Q Provider	None
System information
Python	3.8.8 (default, Apr 13 2021, 12:59:45) [Clang 10.0.0 ]
OS	Darwin
CPUs	2
Memory (Gb)	12.0
Thu May 27 11:05:34 2021 EDT

This code is a part of Qiskit

© Copyright IBM 2017, 2021.

This code is licensed under the Apache License, Version 2.0. You may
obtain a copy of this license in the LICENSE.txt file in the root directory
of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this
copyright notice, and modified files need to carry a notice indicating
that they have been altered from the originals.