2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You may find the paper Circuit for Shor's algorithm using 2n+3 qubits useful $\endgroup$
    – epelaez
    May 2, 2022 at 17:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asimonu
    May 3, 2022 at 7:03

2 Answers 2

Reset to default
1
$\begingroup$

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:

enter image description here

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Asimonu
    May 3, 2022 at 15:08
  • 1
    $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    May 3, 2022 at 15:34
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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