# Is there a general order finding quantum algorithm for a given a and N?

I'm trying to construct a general circuit for Shor's algorithm in Qiskit. I understood the later parts of the circuit (inverse QFT and QPE), but can't really understand the order finding. For example, if we consider $$N=15$$, we have all the $$\text{gcd}$$ of 15 to be 2,7,8,11,13 (although I suspect that 4 is not considered as it is $$2^2$$). For $$a=2 \,\text{or}\, 13$$, we swap qubits 0 and 1, 1 and 2, 2 and 3. If $$a=7 \,\text{or}\, 8$$, we swap 2 and 3, 1 an 2, 0 and 1. If $$a=11$$, we swap 1 and 3, 0 and 2. Also, if $$a=7, 11 \,\text{or}\, 13$$, we add an X gate on all the 4 added qubits.

I want to know how we chose which qubits to swap for a particular number, and how we can generalize it, if possible.

I shall explain taking the case of a = 2. The process is the same for any other value of a you have mentioned.

So to factor N = 15, you need the gates $$U^4$$, $$U^2$$ and $$U^1$$ gates. Where U performs the following operation $$U|y\rangle = |yamodN\rangle$$
$$U^2|y\rangle = |ya^2modN\rangle$$
$$U^4|y\rangle = |ya^4modN\rangle$$

We first apply $$U^4$$ then $$U^2$$ and finally $$U^1$$. I am assuming that you are aware that we start Shor's algorithm by giving an input $$|1\rangle$$ to $$U^4$$ which simply performs $$|16mod15\rangle = |1\rangle$$. Actually if you try out all the possible input values you will realise that $$U^4$$ is actually an identity operation.

For $$U^2$$, the operation performed is $$U^2|1\rangle = |4mod15\rangle = |4\rangle$$. Now in shors algorithm the size of the register on which U acts is 4 qubits (for N = 15, as 4 qubit are needed to represent 15, size of register is $$log_2(n)$$). So $$|1\rangle$$ is represented by 0001 and similarly $$|4\rangle$$ by 0100. Therefore we need to swap 1st and third row. This is the general procedure.

Now the two possible kets which may enter $$U$$ are $$|1\rangle$$ and $$|4\rangle$$. So you need to be able to map them to $$|2\rangle$$ and $$|8\rangle$$ respectively. Which is a mapping from 0001 and 0100 to 0010 and 1000 respectively. Hence the first mapping demands swapping of bits 1 and 2 and the second mapping demands swapping qubits 3 and 4. This is the process of designing these gates. In your question you have talked about U gate. You can either create $$U^2$$ by applying U twice or by the method I have described above. Hope this helps!

In general, you need to use modular exponentiation algorithm. In Qiskit tutorial, I guess they saw some pattern to for that specific case to implement operator $$U$$. Yet you can use the following idea to create operator $$U$$. Let's suppose that $$a=11$$ and $$N=21$$. u is the matrix that corresponds to operator $$U$$. By using u, you should be able to create a gate. Note that we are cheating since if you do all below operations, you already know the order $$r$$ and there is no need for order finding algorithm.

import numpy as np
u = np.zeros([32, 32], dtype = int)

for i in range(21):
u[11*i%21][i]=1
for i in range(21,32):
u[i][i]=1