Note

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

# 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
%qiskit_copyright
```

### Version Information

Qiskit Software | Version |
---|---|

`qiskit-terra` | 0.23.0 |

`qiskit-aer` | 0.11.2 |

`qiskit-ibmq-provider` | 0.19.2 |

`qiskit` | 0.40.0 |

`qiskit-nature` | 0.5.2 |

`qiskit-finance` | 0.3.4 |

`qiskit-optimization` | 0.4.0 |

`qiskit-machine-learning` | 0.5.0 |

System information | |

Python version | 3.8.16 |

Python compiler | GCC 11.3.0 |

Python build | default, Jan 11 2023 00:28:51 |

OS | Linux |

CPUs | 2 |

Memory (Gb) | 6.781219482421875 |

Thu Jan 26 23:19:15 2023 UTC |

### This code is a part of Qiskit

© Copyright IBM 2017, 2023.

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.