23

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 & Bryans (2014) arXiv:1411.6758
  • [4] Zalka (2008) arXiv:quant-ph/0601097
  • [5] Cao & Luo "Comment on: Realization of a scalable Shor algorithm"
user1271772
  • 541
  • 3
  • 16
  • 5
    Depends on what you mean by "scalable". Some of the criticisms of Cao and Liu seem quite nit-picky. For example, one of their criticisms is that Kitaev did not claim that you could use only one qubit in the paper cited for this result. They don't seem to investigate whether this claim itself is actually true or false. Kitaev's algorithm can in fact be modified to use only one qubit, as the Science paper claims, even though this claim does not seem to be in Kitaev's paper on his algorithm. – Peter Shor Dec 08 '16 at 13:23
  • 1
    @PeterShor, what an honor to hear from you! Ok so the authors (correctly) extended the results of Kitaev's paper to make it possible with one qubit, and Cao & Liu complain that they call it "Kitaev's algorithm" rather than "modified Kitaev algorithm or something like that". However, they also say that the complexity argument no longer holds when the QFT is turned into the "semi-classical QFT". I a still a student when it comes to this type of analysis so I would appreciate input. Is the complexity still O(log n)^3 ? Is it still "scalable" in terms of being polynomial, or at least < GNFS ? – user1271772 Dec 08 '16 at 13:55
  • 4
    I'll let somebody else answer this, as people might claim I'm biased. But let me point out that the authors of the Science paper didn't extend Kitaev's algorithm ... it's a well-known extension. They merely didn't cite the correct reference. – Peter Shor Dec 08 '16 at 14:14
  • @D.W. About reference [2]. Thank you for your comment! I am not sure how to fix this. However, I believe it is straightforward to look for the Zalka paper in the reference [2] bibliography, and then see that when Zalka's paper was cited in reference [2], the authors were saying that it was Zalka's paper that lead them to the conclusion that factoring 15 requires at least 8 qubits. This however doesn't even seem necessary, because it is clear from Table 1 of reference [2] that they claimed factoring 15 requires 8 qubits, and then I took the time to summarize exactly how Zalka's paper leads to 8 – user1271772 Dec 08 '16 at 14:34
  • @D.W. If you have any ideas how to improve my reference [2] issue, I would welcome your advice (or edit). Neither Zalka's paper nor reference [2] explicitly explains why factoring 15 requires 8 qubits, but Zalka's paper gives the formula that I've repeated in my question, and then I have taken the time to substitute in the numbers and arrive at 8 qubits. :) – user1271772 Dec 08 '16 at 14:36
  • 5
    These formulas that arrive at 8 qubits take some specific implementation of Shor's algorithm and calculate how many qubits that implementation takes. They do not claim that this is the best possible implementation. – Peter Shor Dec 15 '16 at 15:29
  • @PeterShor: Absolutely, however the 8-qubit scheme of Zalka's paper (reference [4] in the question) seems to preserve the O(log(n)^3) scaling of the overall algorithm, whereas the Cao & Liu paper argues that by replacing the M qubit QFT with a 1 qubit "semiclassical QFT", the O(log(n)^3) scaling argument is lost. The question is whether or not there is merit to that claim (that the scaling deteriorates by replacing the M-qubit QFT this way) ? – user1271772 Dec 15 '16 at 20:34
  • 2
    @user1271772 This was flagged for moderation attention on the basis of you being one of the authors mentioned in your own post. Not that that's bad, some self-advertisement is an unavoidable part of science, but maybe best to be clear about it? – Bjørn Kjos-Hanssen Feb 24 '19 at 05:46
  • What happened was that a moderator broke the moderator agreement contract that they signed when they took the role. I was user1271772 until well into 2020, so that flag in Feb 2019 is evidence of a violation of contract (don't worry, I know who it was). Anyway: I'm not praising my own work or anything like that, in this question. – user1271772 May 03 '21 at 23:01

1 Answers1

13

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.

Peter Shor
  • 24,763
  • 4
  • 93
  • 133
  • Your answer does not tell us why outputting one bit at a time does not affect the (log n)^3 operation count. Can it be explained why the overhead cost suffered by outputting one bit at a time is less than O(log n)^3 ? – user1271772 Jan 09 '17 at 06:37
  • 1
    Please show me where in Cao and Luo's paper they say that outputting one bit at a time affects the operation cost. If I am reading their paper correctly, *they do not.* I think I have adequately refuted their criticism. – Peter Shor Jan 09 '17 at 14:02
  • 2
    Their criticisms are (1) if you only have one bit of output, then the continued fractions algorithm does not work. This is refuted by noticing that you actually have more than one bit of output. (2) if you only have one bit of output, then the probabilities for each output $c$ are incorrect. This again is refuted by noticing that you actually have more than one bit of output. (3) the only multiplication circuits used were ones that multiply $x\cdot t$, where $t$ is a fixed number precomputed into the multiplication circuit. I didn't refute this in my answer, but this is all you need to factor. – Peter Shor Jan 09 '17 at 14:07
  • 2
    I am not going to go through the circuit for one-qubit output phase estimation and explain why the relatively small change needed to accomplish this does not affect the time complexity. It's the "semi-classical" modification described on page 2 of Parker and Plenio's paper, Efficient factorization with a single pure qubit and log N mixed qubits. – Peter Shor Jan 09 '17 at 14:23