cirq

Cirq Textbook

Cirq comes with a collection of example implementations of beginner, intermediate, and advanced quantum algorithms that demonstrate the main features of the library.

Qiskit

Qiskit Textbook

Shor's algorithm

Implementing Shor’s Algorithm using Qiskit

Introduction

Shor’s algorithm is famous for factoring integers in polynomial time. Since the best-known classical algorithm requires superpolynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers.

The algorithm is significant because it implies that public key cryptography might be easily broken, given a sufficiently large quantum computer. RSA, for example, uses a public key N which is the product of two large prime numbers. One way to crack RSA encryption is by factoring N, but with classical algorithms, factoring becomes increasingly time-consuming as N grows large; more specifically, no classical algorithm is known that can factor in time O((log N)k) for any k. By contrast, Shor’s algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor’s algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor’s algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.

Implementation

The algorithm can be implemented incredibly easily since Qiskit has a baked in function for the algorithm called Shor(N).

Where N will be the integer you wish to factor. For example Shor(21) will find the prime factors for 21.

You will need an API token which you can get by registering here: https://quantum-computing.ibm.com/



from qiskit import IBMQ

from qiskit.aqua import QuantumInstance

from qiskit.aqua.algorithms import Shor

IBMQ.enable_account('ENTER API TOKEN HERE') # Enter your API token here

provider = IBMQ.get_provider(hub='ibm-q')

backend = provider.get_backend('ibmq_qasm_simulator') # Specifies the quantum device

print('\n Shors Algorithm')

print('--------------------')

print('\nExecuting...\n')

factors = Shor(21) #Function to run Shor's algorithm where 21 is the integer to be factored

result_dict = factors.run(QuantumInstance(backend, shots=1, skip_qobj_validation=False))

result = result_dict['factors'] # Get factors from results print(result)

print('\nPress any key to close')