# Can the paper by Monz et al. (2015) be regarded as a real implementation of Shor's algorithm?

I'm studying about the Shor algorithm and I wonder whether the paper below can be regarded as a real implementation of the Shor algorithm:

https://arxiv.org/abs/1507.08852

In this paper, they tried to recycle the first register 2 times for factoring 15 so that they can realize 3 qubits in the first register.

But for implementing the Shor algorithm without any prior knowledge and satisfying the best approximation condition of the continued fraction expansion algorithm, shouldn't it be recycled 7 times so that it can satisfy 8 qubits (which is the requirement for factoring 15)?

Also, I wonder whether applying the optimization process on the unitary operator where the initial quantum state in the second register is changed is reasonable generally and can be regarded as part of the modular exponentiation (this has been applied in every Shor algorithm experiment, of course in the above paper too). If so, can we regard the Fig 1.(b) case in the above paper as a real implementation of the Shor's algorithm WHEN the first register is recycled 7 times?

It's fundamentally not possible to demonstrate "scalable" factoring by doing $$n=15$$. If the approach was so scalable, it should have actually scaled up and done larger numbers!

In my opinion, a "scalable" system should be able to factor any number less than 1000. And it should be able to factor this number that's less than 1000 reliably; using less than 5 runs of the quantum part of Shor's algorithm (on average). For numbers larger than 1000, more than 5 attempts would be okay, but not too much more. Otherwise rolling dice, instead of running the quantum computer, would work just as well. This is actually extremely demanding: it implies the ability to do tens of thousands of gates without a bit flip or phase flip error changing the outcome.

I wonder whether applying the optimization process on the unitary operator where the initial quantum state in the second register is changed is reasonable generally

This optimization is totally valid; it works on all cases. But, when factoring big numbers, this optimization affects such a tiny fraction of the computation that it's completely irrelevant. Whereas, for the paper you cited, this optimization is removing 30% of the circuit! This is an optimization whose benefits don't scale.

shouldn't [the ancilla] be recycled 7 times [instead of 2]?

Yes, I think they should have done 8 multiplications instead of 3 if they wanted to claim they were "really" doing Shor's algorithm.