3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Community Bot
    Jan 11, 2023 at 7:10
  • $\begingroup$ Related: quantumcomputing.stackexchange.com/questions/15280/… $\endgroup$ Jan 12, 2023 at 8:47
  • $\begingroup$ 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. $\endgroup$
    – Guangliang
    Feb 4, 2023 at 2:06

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.