# shors-algorithm

**Repository Path**: vincentwang11/shors-algorithm

## Basic Information

- **Project Name**: shors-algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-05-15
- **Last Updated**: 2025-05-15

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Shor's Algorithms
This is some Qiskit code built as a learning tool to show how Shor's algorithm works. Given the scope
of the project and its purpose as an introductory learning tool, the function is only able to actually factor
the number 15 as implementing an operator for any general N is a very complex task that theorists are still
discovering new ways to do.


## Usage
Simply run the main python file

```
python main.py
````

Upon running the program, the user will be prompted for a number to factor and another random integer
to use as the "guess". If desired, the user can then simulate that hardware using Qiskit's Aer simulator
which will return a factor and print a histogram of what a quantum computer would have measured. The user
can also choose to simply print the circuit and see how it would look for integers != 15

## Implementation

The file which the user runs (main.py) is mostly a wrapper file which just collects input from the user
and verifies that the input is valid. Upon collecting all the data, the file makes use of the functions
implemented in "classical.py". Classical.py implements all the classical functions necessary to run Shor's algorithm
(hence the name) and makes use of "quantum.py" for all the Qiskit code and quantum computing. Quantum.py, as you
would expect, implements the quantum circuits required for Shor's algorithm.

### Nitty-Gritty

At it's core, Shor's algorithm works by turning the problem of factoring a number into a period finding problem then
involving quantum phase estimation (QPE) to solve for said period and thereby factor the number. To do this, Shor's algorithm
first and foremost makes use of two import math theorems:  

1. The Euclidean Algorithm (which provides a classical algorithm to find the GCD of two natural numbers)
2. Euler's Theorem (which says that a^x = 1 (mod N) for some integer x if a and N are co-prime)

The second of these theorems, Euler's Theorem, is particularly useful in that by simply subtracting 1 and factoring:  

a^x = 1 (mod N)  
a^x - 1 = 0 (mod N)  
(a^(x/2) - 1) * (a^(x/2) + 1) = 0 (mod N)  

We are able to see that finding an integer x such that a^x = 1 (mod N), we will have a high likelihood of "guessing" a
factor of N. This is turned into a period finding problem by simply acknowledging that a^0 = 1 (mod N) is a trivial solution
to this problem and that since (mod N) makes the function periodic, we can simply add the period (which we will call r) to
the 0 to get a non trivial solution:  

a^0 = 1 (mod N) and a^0 = a^(0+r) (mod N) therefore  
a^r = 1 (mod N)  

Next we can rewrite this as a quantum operator U:  

U|y> = |ay mod N>  

By applying this operator x times, we can achieve a quantum version of the function a^x mod N. Now that we have this function
written as a quantum operator, we can find the period by looking for an eigenstate which contains information about the period
then using QPE to get the eigenvalue of said eigenstate. The first step in this process is recognizing that if we set |y> equal to a 
super position of all the unique values you get by reapplying U, you get an eigenstate as there are only a limited number of unique values 
that can be generated by reapplying U (See slide 24 for a visual).  

Albeit an interesting result, this eigenstate isn't useful in and of itself, but we can make it a useful eigenstate by simply encoding
the number of times U has been applied to the phase of each individual state (See slide 25). This turns the eigenvalue into
e^(2pi(k/r)s) where s is an integer between 0 and r-1 (this is simply due to the fact that there are different ways you could encode the number of
times U has been applied into the phase). Since this eigenstate's eigenvalue contains information about the period, it makes it a perfect eigenstate to use for QPE.  

QPE works by relying on the fact that unitary operators that apply a phase to a qubit will "kickback" the applied phase onto a control qubit (if one is being used). This means
allows us to extract the phase that U applies to qubits by creating a register of t qubits (for reasons we'll see later, t is typically twice the size of the number of bits used
to describe the number you're factoring) where each qubit is used as a control qubit for an operator which applies U 2^t times (That is to say, qubit 0 will cause U to be applied once and 
qubit 3 will cause U to be applied 8 times). This encodes the phase of the operator U into the register of qubits in the exact same way that a Quantum Fourier Transform (QFT) does which
means we can use the inverse of QFT (QFT dagger) to convert the stored phases back into a regular basis. Upon measuring these qubits in the standard basis we will get the phase of U (which is s/r) times 2^t.
Turning this back over to the classical algorithms we can simply divide by 2^t and use continued fractions to find s and r.  

The final piece of the theory behind Shor's algorithm is to decide which eigenstate of U to use for QPE (as stated above, there are mulitple values of s which have unique phases of s/r).
Thankfully it turns out that a superposition of all the eigenstates will cause the phases to destructively interfere and simply result in the phase |1>. This means that by using the phase |1>
we QPE will simultaneously calculate the phase of every unique eigenstate and once we measure the circuit, the state will collapse into just one and we will end up measuring a random s/r. Repeating
this a few times gives us a list of all possible values of s/r which, as we established above, can all be used with a high likelyhood to find a factor of N.

### Implementation Short Comings

The above procedure is laid out throughout the files classical.py and quantum.py with comments to explain what is happening each step of the way. The only shortcoming it has is in the implementation
of the unitary operator U. Creating a quantum circuit that implements modular exponentiation proved to be as hard as it sounds and after doing some research, it appears as though finding clean and efficient ways
to do so is still an active field. To remedy this, the above implementation of U is specifically for mod 15 since creating a general one for mod N proved too difficult (although I did have some fun trying). 
So although theoretical papers exist on how to implement a general U (and in fact the source code the Qiskit python package contains one such an example), it was all far too complex to implement in this project. 
But for as discouraging as this may sound, actual trial runs of shor's algorithm on real quantum computers by Google and IBM did not use a general U but rather they have used a U specially made for the number which 
is being factored, much like how this code is.  

## Future of Encryption

Going into 2021, RSA encryption is widely used all across the internet. If you're reading this on GitHub, or any other website for that matter,
you're almost certainly using RSA encryption to prevent man in the middle attacks. To many, this is very problematic since RSA encryption heavily
relies on the difficulty of factoring large semi-prime numbers. As of 2021, the most efficient classical runs in time:  

O(e^(1.9 * log(N)^1/2 * log(log(N))^2/3)  

This time is consider to be "sub-exponential" time since it's faster then a typically exponential but slower then polynomial. Shor's algorithm on the other hand run in time:  

O(log(N)^2 * log(log(N)) * log(log(log(N))))

So here we have an exponential speed up with Shor's algorithm over the best known classical methods. While this may sound like cause for alarm
at first, it's important to look at some of the draw backs of Shor's algorithm. First and foremost we need to look at the number of qubits needed to factor
a number n bits large. As you can see in the above code, the input bits feed into the U gates need to be at least of size n since the U operator can make them up to N-1 large. Secondly
the register which the phase kick back is applied is typically 2n qubits large since the result number after the QFT dagger needs to still be decipherable after a division of 2^t. Already
our circuit is up to 3n qubits large and we haven't even addressed the extra qubits which might be needed to implement the U gate. The standard theoretically implementation of an entire
circuit to run Shor's algorithm has been 4n + 2 qubits but recent work has been done to reduce this down to 2n + 3 qubits (This was done by changing the implementation of the U gate as I mentioned earlier).
This mean that in order to factor a number using modern RSA (which is typically 1,024 to 4,096 bit large) would require up to about 8,200 qubits! Obviously at this point, we're still quite
a ways away from quantum computers with over 8,000 qubits that would be capable of running an algorithm as complex as Shor's. Nevertheless, technology has a history of growing at a surprising rate
and given the grave threat a large enough quantum computer would pose when coupled with shor's algorithm, it's never to early to start looking in to alternatives to RSA.

## Dependencies
This program requires the Qiskit, matplotlib, and pylatexenc which can all be installed with the following command

```
pip install qiskit matplotlib pylatexenc
```

## References
1. https://en.wikipedia.org/wiki/Shors_algorithm
2. https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html#generalqft
3. https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html#generalqft
4. https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html
5. https://arxiv.org/abs/quant-ph/0205095