Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Here modular multiplication unitary means $U_a : |s\rangle \to|as\mod N\rangle$.
My main question is, can the modular multiplication unitary $U_a$ can be constructed in time polynomial in the number of qubits $n$ for any $a$ and $N$? Or is this an open question? I cannot find a method or proof of implementing modular multiplication unitary fast.
The point is that you can perform this calculation efficiently on a classical computer. So you can implement the same algorithm on a quantum computer. Just think: if you had to do this calculation by hand, how would you do it? This gives you an algorithm, which you can make reversible, and this can be directly implemented on a quantum computer.
In fact, the more relevant question is how to efficiently implement $U_a^k$ for any integer $k$: it's not good enough to implement $U_a$ $k$ times. But, again, this can be done classically and therefore you can implement the same thing on a quantum computer. Other questions on this site have asked that before if you want detail.
