1
$\begingroup$

I read some articles about Shor's algorithm but I can't understand how it works. From my point of view it makes the problem even more complex from O(2^n) to O(n!). How does the oracle that is suppose to solve the modular division simultaneously calculate $r_x \equiv a^x \pmod N$ for all $x$s between $0$ to $2^n$ without permutating?

If $x_j=\sum_i 2^i$, Isn't n! permutations on j needed?! $$r_x \equiv a^{x} \pmod N = \prod_{j \subseteq \{ i \}} a^{2^i} \pmod N$$

I'm not a native English speaker please edit my question to be accurate.

$\endgroup$
1
  • $\begingroup$ The simultaneous calculation is possible thanks to superposition of inputs. In other words, you calculate all the functions outputs for all inputs at once. $\endgroup$ Commented Aug 20, 2022 at 7:10

1 Answer 1

4
$\begingroup$

It appears you may have entirely misunderstood or are not aware of several fundamental concepts of quantum computation, namely: superposition and quantum parallelism.

I will not try to explain how Shor's algorithm works because I'm certain any introductory book will do a better job. However, I highly recommend first understanding well the precursor algorithms such as the Deutsch algorithm, Deutsch-Jozsa algorithm and Simon's algorithm and only then start looking into Shor's algorithm. These algorithms are relatively simpler than Shor's algorithm and introduce necessary concepts.

Also, you might want to review your math equations as they don't make much sense.

$\endgroup$

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.