One question about circuit realization of Shor's algorithm in quantum computing-CodePudding

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 website for details.

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

def c_amod15(a, power):
    """Controlled multiplication by a mod 15"""
    if a not in [2,7,8,11,13]:
        raise ValueError("'a' must be 2,7,8,11 or 13")
    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 = "%i^%i mod 15" % (a, power)
    c_U = U.control()
    return c_U

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?

CodePudding user response：

The value of a is part of the phase estimation part of Shor's algorithm, where the operation

|y> -> |ay mod N>

is applied. So a influences the arithmetic operation and depending on how you implement the modular multiplication influences the final circuit differently.

The Qiskit textbook implementation seems to only support special values of a, but the software package itself has the general code for all values of a: https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/algorithms/factorizers/shor.py

That code uses the Fourier transform to do the multiplication, so a will influence the phase shifts applied after the Fourier transform. Qiskit's implementation is based on this paper where you can find more information.

CodePudding user response：

To try and answer your question in the comments:

I guess my question is why swapping register bits can give us a gate realizing order finding algorithms.

One way to think of Shor's algorithm is it takes as input:

A circuit* U, and
a starting state |ψ⟩

Shor's algorithm tells us the period of that circuit, i.e. the number of times you need to repeat U to get back to your initial input. We then use a classical algorithm to map factoring to this problem by setting U|y⟩≡|ay mod N⟩ and |ψ⟩=|1⟩.

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 this answer but you'll need to read that paper in the other answer for a general method).

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 |1⟩ has period 2. Although this doesn't really count as "doing Shor's algorithm", it's often used to demonstrate the algorithm works 1 2.

*To make the algorithm efficient, the input is really "an efficient way to make circuits for U^(2^x)". Fortunately, we know how to do this for the circuits needed for factoring, but the Qiskit textbook just repeats U inefficiently for sake of demonstration.