2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – maar hybrid
    May 10 at 7:31
  • $\begingroup$ 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 $\endgroup$
    – maar hybrid
    May 10 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.