1
$\begingroup$

I was reading about the Jordan gradient algorithm(https://arxiv.org/pdf/quant-ph/0405146.pdf) and I am a bit confused about one of the phrases:

Next, use the blackbox to compute f and add it modulo $N_0$ into the output register

For context, the Jordan gradient function calculates the gradient vector of a function or blackbox. The blackbox has an output of $N_0$ qubits

What exactly does

add it ..... into the output register

mean?

Thanks

$\endgroup$
4
  • $\begingroup$ Do you understand what x modulo y means? Example 71 modulo 9 = 8. $\endgroup$
    – Mauricio
    Sep 1, 2022 at 17:18
  • $\begingroup$ Yes. I'm confused what it means by add it to the register $\endgroup$ Sep 1, 2022 at 17:52
  • $\begingroup$ Here is an example: If register is $r=3$, $r+x \pmod y = 3+ 71 \pmod 9= 74 \pmod 9=2$. Where as before $x=71$ and $y=9$. $\endgroup$
    – Mauricio
    Sep 1, 2022 at 17:54
  • $\begingroup$ Could you add a circuit diagram, please? $\endgroup$ Sep 1, 2022 at 20:48

1 Answer 1

2
$\begingroup$

If we understand what modular arithmetic is, I assume the question is how do we implement this in a quantum circuit?

Let's consider the simple 2-qubits case first (mod-2 addition):

The functionality of the $CNOT$ gate is writing the mod-2 addition product to the target qubit. Consider a quantum circuit with 2 qubits $q_o = x, q_1 = y$, then $CNOT(q_0,q_1)$ writes $q_1 = y \oplus x = y + x\ (mod\ 2)$:

enter image description here

CNOT circuit diagram and truth table, from the CNOT wikipedia value.

Implementing mod-y addition:

Well, it's not that simple to implement mod-y addition (and adders in general) in a qunatum circuit. There are various methods to do that, and I am not sure there is a systematic method that can be applied for any arbitrary $y$ (Take a look at this QCSE post).

However, I like to get intuition for this by thinking about the operator being applied upon the target register in such mod-y addition. Ultimately, the operator being applied on the target register is not more than a permutation matrix. I will try to emphasize what I mean by taking an example of a target register consisted of $n = 2$ qubits and its statevector is $|\psi\rangle \in \mathbb{C}^{N = 4}$. Then "writing" some value $x\ (mod \ 4)$ to this register is equivalent to one of the following operators $U[x\ (mod\ 4)]$:

$$ U(0) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \ \ \ \ U(1) = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

$$ U(2) = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \ \ \ \ U(3) = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$

Take a look at the matrices and understand how they permute the amplitudes of $|\psi\rangle$, which is essentially the modular addition operation. Those matrices are surely unitary so they can be implemented with quantum gates ($U(2)$ for example is fairly easy to implement with $X \otimes I$).

Edit - $x\ (mod\ y)$ permutation matrices:

I am adding this part as an answer to the questions in the comments. First, I would like to emphasize again that I have just proposed a method to get intuition for the general case of modular-addition, it helps me personally - Maybe it can help you as well. However for implementing an actual adder one needs to construct an adequate circuit.

However, regarding your question about the $3$ qubits case - What is the matrix representation for $x + 3\ (mod\ 5)$ - If $x$ is the value of the register than the following matrix operator is what you are looking for:

$$U_{3\ (mod\ 5)} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$$

I have wrote a little piece of code in Qiskit that generates modular addition operators that you can use for developing your intuition:

import numpy as np
import math
from qiskit.quantum_info import Operator

def generate_x_mod_y_AdditionOperators(x, y):
    N = 2 ** int(math.ceil(math.log(y, 2)))
    u = np.zeros(shape = (N,N))
    x_mod_y = x % y
    
    permutation = 0
    for i in range(x_mod_y, (y + x_mod_y)):
        u[i % y][permutation] = 1
        permutation += 1
    
    for r in range(y,N):
        u[r][r] = 1
    
    U = Operator(u)
    return U

For example, this will return the exact operator $U_{3\ (mod\ 5)}$ that I have wrote above:

U = generate_x_mod_y_AdditionOperators(x = 3, y = 5)

You can also append this operator to a quantum circuit with any desired input, and then observe how the statevector is being affected by applying this operator.

$\endgroup$
9
  • $\begingroup$ So if I wanted to do mod 5, it would be the permutation matrices of the 5 by 5 Identity matrix?(Just to Clarify) $\endgroup$ Sep 2, 2022 at 15:13
  • $\begingroup$ No. For a register of $n = 2$ qubits it’s meaningless to talk about mod-5 addition because the dimension of the state space of the register is $N = 2^n = 4$. To a register consisted of $n = 3$ qubits we can apply mod-5 addition - and we can think of that also as $8 \times 8$ permutation matrix operators being applied on the register. $\endgroup$
    – Ohad
    Sep 2, 2022 at 16:24
  • $\begingroup$ Could you please say what the $8\times8$ permutation matrices are for mod 5? Like (x + 3) mod 5? $\endgroup$ Sep 4, 2022 at 1:12
  • 1
    $\begingroup$ You don't "index" "elements" in the statevector. Every entry of the statevector is a probability amplitude for a specific computational basis state (which are indexed from $0$ to $N = 2^n - 1$ in binary representation, while $n$ is the number of qubits). For example, the state space spanned by $n = 2$ qubits is $4$ dimensional and its basis states are $|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$. I have modified my answer with a full explanation regarding your question. $\endgroup$
    – Ohad
    Sep 6, 2022 at 9:40
  • 1
    $\begingroup$ No. It’s a little bit confusing. I suggest you try this with various values and you will see it does the job. $\endgroup$
    – Ohad
    Sep 6, 2022 at 17:14

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.