3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ It looks like you are just talking about classical circuits. Is that the case? $\endgroup$
    – AHusain
    Apr 15, 2019 at 14:32
  • $\begingroup$ yes but how do i implement it in quantum circuits? $\endgroup$
    – Upstart
    Apr 15, 2019 at 14:41

1 Answer 1

Reset to default
5
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.