Is the 2016 implementation of Shor's algorithm really scalable? In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 of [3]. The 8-qubit requirement comes from the end of [4] which states that the number of qubits needed for factoring an $n$-bit number is $1.5n+2$ which for 15 is $1.5\cdot 4 + 2=8$.

The paper that uses only 5 qubits states that their algorithm "replaces a QFT acting on M qubits with a semiclassical QFT acting repeatedly on a single qubit", but the consequences of this on the complexity of the  algorithm was never mentioned in the paper. 

Now there has been harsh criticism of the paper claiming to factor 15 in a "scalable" way, as they say in Section 2 that the complexity argument for Shor's algorithm no longer holds. However, this criticism has not been corroborated anywhere, and the Science paper keeps getting celebrated as a "scalable" version of Shor's algorithm. What is the complexity of the "scalable" Shor algorithm?


[1] Monz et al. (2016) Science. Vol. 351, Issue 6277, pp. 1068-1070
[2] Smolin et al. (2013) Nature. 499, 163–165
[3] Dattani &amp; Bryans (2014) arXiv:1411.6758
[4] Zalka (2008) arXiv:quant-ph/0601097
[5] Cao &amp; Luo "Comment on: Realization of a scalable Shor algorithm"
The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get 1 bit of output from the algorithm, that's insufficient for factorization. (For one thing, although this isn't their argument, 1 bit clearly does not contain enough information to determine the factors.)

What Cao and Luo seem not to realize is that for the variation of the Fourier transform with only one bit in the first register, the same value of $c$ is output as in the standard factoring algorithm; it's just output one bit at a time.
This change doesn't affect the $O(\log^3 N)$ running time. 

To try to be fair to Cao and Luo, they say that they don't think this algorithm works, and if it does work, then it isn't Shor's algorithm because it doesn't exactly match the algorithm described in the original factoring paper. A quote from their paper: 


  Finally, we would like to stress that if the implementation is indeed credible then it would be a new quantum factoring algorithm, not the Shor algorithm, because all requirements of the original Shor’s algorithm are not satisfied.


And indeed, it's not the algorithm from my original factoring paper. It uses the phase estimation procedure from Kitaev's factoring algorithm, and a variant on that, discovered by Griffiths and Niu (not by Parker and Plenio, as I said in a previous edit of this answer) that lets the algorithm output the estimate of the phase one bit at a time.