How to generate a unitary matrix given a permutation of the qubits

Question

The title explains it all, let's say that I have a unitary matrix whose effect is defined when applied to qubits 0 and 1 in order, how can I create its unitary for when it is applied to 1, 0? For two qubit gate it's trivial as that's the transformation from the two different endianess CNOT, but for multi-qubit gates and custom n-qubit gates?

Answer 1

Briefly, the rows of your unitary matrix $U$ will be the $2^n$ input vectors (same as a truth table); the columns of your matrix $U$ will also be the $2^n$ vectors; and the entries $U_{ij}$ will be $1$ iff input vector $i$ maps to vector $j$, and will be $0$ everywhere else.

Conventionally the rows and columns are ordered in binary, starting with $|00\cdots0\rangle$ and ending with $|11\cdots1\rangle$, although I guess that's not really required.

For a 3+qubit gate like $\mathsf{CCNOT}$ gate, conventionally the first $6$ rows and columns only have $1$ along the diagonal, because no permutation happens there.

---

Letting $\mathsf{CCNOT}_{a,b}$ be the Toffoli gate controlled on qubits $a,b$, we have:

$$\mathsf{CCNOT}_{1,2}=\begin{pmatrix} 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 & 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 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix};$$

while: $$\mathsf{CCNOT}_{2,3}=\begin{pmatrix} 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 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \end{pmatrix};$$

and

$$\mathsf{CCNOT}_{1,3}=\begin{pmatrix} 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 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}.$$

Answer 2

For the simple 2-qubit case, you will certainly agree that you can implement a $CNOT_{1\to0}$ gate by performing a $CNOT_{0\to1}$ gate between two $SWAP_{0 \iff 1}$ gates. This is also true for the underlying unitary matrices, you can go back and forth between the two endianess of a 2-qubit gate by conjugating its unitary matrix by a permutation matrix (the $SWAP$ gate unitary in this case).

In the more general case, you want to conjugate your unitary matrix by a permutation matrix corresponding to your desired qubit permutation.

Since any permutation can be decomposed into a sequence of transpositions, you can build your permutation matrix as a product of $SWAP$ gates on different qubits.

The decomposition is not unique and can be done in more or less naive ways. Going all the way back to adjacent transpositions (i.e. the exchange of two consecutive qubits aka a $SWAP_{i \iff i+1}$ gate) can be a good starting point.