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.

[1]:

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:

[2]:

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.

[3]:

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

[4]:

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

/home/computertreker/git/qiskit/qiskit/.tox/docs/lib/python3.7/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
  warn_package('aqua', 'qiskit-terra')

Version Information

Qiskit Software	Version
`qiskit-terra`	0.18.2
`qiskit-aer`	0.8.2
`qiskit-ignis`	0.6.0
`qiskit-ibmq-provider`	0.16.0
`qiskit-aqua`	0.9.5
`qiskit`	0.29.1
`qiskit-nature`	0.2.2
`qiskit-finance`	0.3.0
`qiskit-optimization`	0.2.3
`qiskit-machine-learning`	0.2.1
System information
Python	3.7.12 (default, Nov 22 2021, 14:57:10) [GCC 11.1.0]
OS	Linux
CPUs	32
Memory (Gb)	125.71650314331055
Tue Jan 04 11:05:28 2022 EST

This code is a part of Qiskit

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.