Implementing Shor’s Factoring Algorithm and Comparing to Classical Factoring Algorithms

1. The following gate can be used to factor the number of 15 with all possible values of a. This gate is presented withouth proof and taken from the Qiskit Textbook.

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 = f"{a}^{power} mod 15"
    c_U = U.control()
    return c_U

1. (5 pts.) Explain why a = 2, 4, 7, 8, 11, and 13 are valid choices for factoring N = 15 but other numbers are not.

2. (25 pts.) Implement this gate into a quantum phase estimation (QPE) algorithm and set up the appropriate post-processing to determing the factors of N = 15.

3. (10 pts.) Does there appear to be a value of a which gives the best results (consider the most common output only)?

4. (10 pts.) What is the minimim number of counting qubits needed to accurately predict the factors of N = 15 for the a value you choose in part c?