I'm trying to simulate Shor's algorithm with a model using vectors for quantum registers and matrices for quantum gates, however I'm stuck at the modular exponentiation bit of Shor's algorithm, having no idea how to build the corresponding matrix (unlike Hadamard and QFT). How can I build said matrix?


Note that Shor's algorithm doesn't require modular exponentiation. All you need is (controlled) modular multiplication.

There are two steps to getting the matrix for modular multiplication:

  1. Write a function to turn any permutation into a matrix.

  2. Apply it to the permutation $a \rightarrow a \cdot k \pmod{r}$.

  3. (Optional) Instead of making that matrix and multiplying by it, save massive execution time by just applying the permutation directly.

For step 1, just have a function like this:

import numpy as np

def make_permutation_matrix(n, permutation):
    r = np.zeros((n, n))
    for i in range(n):
        r[permutation(i), i] = 1
    return r

Then for step 2, use it:

import math
k = pow(base, exponent, modulus)
n = math.ceil(math.log(modulus, 2))
mul_matrix = make_permutation_matrix(
    permutation=lambda x: x*k % modulus)
| cite | improve this answer | |

Your Answer

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

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