I need to make a general implementation of Shor's algorithm that factors, at least, N = 15. I have been able to perform an implementation that works in simulators, with ProjectQ, but when running it on a real quantum computer.

I have decided to try it using Qiskit. Currently, I'm trying to find the first implementations in Qiskit, to see if it's possible to do what I want because I already doubt it.

I have tried, among others, whit these implementations. Also with IBM's own implementation. But either they use too many qubits 4n+2, which for N = 15 would be 18 qubits, and the public quantum computer with more qubits has only 14, or they use several measurements in the same qubit, which is not supported by IBM quantum computers. Now, I just want to know if it is possible to do what I want with current computers and how. I have read many papers, but their conclusions and methods are not supported by the current publicly available quantum computers, or the maximum N that they can factor is less than 15.

Thank you in advance. Greetings.

  • $\begingroup$ You can't factor numbers <15 with Shor's algorithm. $\endgroup$ – Norbert Schuch Sep 29 '19 at 14:12
  • $\begingroup$ I think you can, but 15 is the first non-trivial N. Likewise, I look for factorizer N = 15, but with an implementation that, if there is a quantum computer powerful enough and with enough qubits, you could factor any N. $\endgroup$ – WaSon Sep 29 '19 at 17:55
  • 1
    $\begingroup$ Shor's algorithm only applies to (i) odd numbers which (ii) are not prime powers. 15 is the first such number. $\endgroup$ – Norbert Schuch Sep 29 '19 at 18:16
  • $\begingroup$ Okay, you're right, I changed the title. Do you have an implementation to propose? $\endgroup$ – WaSon Sep 29 '19 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.