I began to work on the implementation of Shor's algorithm with a custom value for the modulo. Despite some questions have already been asked about it here, I don't manage to get a complete example or at least a satisfying idea of what I should do regarding the
U matrix performing the modular multiplication or exponentiation.
I implemented a circuit to perform the classic-quantum operation
a * b % m were a and m are classic and x is in a quantum register. It requires 2n+2 qubits, were n is the number of bits required to represent m. To operate, it applies a shift and add approach with a modular add operator, and at each step an external classic modulo is applied to the shifted value of a before the addition.
The problem is that this circuit performs the operation
(b,0,0)->(b,a*b%m,0) (the last value being the ancilliae qubits). However, I think here b can be seen as a dirty register, because when using Shor's algorithm, we would need to get rid of it to apply the multiplication several times. I guess the ideal operation would then be
(b,0,0)->(a*b%m,0,0). This is probably in general impossible, because modular multiplication is not always reversible (e.g.
x*4%8=0 can lead to
Then my question is: is my circuit completely useless to build Shor's algorithm? In case yes, what should I do instead?