2
$\begingroup$

This is a follow-up question from here.

Let's say after an LUP decomposition, we have an 8x8 permutation matrix:

$ P^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix} $

How to construct the corresponding swap gates?

Note: I think this question is different from the other question because the question in that link is in the form of unitary matrix ($2^n$ x $2^n$) while here is a $n$ x $n$.

$\endgroup$
2
$\begingroup$

There's a thing named elementary row operations, where the swap gate I think corresponds to the Row Switching operation. So what you need to do is change your matrix step by step into an identity matrix.

For your case, $\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}=swap(2,3) *\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}=swap(2,3)*swap(3,5)* \begin{bmatrix} 1 & 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 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix} ...$

Where I use the $swap(i,j)$ representing the action of switching two rows. Finally, you will find out the corresponding swap gate.

$\endgroup$
2
  • $\begingroup$ Thanks for the prompt answer! I have questions though: 1) your matrix is 7x8 while mine is 8x8, it's just a mistype, right? 2) Is there an algorithmic, fixed way to obtain the sequence of swap gates, or is it heuristic? $\endgroup$
    – prairie99
    Nov 9 at 10:47
  • 1
    $\begingroup$ @prairie99 typo, sorry. The way I find the swap gate is just by changing the matrix more and more like the identity matrix. That is, first fix the $(1,1)$ element to be 1, then the $(2,2)$ element to be 1, then ... $\endgroup$
    – narip
    Nov 9 at 10:52

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.