I would like to ask whether the entanglement verification is necessary in Shor's algorithm

In the paper, Nature Photon 6, 773–776 (2012), they mentioned that they tried to factorize 21 to avoid the entanglement verification, but I'm not sure why this verification can be avoided.

Are there any certain numbers that don't require entanglement verification process? If so, could you please let me know the reason?


In the abstract of this paper they say

The algorithmic output is distinguishable from noise, in contrast to previous demonstrations.

The previous demonstrations seem to be claims to have factored $15$.

Shor's algorithm works (slowly) even if your "quantum" computer has a coherence time of zero. The reason is that it runs the quantum subroutine in a loop, classically checking the output until it finds a factor. If the qubits are effectively classical (measured after every gate operation), then the output of the quantum subroutine will be uniformly random, and eventually it will be correct.

If you're factoring a large number, then the algorithm terminating in less than the age of the universe proves that your quantum computer is working. If you're factoring a tiny number that could be factored instantaneously by trial division, then Shor's algorithm terminating by itself proves nothing. You need some other evidence that the computation is really quantum, such as the frequency distribution of different outputs.

It's somewhat moot, though, because neither this paper nor the previous demonstrations actually implemented Shor's algorithm. Their quantum computers couldn't even store the number they claimed to factor, much less do modular exponentiation. There may have been merit to the experiments from an engineering perspective, but tying them to Shor's algorithm was just clickbait. See Smolin, Smith and Vargo, "Oversimplifying quantum factoring" and Dattani and Bryans, "Quantum factorization of 56153 with only 4 qubits".

  • $\begingroup$ Thank you for your comment. I have some questions in your comment. Why showing the frequency distribution of different outputs is quantum nature? And I cannot understand the meaning of the last sentence "Their quantum computers couldn't even store the number they claimed to factor, much less do modular exponentiation". Could you please explain these two things again? $\endgroup$
    – James
    Jun 14 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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