# I have question about cost of 'modular multiplication unitary' in Shor's algorithm

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.

New contributor
maar hybrid is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

## 1 Answer

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.

• Let me explain more specifically. For example, when a=7 and N=15, then unitary gate in 4 qubit will be x(0)x(1)x(2)x(3)cx(1,2)cx(2,1)cx(1,2)cx(2,3)cx(3,2)cx(2,3)cx(0,3)cx(3,0)cx(0,3). So, to implement U_7, there must be preprocessing to find way to implement U_7. My main question is this preprocessing can be calculated polynomial time with qubit number or exponential time with qubit number May 10 at 7:31
• I know main idea of shor algorithm is (U_a)^k is same with U_(a^k) but my question is U_a or U_(a^k) can be prepared in polynomial time May 10 at 7:38