2
$\begingroup$

I'm studying Shor's algorithm using an iterative approach where only one single qubit is used on the upper register and it is recycled $2\log_2(N)$ times ($N$ is the number to factorize).

I have a question about the recycling time in this approach. If I recycle more than $2\log_2(N)$ times, the number of computational basis states would increase, which would be more than $2^{2\log_2(N)}$.

I know that the accuracy of finding the right period would enhance if I recycle further, but I wonder whether the computational speed would decrease if I recycle more and more.

Also, I would like to know if there is a relationship between the success probability of finding the right period and the number of recycling. If so, what kind of relationship is there?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

  1. As for the runtime: Let us disregard issues related to fault tolerance, and so forth, and consider a logical circuit. Let us furthermore fix the group (in your case, we fix $N$ and some generator $g$ of a subgroup of $\mathbb Z_N^*$) and vary only the exponent length $l$: In a typical implementation, you would then evaluate $l$ controlled group operations sequentially quantumly. The evaluation of these controlled group operations dominates the runtime. So in such an implementation the runtime is essentially linear in $l$.

    (I am not quite sure what you mean by the number of computational basis states increasing, because when you use the semi-classical QFT, and recycle the control qubits, the number of qubits in the circuit remains the same even if you increase the exponent length.)

  2. As for the success probability (of recovering a non-trivial divisor of the order $r$ of $g$), it grows fairly sharply as you increase the exponent length: For an analysis, see for instance [BW07] [BW06p]. Note however that you may achieve a very high success probability (of recovering $r$, and the complete factorization of $N$) by instead searching a bit in the classical post-processing, so in practice you do not want/need to increase the exponent length: See [E22p] for an analysis and further details.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. I have a question for the number 1 answer. I found in the following paper that the quthors factored 15 with ququarts YC22. Using ququarts, the exponent length can be reduced, but in this case, the number of computational basis is 4, which is twice of qubits. In this case, even though the exponent length has been reduced twice, since the computational basis is twice larger, isn't the computational speed the same as that of qubit case? $\endgroup$
    – Alex
    Apr 3 at 14:33
  • $\begingroup$ Your follow-up question is related to specific details regarding how the logical circuit is implemented physically, whereas my original answer pertains to higher levels of the stack. Also, when I write exponent length, I mean the length of the exponent to which g is raised in the mathematical description of the algorithm — i.e. at the top level of the stack. The exponent length does not change at lower levels of the stack. $\endgroup$
    – Martin Ekerå
    Apr 3 at 16:36
  • $\begingroup$ Oh, there is a confusion a bit. Let me rephrase my question again. In the following paper YC22. The authors factored 15 using ququarts, and they achieved the reduction of the iteration, which is twice fewer than that of qubits, saying that their computational speed is twice faster than using qubits. In this case, even though the iteration number has been reduced twice compared to qubits, since the computational basis is twice larger, isn't the computational speed the same as that of qubit case? $\endgroup$
    – Alex
    Apr 3 at 16:44
  • $\begingroup$ I think maybe you should ask a separate question if you have a longer follow-up question regarding a specific paper. I did not read the paper you refer to in detail. In short, the runtime should be essentially linear in the exponent length, for the reason I give and in the kind of implementation I consider in my original answer. $\endgroup$
    – Martin Ekerå
    Apr 3 at 17:05

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.