10
$\begingroup$

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem or period of modular exponentiation sequence of some random $x$ such that $1 < x < N$.

I have no problem regarding the idea of the algorithm. But I'm wondering if Shor’s algorithm creates such a sequence by repeated squaring (which is an efficient way classically). In my understanding, the term "efficient" means that the complexity of the algorithm is polynomial in time.

Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered $x^{r} = 1 \ \text{mod} N$? During the creation process, it should not increase complexity to exponential-time, right?

Why bother with quantum Fourier transform at all? Did I misunderstand it in some way?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hi, Poramet. Welcome to Quantum Computing SE! Please only ask one question per post - only ask several if they are so closely related that it wouldn't make sense to split them up since they cannot reasonably be answered separately. That way, answerers that might be able to answer one question but not the others still can provide useful, complete answers to a question. Review How to write a good question?. $\endgroup$
    – Sanchayan Dutta
    Commented Feb 7, 2019 at 7:37
  • 1
    $\begingroup$ I've edited your post to remove the second question (v5 is still visible here). Please ask that as a separate question if necessary. $\endgroup$
    – Sanchayan Dutta
    Commented Feb 7, 2019 at 7:39

2 Answers 2

Reset to default
8
$\begingroup$

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many times does each have to evaluate the function.

For the classical algorithm you're suggesting, you'd calculate $a\text{ mod }N$, and $a^2\text{ mod }N$, and $a^3\text{ mod }N$, and so on, until you hit a repeating value. You have to perform $r$ evaluations, and $r$ could be quite large. Indeed, it could be $O(N)$. It's this large number of repetitions that kills this idea for the classical algorithm.

By comparison, the quantum algorithm only evaluates the order once. You then need the Quantum Fourier Transform in order to be able to compare all the simultaneously calculated values because you cannot access all of these values all at once. The QFT is what does all the magic.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ When you say $O(N)$ , does it mean I have to run repeated squaring for maybe worse case close to $N$ time and even if the repeated squaring algorithm is a polynomial-time complexity for calculate $x^{a} \text{mod} N$ for one value $a$. It turn out that run the algorithm in $O(N)$ time, will increase complexity to exponential-time? Do I understand correctly? $\endgroup$
    – Poramet Pathumsoot
    Commented Feb 7, 2019 at 16:13
  • 2
    $\begingroup$ @PorametPathumsoot Yes, exactly (because complexity is measured based on the number of bits of input, $n=\log_2(N)$, so $N$ is exponential in $n$. $\endgroup$
    – DaftWullie
    Commented Feb 7, 2019 at 20:44
4
$\begingroup$

Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered $x^{r} = 1 \ \text{mod} N$? During the creation process, it should not increase complexity to exponential-time, right?

Why bother with quantum Fourier transform at all? Did I misunderstand it in some way?

The answer to the above question is that there exists no known classical (non-quantum) algorithm that can find this period efficiently (in polynomial complexity). So that means there is no efficient classical algorithm to find the period of functions like $x = 2^r_{1} \ \text{mod} N$. That is not to say such a classical algorithm does not exist – just that no one knows such a classical algorithm.

The classical discrete Fourier transform has exponential complexity – however, the quantum version of that Fourier transform has polynomial complexity. So we do need to bother with the quantum Fourier transform.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry for my bad English, I tried to edit that on post, don’t know if it help or not. Before I come to ask the questions I have read some papers and get the answer that there is no classical algorithm known that can find the period efficiently. But since by repeated squaring one can create the sequence efficiently then if one just add check statement "if $x^r = 1 mod N$ or not" during the process of creating, is this still efficiently way to find the period or not, if not then what is the problem. Thank you $\endgroup$
    – Poramet Pathumsoot
    Commented Feb 7, 2019 at 7:21
  • $\begingroup$ Hi, Learner. Welcome to Quantum Computing! I've edited your answer a bit to match the current version (v8) of the question. $\endgroup$
    – Sanchayan Dutta
    Commented Feb 7, 2019 at 7:47

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.