11
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You can't factor numbers <15 with Shor's algorithm. $\endgroup$
    – Norbert Schuch
    Sep 29, 2019 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, 2019 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, 2019 at 18:16
  • $\begingroup$ Okay, you're right, I changed the title. Do you have an implementation to propose? $\endgroup$
    – WaSon
    Sep 29, 2019 at 19:44
  • $\begingroup$ I had exactly the same challenge. After researching for months, I built a general implementation in QISKIT, that runs on the simulator, with 14 qubits. But when I started this on real hardware, I got error messages. But one of the reasons for failing might be the execution time that the akgorithm needs. Not only the number of qubits, also the processing time is a criteria if an algorithm can be executed on real hardware. Finally, I gave up and could only run it on the simulator. But I could share the geberal qiskit algorithm, if you're still searching for that. $\endgroup$
    – mbuchberger1967
    May 2, 2020 at 23:35

1 Answer 1

Reset to default
3
$\begingroup$

Yes it is possible! However you need to make some small changes to the circuit. In the paper An Experimental Study of Shor's Factoring Algorithm on IBM Q

They have factored 12,21 and 35 using something called the Kitaev approach. In Shor's algorithm, you perform the QFT in such a manner that the entire answer is given to you at once. However if you instead have a circuit where bit of the answer is given out one at a time, you can drastically reduce the number of required qubits. For example in this paper the number 15 is factored using only 5 qubits. Actually all experimental implementations of Shor's algorithm have been using the Kitaev approach, as otherwise far too many qubits are needed.

Improve this answer
$\endgroup$

Your Answer

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

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