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'][0]))

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'
  • 1
    $\begingroup$ 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. $\endgroup$
    – cnada
    Mar 9, 2020 at 7:14
  • $\begingroup$ 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 $\endgroup$ Mar 9, 2020 at 7:32

1 Answer 1


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.

  • $\begingroup$ 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 $\endgroup$ Mar 9, 2020 at 13:05

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.