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 7,8 8,11 11,13 13 (although I suspect that 4 is not considered as it is $$2^2$$). For $$a=2 \,\text{or}\, 13$$$$a=2$$ or $$13$$, we swap qubits 0 and 1, 1 and 2, 2 and 3. If $$a=7 \,\text{or}\, 8$$$$a=7$$ or $$8$$, we swap 2 and 3, 1 anand 2, 0 and 1. If $$a=11$$, we swap 1 and 3, 0 and 2. Also, if $$a=7, 11 \,\text{or}\, 13$$$$a=7, 11$$ or $$13$$, we add an X$$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.

Bumped by Community user
Bumped by Community user
Bumped by Community user

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$$N=15$$, we have all the gcds$$\text{gcd}$$ of 15 to be 2,7,8,11,13 (although I suspect that 4 is not considered as it is 2^2$$2^2$$). For a=2 or 13$$a=2 \,\text{or}\, 13$$, we swap qubits 0 and 1, 1 and 2, 2 and 3. If a=7 or 8$$a=7 \,\text{or}\, 8$$, we swap 2 and 3, 1 an 2, 0 and 1. If a=11$$a=11$$, we swap 1 and 3, 0 and 2. Also, if a=7, 11 or 13$$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 want to know how we chose which qubits to swap for a particular number, and how we can generalize it, if possible.

# 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 gcds 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 an 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.