# Is it possible to turn modular multiplication into in-place operation?

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 x=2, x=4 or x=6).

Then my question is: is my circuit completely useless to build Shor's algorithm? In case yes, what should I do instead?

• You may find the paper Circuit for Shor's algorithm using 2n+3 qubits useful May 2, 2022 at 17:14
• Excellent, it answers very well to my question, thanks! I was in fact very close to the end, all that was needed is the final clever trick: swap the two registers and apply the adjoint of (b(a^-1)%m) to cancel out the b. May 3, 2022 at 7:03

I thought this question was going to be about whether you can perform the operation $$|k\rangle \rightarrow |k\cdot C \pmod{N}\rangle$$ for classical constants $$C, N$$ using only the $$k$$ register (i.e. do the operation "inplace" as in "without using a secondary register"). Might as well answer that one.

No one knows the answer to this question! If anyone did know how to do it, we could run Shor's algorithm with $$n + O(1)$$ qubits instead of $$2n + O(1)$$. A lot of people have tried to reduce the space usage of Shor's algorithm (including me), so you can at least assume it's publication-worthy to find a quantum circuit that performs this operation inplace (as in with no secondary register).

Note that if $$N$$ was a power of 2, then it would be possible to do it inplace:

The circuit is based on the fact that varying the input bit $$i_j$$ cannot change the output bit $$o_k$$ unless $$k \geq j$$. That property allows you to eat through the register incrementally, but it's not true when $$N$$ is odd. It doesn't work when, for example, $$N$$ is the product of two huge primes like you'd run into for Shor's algorithm.

• Interesting point indeed, as I didn't find such an algorithm I was assuming it wasn't possible (but knowing it's an open question is better). You say $n+O(1)$ could be targeted instead of $2n+O(1)$, isn't there any intermediate enhancement possibility ? Like using a "small" secondary register May 3, 2022 at 15:08
• @asimonu Well, if you knew the factorization of the modulus, you could use the Chinese remainder theorem to do it in smaller pieces. But using that's a catch 22 for a factoring algorithm. There's also an incorrect result by Zalka in arxiv.org/abs/quant-ph/0601097 that claims to do it in 1.5n by finding two n/2 bit numbers which are sort of like factors of $C$, but it ignores the fact that you also need to multiply by the inverses of those numbers and the inverses mod N aren't n/2 bit numbers. May 3, 2022 at 15:34

Okay so the paper epelaaez mentionned answers to the question. The answer it gives is : no, the modular multiplication is not useless. It is even very close to what is needed.

Having the operation $$MultMod(a,mod)$$, the plan is the following:

1. Perform (b,0,0)->(b,a*b%m,0) by applying $$MultMod(a,mod)$$ to b
2. Perform (b,a*b%m,0)->(a*b%m,b,0) with some SWAPs
3. Perform (a*b%m,b,0)->(a*b%m,0,0) by applying the adjoint of $$MultMod(a^{-1},mod)$$, where $$a^{-1}$$ is the modular inverse of a modulo mod, that can be efficiently computed classically. The adjoint simply changes the addition of $$a*b\%mod$$ to the second register to a substraction. This way the second register becomes $$b-(a*b\%mod)*a^{-1}\%mod = b-b = 0$$.

About the remark that some modular multiplications are not reversible: I think it is a relevant point, however, the algorithm moves the problem to the classical part. Indeed, numbers such that their modular multiplication is not reversible don't have a modular inverse, that is they are not prime with the modulo and so the step 3 can't be executed. As in Shor's algorithm it is checked that a and N (the mod) are prime, the problem can't happen.