<p>To try and answer your question in the comments:</p>
<blockquote>
<p>I guess my question is why swapping register bits can give us a gate realizing order finding algorithms.</p>
</blockquote>
<p>One way to think of Shor's algorithm is it takes as input:</p>
<ul>
<li>A circuit* <code>U</code>, and</li>
<li>a starting state <code>|ψ⟩</code></li>
</ul>
<p>Shor's algorithm tells us the <em>period</em> of that circuit, i.e. the number of times you need to repeat <code>U</code> to get back to your initial input. We then use a classical algorithm to map factoring to this problem by setting <code>U|y⟩≡|ay mod N⟩</code> and <code>|ψ⟩=|1⟩</code>.</p>
<p>You can confirm through simulations that the circuit in the Qiskit Textbook has that property, although it doesn't give a method of generating that circuit (I imagine it was educated guessing similar to <a href="https://quantumcomputing.stackexchange.com/questions/12849/how-to-implement-cx-mod-n-unitary/12861#12861">this answer</a> but you'll need to read <a href="https://arxiv.org/abs/quant-ph/0205095" rel="nofollow noreferrer">that paper</a> in the other answer for a general method).</p>
<p>If we already know the answer using the algorithm, then we could just find any old circuit with the correct period and plug that in. E.g. a single swap gate acting on <code>|1⟩</code> has period 2. Although this doesn't really count as &quot;doing Shor's algorithm&quot;, it's often used to demonstrate the algorithm works <a href="https://www.nature.com/articles/s41598-021-95973-w" rel="nofollow noreferrer">1</a> <a href="https://github.com/qiskit-community/ibm-quantum-challenge-2021/blob/main/solutions%20by%20participants/ex2/ex2-AlbertoMaldonadoRomo-6cnot.ipynb" rel="nofollow noreferrer">2</a>.</p>
<hr />
<p>*To make the algorithm efficient, the input is really &quot;an efficient way to make circuits for <code>U^(2^x)</code>&quot;. Fortunately, we know how to do this for the circuits needed for factoring, but the Qiskit textbook just repeats <code>U</code> inefficiently for sake of demonstration.</p>
One question about circuit realization of Shor's algorithm in quantum computing
<p>I am studying the quantum circuit realization of Shor's algorithm about factoring 15 into product of prime numbers using the python package Qiskit. See this <a href="https://qiskit.org/textbook/ch-algorithms/shor.html" rel="nofollow noreferrer">website</a> for details.</p>
<p>My question is related to the realization of U-gate in this website. In this website, the realization of U-gate is given in the form</p>
<pre><code>def c_amod15(a, power):
    &quot;&quot;&quot;Controlled multiplication by a mod 15&quot;&quot;&quot;
    if a not in [2,7,8,11,13]:
        raise ValueError(&quot;'a' must be 2,7,8,11 or 13&quot;)
    U = QuantumCircuit(4)        
    for iteration in range(power):
        if a in [2,13]:
            U.swap(0,1)
            U.swap(1,2)
            U.swap(2,3)
        if a in [7,8]:
            U.swap(2,3)
            U.swap(1,2)
            U.swap(0,1)
        if a == 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 = &quot;%i^%i mod 15&quot; % (a, power)
    c_U = U.control()
    return c_U
</code></pre>
<p>My question is that why this U-gate is engineered in such way by swapping qbits. How exactly the value of 'a' will affect the swapping scheme? What if I want to factor 33? How should I change this swapping scheme to factor 33?</p>