11

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.

WaSon
  • 111
  • 4

1 Answers1

3

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.

Martin Vesely
  • 15,244
  • 4
  • 32
  • 75
siddg
  • 51
  • 3