23
$\begingroup$

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"
Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Dec 8, 2016 at 13:23
  • 1
    $\begingroup$ @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 ? $\endgroup$
    – user1271772
    Dec 8, 2016 at 13:55
  • 4
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Dec 8, 2016 at 14:14
  • 5
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Dec 15, 2016 at 15:29
  • 2
    $\begingroup$ @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? $\endgroup$
    – Bjørn Kjos-Hanssen ♦
    Feb 24, 2019 at 5:46

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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 ? $\endgroup$
    – user1271772
    Jan 9, 2017 at 6:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Jan 9, 2017 at 14:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Jan 9, 2017 at 14:07
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Jan 9, 2017 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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