0
$\begingroup$

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
$\endgroup$

1 Answer 1

2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Should it be while(N < 2**k) instead of while(N > 2**k) ? $\endgroup$
    – kevin
    Aug 11 at 0:44
  • 1
    $\begingroup$ No. this loop counts the amount of bits needed for writing $N$ as a binary number. For example, if $N = 5$ then in binary $N = 101$, i.e 3 bits. In this case the loop would run 2 times (for $k = 1$ and $k = 2$) and in the third time (when $k = 3$) it halts - and we got the number of bits as the value of k. A more elegant and efficient way to do the same thing is replacing this loop with this 1 row: k = int(math.log(N, 2) + 1). $\endgroup$
    – Ohad
    Aug 11 at 6:08

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.