3
$\begingroup$

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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank your for your reply! May I ask you which part has been removed in their paper? $\endgroup$
    – Alex
    Jun 29, 2022 at 21:10
  • $\begingroup$ The fact that the first two operations are simpler than the last one is the part that was "removed". It's perfectly valid as an optimization, but in larger cases reducing the cost of the first two multiplications is just negligible because there are so many multiplications total. $\endgroup$
    – Craig Gidney
    Jun 29, 2022 at 23:56
  • $\begingroup$ Why does it have to be "using less than 5 runs"? $\endgroup$
    – user1271772 No more free time
    Apr 15, 2023 at 19:07
  • $\begingroup$ @user1271772 the reason for the limit on the number of runs is to prevent solving the problem by random guessing. For semiprimes N between 100 and 1000, if you pick a random number 32 times and compute its gcd versus N, you're likely to find a factor of N just by luck. Limiting it to 5 keeps you well away from that degenerate solution. $\endgroup$
    – Craig Gidney
    Apr 15, 2023 at 19:47
  • $\begingroup$ There's 143 primes between 100 and 1000, so why is it that the quantum computer should only be allowed to run Shor's algorithm 5 times? $\endgroup$
    – user1271772 No more free time
    Apr 15, 2023 at 19:56

Your Answer

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

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