# Trying to construct modular exponentiation gate in Qiskit

https://qiskit.org/textbook/ch-algorithms/shor.html in this tutorial I don't understand especially in how they define for the modular exponentiation gate with only swap gate (inside c_amod15 function).

def c_amod15(a, power):
"""Controlled multiplication by a mod 15"""
if a not in [2,4,7,8,11,13]:
raise ValueError("'a' must be 2,4,7,8,11 or 13")
U = QuantumCircuit(4)
for iteration in range(power):
if a in [2,13]:
U.swap(2,3)
U.swap(1,2)
U.swap(0,1)
if a in [7,8]:
U.swap(0,1)
U.swap(1,2)
U.swap(2,3)
if a in [4, 11]:
U.swap(1,3)
U.swap(0,2)
if a in [7,11,13]:
for q in range(4):
U.x(q)
U = U.to_gate()
U.name = "%i^%i mod 15" % (a, power)
c_U = U.control()
return c_U


is not very clear to me how they suddenly come up with this code without a detail explanation

• Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
– Community Bot
Jan 11, 2023 at 7:10
• Jan 12, 2023 at 8:47
• watch the bit pattern change from $x$ to $ax\mod 15$ for a given $a$ value, then compare to the gate generated by this method, you should be able to understand the process. Feb 4, 2023 at 2:06

This circuit represents the operation $$x*a^p \mod 15$$. In order to implement any arithmetic operation we need to manipulate bits. For simplicity let's put $$x=1$$. This will allows us to focus on the swap gates.

For example, suppose $$a=2$$ and $$p=3$$. Then our operation is $$1*2^3 = 1*2*2*2$$. Let's work it out in binary. Note that \begin{align} 1 * 1 &= 1 \equiv 0001 * 0001 = 000\color{red}1. \end{align} Then we have: \begin{align} \tag{1} 1*2 &= 2 \equiv 0001 * 0010 = 00\color{red}10,\\ 2*2 & = 4 \equiv 0010 * 0010 = 0\color{red}100\\ 4*2 &= 8 \equiv 0100 * 0010 = \color{red}1000. \end{align} The pattern is very clear, repetitive multiplication by $$2$$ shifts the red bit from right to left. Let's do another multiplication by $$2$$ to bring it home: $$2^3 *2 \mod 15 = 1$$. So we get that $$2^4 = 1$$ in mod $$15$$. Let's verify this by continuing the multiplication table above: \begin{align} 4*2 &= 8 \equiv 0100 * 0010 = \color{red}1000\\ 8 * 2 &= 1 \equiv 1000 * 0010 = 000\color{red}1. \end{align} So we indeed get a cyclic shift from right to left, i.e., we return back to where we have started. So implementing an operation $$a^p \mod 15$$ amounts to shifting the bit $$\color{red}1$$. This shift is achieved by doing a series of swaps that exchange the position of $$\color{red}1$$.

In the example given in Eq (1), we had $$p=3$$, so it took $$3$$ iterations to get $$2^3 =8$$. This is reflected in the code where the variable power would be equal to 3:

for iteration in range(power):
if a in [2,13]:
U.swap(2,3)
U.swap(1,2)
U.swap(0,1)


The first iteration will shift the bit $$\color{red}1$$ from the most right to left by one position. The second iteration will shift the bit by one more position. And finally, the third iteration will give $$\color{red}1000$$.

I hope you can figure out the rest.