# How many Qubits does the qiskit implementation of Shor's Algorithm need to factor N=15?

I know there is a documentation for qiskit.aqua.algorithms.Shor that explains that they used this reference for implementing the actual circuit. It says that the number of qubit needed is 2n+3. So to factor N=15, 11 qubits would be needed. I decided to test this using Qiskit with a backend that has up to 15 qubits. But then I get an error saying that I needed 18 qubits to factor N = 15. Is the implementation different from the actual paper referenced? or am I missing something ?

This is the code I used to factor N=15

shor = Shor(15,2)
backend = provider.get_backend('ibmq_16_melbourne')
quantum_instance = QuantumInstance(backend, skip_qobj_validation=False)
res = shor.run(quantum_instance)
print("The list of factors of {} as computed by Shor is {}.".format(PRIME, res['factors']))


And this is the error i got

TranspilerError: 'Number of qubits (18) in circuit1 is greater than maximum (15) in the coupling_TranspilerError: 'Number of qubits (18) in circuit1 is greater than maximum (15) in the coupling_map'

• Have you tried running on a different backend like a simulator? If on simulator it uses 11, my guess would be that running on a real hardware instance may have another layer of computation to adapt to the architecture. – cnada Mar 9 at 7:14
• Thankyou for your comment. Yes, I have tried using the qasm_simulator backend it has up to 32 qubits and it does factor N=15, but I don't know if there is a way of checking how many qubits were used in the process. I am now reading about the actual source code of the implementation, and the paper it's based on – MatthewEvans Mar 9 at 7:32

Well actually when looking at the source code, the construct_circuit method:

# quantum register where the sequential QFT is performed

    self._up_qreg = QuantumRegister(2 * self._n, name='up')
# quantum register where the multiplications are made
self._down_qreg = QuantumRegister(self._n, name='down')
# auxiliary quantum register used in addition and multiplication
self._aux_qreg = QuantumRegister(self._n + 2, name='aux')


They use indeed $$4n + 2$$ qubits, so it seems they changed what was proposed in the paper. Some parts were simplified. Check the docstring in the original github repo.

• Thanks a lot !, I figured it was something like that but couldn't find some explanation to it. I guess ill be looking at studying the source code at the original git repo a bit more – MatthewEvans Mar 9 at 13:05