I have been trying to build a Shor's Algorithm simulation for N = 15 on Qiskit's framework. Having referenced the Qiskit textbook, I built a circuit that largely resembles what they have done, with a few minor caveats. I am getting some strange and unexpected measurements, could anybody find where my problem is? Below is my code.

N = 15
a = np.random.randint(2, 15)
if math.gcd(a, N) != 1:
     raise ValueError("Non-trivial factor.") 


def a_mod15(a, x):
    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(x):
        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 = U.to_gate()
    U.name = "%i^%i mod 15" % (a, x)
    c_U = U.control()
    return c_U

def mod_exp(qc, n, m, a):
    for x in range(n):
        qc.append(a_mod15(a, 2**x), [x] + list(range(n, n + m))) 

def iqft(qc, n):
    qc.append(QFT(len(n), do_swaps = False).inverse(), n)
def circ(n, m, a):
    # Let n = 'X register'
    # Let m = 'W register'
    qc = QuantumCircuit(n + m, n)
    qc.x(n + m - 1)
    mod_exp(qc, n, m, a)
    iqft(qc, range(n))
    qc.measure(range(n), range(n))
    return qc

n = 4
m = 4

qc = circ(n, m, a)

simulator = Aer.get_backend('qasm_simulator')
counts = execute(qc, backend=simulator).result().get_counts(qc)


enter image description here

These are the expected Qiskit results (note they used 8 counting qubits and I used 4): enter image description here

  • 2
    $\begingroup$ To better understand the issue, and since your code isn't commented, could you summarize the changes you made from the qiskit example, and also describe the measurement result that you expected? $\endgroup$
    – ryanhill1
    Feb 5, 2022 at 17:46
  • $\begingroup$ for sure, the changes that I made were as follows; 1) Below the mod_exp function that I defined, I iterated through qubits using list(range(n, n + m))), whereas the Qiskit code used [i+n_count for i in range(4)]) - I wouldn't think this would make a difference, though. 2) Qiskit hardcoded the inverse QFT, while I simply used the built-in function and made it the conjugate transpose. 3) While Qiskit appended the modular exponentiation and the inverse QFT, I integrated them as functions, so called them in a slightly different way. (expected result above) Thanks so much! @ryanhill1 $\endgroup$ Feb 6, 2022 at 18:32
  • $\begingroup$ Have you tried using 8 counting qubits like the original? $\endgroup$
    – prairie99
    Feb 7, 2022 at 6:41

1 Answer 1


Your error lies in the use of the built-in QFT inside your iqft function. It seems the issue gets resolved with either of the following two tweaks:

  1. Setting do_swaps=True, i.e.
def iqft(qc, n):
    qc.append(QFT(len(n), do_swaps=True).inverse(), n)
  1. Reverting back to using Qiskit's hard-coded inverse QFT method, i.e.
def qft_dagger(n):
    """n-qubit QFTdagger the first n qubits in circ"""
    qc = QuantumCircuit(n)
    # Don't forget the Swaps!
    for qubit in range(n//2):
        qc.swap(qubit, n-qubit-1)
    for j in range(n):
        for m in range(j):
            qc.cp(-np.pi/float(2**(j-m)), m, j)
    qc.name = "QFT†"
    return qc

def iqft(qc, n):
    qc.append(qft_dagger(len(n)), n)
  • $\begingroup$ Thank you so much! $\endgroup$ Feb 7, 2022 at 20:00

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.