Using Shor's algorithm on Qiskit

Shor's algorithm is a quantum algorithm for factoring integers that was discovered by mathematician Peter Shor in 1994. It is the most efficient known classical algorithm for this task. However, implementing Shor's algorithm requires a large amount of qubits and a high level of precision, which are currently not possible with current quantum technology.

For example: Can we run Shor's algorithm on a 100 digit number?

The short answer is NO. It is currently not possible to run Shor's algorithm on a 100-digit number using currently available quantum computers. The number of qubits required for factoring a 100-digit number using Shor's algorithm is on the order of several hundred, and current quantum computers have significantly fewer qubits. Additionally, the precision required to run Shor's algorithm on a 100-digit number is also currently beyond the capabilities of available quantum computers. The development of quantum computers is still in its early stages, and while progress is being made, it is difficult to predict when a quantum computer with the necessary number of qubits and precision will be available. It is expected that it will take several more years, if not decades, before we have a quantum computer that can run Shor's algorithm on a 100-digit number.

As the technology advances, the number of qubits on a single chip is increasing and the error rate is decreasing. It is also possible that new algorithms or modifications of Shor's algorithm may be developed that can run on a smaller number of qubits or with less precision. However, it is still an active area of research and it is hard to give a definitive answer on when it will be possible to run Shor's algorithm on 100 digit numbers using quantum computers. So, what is the limit of current classical super computers to calculate factoring number ? The limit of classical supercomputers to calculate the factoring of a number depends on the specific algorithm being used, as well as the size of the number being factored. The most well-known classical algorithm for factoring integers is the general number field sieve (GNFS), which is the most efficient known classical algorithm for factoring integers. The GNFS algorithm has a running time of O(exp((64/9)^(1/3)(ln N)^(2/3)(ln ln N)^(1/3))), where N is the number being factored. This means that the running time of the algorithm grows exponentially with the size of the number being factored.

For example, factoring a number with 100 digits using GNFS algorithm would take significantly longer time than factoring a number with 50 digits, even with the most powerful classical supercomputers. With the current technology and resources, factoring large numbers such as a 100-digit number is considered to be infeasible using classical supercomputers.

There are other algorithms for factoring integers such as the Quadratic Sieve, that have lower asymptotic complexities than GNFS, but still the factoring of large integers with hundreds of digits is considered computationally infeasible with the current technology.

It's worth noting that the limit of classical supercomputers to factorize a number is closely related to the security of encryption systems such as RSA, which is widely used in secure communication. In order to guarantee the security of RSA, the numbers that are used as the keys need to be large enough such that factoring them would be infeasible with the current technology.

Here is an example of how Shor's algorithm could be implemented in Qiskit, a Python library for quantum computing:

START

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, execute

from qiskit.quantum_info import state_fidelity

from math import gcd

# Define the number to be factored

N = 15

# Define the number of qubits needed for the algorithm

num_qubits = 2 * (len(bin(N))-2)

# Create the quantum and classical registers

q = QuantumRegister(num_qubits)

c = ClassicalRegister(num_qubits)

# Create the quantum circuit

qc = QuantumCircuit(q, c)

# Add the necessary gates for the algorithm

# ...

# Execute the circuit on a quantum simulator

backend = Aer.get_backend('qasm_simulator')

job = execute(qc, backend, shots=1)

result = job.result()

# Measure the qubits and obtain the output

output = result.get_counts()

# Extract the factors of N from the output

# ...

# Print the factors

print("The factors of", N, "are", factors)

END

This code demonstrates how Shor's algorithm could be implemented using Qiskit. However, it is important to note that this example is highly simplified and would not work in a real-world scenario, as it lacks the majority of the quantum gates and instructions necessary for the algorithm. Currently, I have a project to test the algorithm on classical PC simulation systems.

In addition, it is important to note that the factoring problem is in the complexity class of problems named BQP (Bounded error Quantum Polynomial time) which means that with a quantum computer it can be solved exponentially faster than with a classical computer, but we currently don't have a quantum computer with enough qubits and precision to run it.