# How to make a Shor's algorithm for an arbitrary number of qubits with Qiskit on a IBM machine?

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?

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!

• Thanks very much! And yes, the circuits are indeed huge hahaha Jan 17 '20 at 0:08