Quantum addition and modulo operation using gates

I have a matrix equation $$X_{\text{new}}=AX_{\text{old}}$$, where $$A=\begin{bmatrix}1 & 1 & 1\\ 2 & 3 &2\\ 3&4&4 \end{bmatrix}\bmod 64$$, and $$X_{\text{old, new}}\in \{1,2,...64\}$$. Now I need to do these calculations in quantum sense, using gates.

What I see is that to get $$X_{\text{new}}(1)=(X_{\text{old}}(1)+X_{\text{old}}(2)+X_{\text{old}}(3))\bmod 2^{6}$$.

Since each $$X_{\text{old}}(i)\in \{1,2,...64\}$$, to add these three components, I need 6 full adders and to do the mod $$2^6$$ operation I need to just keep the 6 least significant bits of the sum. Is my approach correct?

• It looks like you are just talking about classical circuits. Is that the case? Apr 15 '19 at 14:32
• yes but how do i implement it in quantum circuits? Apr 15 '19 at 14:41

The main criteria that you need, in order to multiply by a matrix on a quantum computer (in the sense of permuting the states, not in the sense of adjusting the amplitudes) is for the matrix to have an inverse. You can find this inverse by performing Guassian elimination. Performing the Guassian elimination spits out exactly the operations you will need to perform, in reverse.

Let's do the Guassian elimination of $$M$$:

# 111
# 232
# 344

r2 -= 2*r1
r3 -= 3*r1
# 111
# 010
# 011

r1 -= r2
r3 -= r2
# 101
# 010
# 001

r1 -= r3
# 100
# 010
# 001

We managed to reach the identity matrix. Note that we didn't need to compute any multiplicative inverses in order to make the rows cancel properly or to make elements along the diagonal equal to 1, which is good because it means we can multiply by this matrix modulo any $$n$$. That won't always be the case.

If you run these operations backwards (reverse order and += instead of -=), you will turn the identity matrix into $$M$$. Run them backwards against a vector, and you are multiplying by $$M$$. The first column is preparing an input state to test it, the second column is green state displays showing the prepared value is [1, 2, 3], the final column is green state displays showing the output (modulo 8) is [6, 6, 7]. All the stuff in between is the reversed Gaussian elimination operations.

• sir i couldnot understand your explaination though it was very well written but still can you elaborate your steps Apr 15 '19 at 18:26
• Sir after carefully looking at the circuit i understood the steps, but what are the internal operations that are going on is what i wanted to know, like adding two qubits , since this tool automatically does a $(\mod~8)$ operation, what is the mathematics behind that is that the same that i mentioned in my question, and what fundamental gates like Pauli( I see you have used Pauli gate to initialize your vector) other gates like CNOT, etc are used implicitly? Apr 16 '19 at 7:36
• @Upstart The adder circuits perform two's complement addition. There are a variety of possible circuits for this, such as the cuccaro adder. Addition scaled by a classical constant can be implemented using repeated additions, or using more efficient techniques such as the ones explained in this paper. Apr 16 '19 at 12:51
• But in the method you have written, where and when does the quantum part come. Apr 16 '19 at 13:34
• @Upstart The quantum part comes from some larger algorithm passing superposed states through the circuit and then interfering the output in some useful way. This is possible as long as you make sure the circuit is reversible, even if you construct it out of what you might think of as classical pieces such as addition. Apr 16 '19 at 14:35