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.


2 Answers 2


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):
for i in range(21,32):

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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.