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?

  • $\begingroup$ It looks like you are just talking about classical circuits. Is that the case? $\endgroup$ – AHusain Apr 15 at 14:32
  • $\begingroup$ yes but how do i implement it in quantum circuits? $\endgroup$ – Upstart Apr 15 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$.

For example, here is a circuit which multiplies by $M$, working modulo 8:

M circuit

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.

  • $\begingroup$ sir i couldnot understand your explaination though it was very well written but still can you elaborate your steps $\endgroup$ – Upstart Apr 15 at 18:26
  • $\begingroup$ 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? $\endgroup$ – Upstart Apr 16 at 7:36
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney Apr 16 at 12:51
  • $\begingroup$ But in the method you have written, where and when does the quantum part come. $\endgroup$ – Upstart Apr 16 at 13:34
  • $\begingroup$ @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. $\endgroup$ – Craig Gidney Apr 16 at 14:35

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.