I'm implementing Shor's algorithm from scratch and therefore want to implement a unitary gate $U$ such that $U^{2^j}|y\rangle = |a^{2^j}y \: \text{mod} \: N\rangle$. I know that an efficient way of doing this is by following the procedure presented by Stephane Beauregard in Circuit for Shor's algorithm using 2n+3 qubits; and this is what I'm going to be using.

Out of curiosity, I wanted to know if there is any way of building these unitaries without resorting to some clever insights like done in the paper or other efficient implementations, i.e. if there is something more beginner friendly. I was specifically wondering if there is a way of constructing the matrix for $U^{2^j}$ and then just use Qiskit's unitary to gate function. I know this would be very inefficient, but does anyone know how to do this?

I found this answer that does what I'm asking but it relies on already knowing the order $r$. Is there some way to do it for any $a$ and $N$ without having to know the order of $a^x \: \text{mod} \: N$ beforehand?

  • 1
    $\begingroup$ You might find github.com/Strilanc/PaperImpl-2017-DirtyPeriodFinding handy. It has python code that decomposes the entire powmod circuit using ProjectQ. $\endgroup$ Jun 15, 2021 at 0:32
  • $\begingroup$ Thanks @CraigGidney! Is there some specific file/part I should look into? Or some specific section of the paper? $\endgroup$
    – flyingpig
    Jun 15, 2021 at 0:38
  • $\begingroup$ The page I linked you to has a table going over the constructions. $\endgroup$ Jun 15, 2021 at 1:15
  • $\begingroup$ I'll look into it, thanks $\endgroup$
    – flyingpig
    Jun 15, 2021 at 1:16


Your Answer

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