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.

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'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.

Bumped by Community user
Bumped by Community user
Bumped by Community user
added 59 characters in body
Source Link
Martin Vesely
  • 12.6k
  • 3
  • 21
  • 57

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.

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.

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.

Source Link

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.