So suppose you want to do a Shor algorithm on an arbitrary number of qubits using an arbitrary $a$ (the base number in the periodic function $a^x \mod c$) and $c$ ( the factored number). Making the IQFT is easy for an arbitrary number of qubits because it has a clear pattern and it uses only Hadamard and controlled phase shifts gates. But what about the permutation gate that multiplies the function? I can make one for a 7 qubits Shor with 3 qubits $x$ and 4 qubits $f(x)$ using Toffolli gates but I don't know how I can code something that does it automatically for given $c$ and $a$. I also wonder how would you do it for a higher number of qubits. Any help, reading material or pointers on that?


1 Answer 1


Maybe this paper can help you, that's what the implementation in Qiskit is based on.

Otherwise looking at the implementation of Shor's algorithm in Qiskit itself might be insightful. The circuit for the algorithm is constructed in the method construct_circuit and can be visualized with this snippet.

from qiskit.aqua.algorithms import Shor
a, N = 2, 3
shor = Shor(N, a)
circuit = shor.construct_circuit()
print(circuit.draw())  # or circuit.draw(output='mpl') for a nicer looking diagram ;)

Warning: the circuit is huge and takes a long time to plot for large N!

  • $\begingroup$ Thanks very much! And yes, the circuits are indeed huge hahaha $\endgroup$
    – Zeor137
    Jan 17, 2020 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.