2
$\begingroup$

I am trying to implement Shor's algorithm using modular exponentiation as described in this paper: https://arxiv.org/abs/quant-ph/0205095

The issue is found when trying to implement CMULT($a^{-1}$)mod(N) Controlled U gate

Since we can only use integers, do you know how to inject $a^{-1}$ into the algorithm?

$\endgroup$
2
  • $\begingroup$ Just idea based on equation no 3. It seems that the gate you are looking for is just CMULT a MOD n taken in inverse order. In other words, it uncomputes the ancilla qubits back to zero state. $\endgroup$ Feb 1 at 7:21
  • 1
    $\begingroup$ @MartinVesely I thoght that at the begining, but when using the inverse of CMULT(a)mod N I realized that the result is (b-ax)mod N (in the particular case of the enclosed image is (0-ax)mod N. Therefore there should be a mean to inject a^-1 into the algortihm... In any case, I think I am missing something here... $\endgroup$ Feb 1 at 15:54

2 Answers 2

3
$\begingroup$

$a^{-1}$ is an integer, because you're working in modular arithmetic.

$a^{-1}$ is the value that satisfies $a \cdot a^{-1} = 1$. For example, on a clock, 5-oclock times 5-oclock equals 25-oclock which is the same as 1-oclock so a solution to $5x = 1 \pmod{12}$ is $x=5$ meaning $5^{-1} = 5 \pmod{12}$.

In python you can compute multiplicative inverses mod N by using pow:

N = 101*103
a = 52
a_inv = pow(a, -1, N)
print(a_inv)  # 3401
print(a * a_inv)  # 176852
print(a * a_inv % N)  # 1
$\endgroup$
1
  • $\begingroup$ Clear explanation, thank you so much! This is exactly what I didn't understand of this sentence in the paper: "The value a^−1, which is the inverse of a modulo N, is computable classically in polynomial time using Euclid’s algorithm and it always exists since gcd(a, N) = 1". $\endgroup$ Feb 2 at 16:02
3
$\begingroup$

Given two coprime integers $a$ and $N$, you can compute $a^{-1} \text{ mod } N$ efficiently classically by using the extended Euclidean algorithm even if the factorization of $N$ is unknown. This is what saves you.

To see this easily, note that said algorithm gives you integers $u, v$ and $d$ such that $ua + vN = d = \gcd(a, N) = 1$. It follows that $ua \equiv 1 \:\: (\text{mod } N)$ and hence that $u \equiv a^{-1} \:\: (\text{mod } N)$.

(Note also that had we know the order $r$ of $a$ perceived as an element of a cyclic subgroup to $\mathbb Z_N^*$, then we could have used that $a^{-1} \equiv a^{r-1} \:\: (\text{mod } N)$ to find the inverse $a^{-1} \text{ mod } N$. This technique generalizes to any cyclic group, and so may be useful for taking inverses efficiently classically when implementing Shor's algorithm for computing discrete logarithms — if needed to implement the arithmetic, and if the group in question does not admit a more efficient algorithm for taking inverses. But in Shor's order-finding algorithm, the order $r$ of $a$ can of course not be assumed to be classically known.)

$\endgroup$

Your Answer

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

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