Question about Controlled Modulo Quantum Gate

Question

How does the Ux(x, N) function implements Ux|y> -> |xy mod N> ?

import numpy as np
import cirq

def Ux(x,N):

    k=1
    while(N>2**k):
        k=k+1
        
    u = np.zeros([2**k, 2**k], dtype = int) 

    for i in range(N):
        u[x*i%N][i]=1
    for i in range(N,2**k):
        u[i][i]=1
        

    XU = cirq.MatrixGate(u).controlled()
    return XU

Answer 1

The function $Ux$ creates a unitary operator that performs: $Ux|y⟩ = |xy\ (mod\ N)⟩ $. It is doing that by computing the matrix operator $u$ needed for applying such an action upon an input vector.

Let's go through that step by step:

k=1
while(N>2**k):
    k=k+1

This implies that a binary representation for $N$ is consisted of $k$ bits. A binary string of length $k$ has $2^k$ possible values.

---

u = np.zeros([2**k, 2**k], dtype = int)

A numpy array of dimensions $2^k \times 2^k$ is being created with zero entries everywhere.

---

for i in range(N):
    u[x*i%N][i]=1

Here we are building the matrix operator $u$. The action of this matrix operator $u$ upon an input vector $|y⟩$ is essentially - from a mathematical point of view - just a multiplication of the input vector $|y⟩$ by the matrix operator $u$. Mathematically each entry in $|y⟩$ is being manipulated by the corresponding row in $u$.

To clarify this functionality, let's consider a simple example of a vector multiplication by a matrix:

$\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0\cdot1 + 1\cdot0 \\ 1\cdot1 + 0\cdot0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}$

Each entry in the result vector is just a manipulation of the entries in the input vector, "coded" by the rows of the matrix operator.

Now let's go back to our issue. This for loop quoted above goes through all possible discrete values from $0$ to $N-1$ and sets up the corresponding rows in the matrix operator $u$ such that each entry $xi\ (mod\ N)$ in the input vector $|y⟩$ gets the value of the $i$ entry. Each entry $i$ in $|y⟩$ gets a "jump-ahead" of $xi\ (mod\ N)$ - and this is exactly what we wanted! We achieved $xy\ (mod\ N)$.

---

The remaining parts are peanuts. But we will go through them quickly:

for i in range(N,2**k):
    u[i][i]=1

Since $|y⟩$ contains $2^k$ entries which may be more than $N$ entries, we simply set the remaning $2^k - N$ rows corresponding with the redundant entries to be "identity rows" which essentially do nothing.

Now we can introduce an example for $u$ that should emphasize and demonstrate the explanations above. If we call Ux(x = 3, N = 5) then $u$ is:

Try to examine this result and understand how all the explanations above are coming true here.

---

XU = cirq.MatrixGate(u).controlled()

This command builds a Gate object (a controlled version in this case) in cirq from the unitary matrix operator $u$ that we have computed. You can see the exact functionality of these methods here.