English
Languages
English
Bengali
French
German
Japanese
Korean
Portuguese
Spanish
Tamil

Note

# 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]}.")

/tmp/ipykernel_9053/2546798916.py:4: DeprecationWarning: The Shor class is deprecated as of Qiskit Terra 0.22.0 and will be removed
no sooner than 3 months after the release date.
It is replaced by the tutorial at https://qiskit.org/textbook/ch-algorithms/shor.html

shor = Shor(quantum_instance=quantum_instance)

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


### Version Information

Qiskit SoftwareVersion
qiskit-terra0.23.0
qiskit-aer0.11.2
qiskit-ibmq-provider0.19.2
qiskit0.40.0
qiskit-nature0.5.2
qiskit-finance0.3.4
qiskit-optimization0.4.0
qiskit-machine-learning0.5.0
System information
Python version3.8.16
Python compilerGCC 11.3.0
Python builddefault, Jan 11 2023 00:28:51
OSLinux
CPUs2
Memory (Gb)6.781219482421875
Thu Jan 26 23:19:15 2023 UTC