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

Question

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$ or $13$, we swap qubits 0 and 1, 1 and 2, 2 and 3. If $a=7$ or $8$, we swap 2 and 3, 1 and 2, 0 and 1. If $a=11$, we swap 1 and 3, 0 and 2. Also, if $a=7, 11$ 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.

Answer 1

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
  

Answer 2

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 = |ya \: \text{mod} \: N\rangle $
$ U^2|y\rangle = |ya^2\: \text{mod} \:N\rangle $
$ U^4|y\rangle = |ya^4\: \text{mod} \:N\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 $|16\: \text{mod} \:15\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 = |4\: \text{mod} \:15\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!