Permutation gate applies a classical permutation to the computational basis states of $n$ qubits. It is a unitary operation that reorders basis states according to a permutation $\pi$: $|j\rangle \to |\pi(j)\rangle$. Permutation gates are reversible, preserve the Hamming weight (number of 1s), and can be efficiently decomposed into two-qubit gates.

For $n$ qubits, a permutation gate corresponding to permutation $\pi: \{0,1,\ldots,2^n-1\} \to \{0,1,\ldots,2^n-1\}$ is:

$$P_\pi |j\rangle = |\pi(j)\rangle$$

The matrix representation is $P_\pi[i][j] = 1$ if $j = \pi^{-1}(i)$ and 0 otherwise (permutation matrix).

Cyclic shift (rotation): $|j\rangle \to |j \oplus 1 \pmod{2^n}\rangle$

• Rotates all basis states by one position
• For 3 qubits: $|0\rangle \to |1\rangle \to |2\rangle \to \cdots \to |7\rangle \to |0\rangle$

Bit-reversal permutation: $|j\rangle \to |\text{reverse}(j)\rangle$

• Reverses the bitstring of $j$
• For 3 qubits: $|101\rangle \to |101\rangle$ (palindromic), $|100\rangle \to |001\rangle$
• Used in Fourier transforms to reorder outputs

Transposition (single swap): exchange two basis states

• $|i\rangle \leftrightarrow |j\rangle$ for fixed $i, j$
• All other states unchanged

SWAP of qubits: reorder qubits, e.g., $|x_1 x_2 x_3\rangle \to |x_3 x_2 x_1\rangle$

• Permutation of qubits within a state

• Unitary: $P_\pi^\dagger P_\pi = I$ (permutations are reversible)
• Permutation matrix: orthogonal, each row and column has exactly one 1
• Hamming weight preservation: cyclic shifts and bit-reversals preserve the number of 1s
• No phase: purely classical reordering, no complex amplitudes introduced
• Self-inverse (sometimes): some permutations (transpositions, bit-reversal) satisfy $P^2 = I$

Most permutations can be decomposed into SWAP gates and single-qubit gates:

Bit-reversal on n qubits: $\lfloor n/2 \rfloor$ SWAPs

• Swap qubits 0 and $n-1$, then 1 and $n-2$, etc.
• Total: $O(n)$ gates

Cyclic shift: use CNOTs to implement rotation logic

• More complex than bit-reversal; often $O(n^2)$ gates for general construction

Arbitrary permutation: decompose into transpositions, then implement each via SWAPs

• Up to $O(n^2)$ gates for arbitrary permutations

• Bit-reversal: $O(n)$ depth with adjacent SWAPs
• Cyclic shift: $O(n)$ depth for specific implementations
• General permutation: $O(n)$ depth worst-case, depending on permutation structure

• Quantum Fourier Transform: bit-reversal reorders output (QFT outputs in reversed order)
• Sort and search: reorder states for algorithm optimization
• Quantum simulation: map between different basis orderings
• Error correction: classical syndrome reordering in stabilizer codes

Permutation gates can be applied post-measurement to reorder classical bit strings without quantum overhead. However, applying them to superpositions before measurement can alter quantum interference patterns.

• SWAP gates: implement transpositions and reorderings
• Quantum Fourier Transform: uses bit-reversal permutation
• Controlled-unitary gates: permutations can be controlled