High-level Simulation

Addition mod M: (a,b) -> (a,(a+b)%M)

• a and b are m-qubit pieces of an n-qubit register q,

• with n=2m, N=2ⁿ, and M=2^m

  t = copy(q); // temporary copy of q register
  
  for( X = 0; X < N; ++X) // for each element of the state array
  {
    a = X >> m;       // top m bits
    b = X & mask;     // bottom m bits, mask = 2m-1 = 0111..1 (m 1's)
    c = (a + b) % M;  // classical addition
    Y = (a << m) | c; // concatenate the bits
    q[Y] = t[X];      // perform the permutation
  }