# Permutation Gate

**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.

## Definition

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).

## Examples

**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

## Properties

- **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$

## Construction from Two-Qubit Gates

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

## Circuit Depth

- **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

## Applications

- **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

## Measurement Outcome Reordering

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.

## Relation to Other Gates

- [[quantum-gate-swap|SWAP gates]]: implement transpositions and reorderings
- [[quantum-gate-qft|Quantum Fourier Transform]]: uses bit-reversal permutation
- [[quantum-gate-controlled-unitary|Controlled-unitary gates]]: permutations can be controlled