Bemerkung

# 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


### 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) [Clang 10.0.0 ]
OSDarwin
CPUs2
Memory (Gb)12.0
Thu May 27 11:05:34 2021 EDT

### This code is a part of Qiskit

obtain a copy of this license in the LICENSE.txt file in the root directory

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.