Table of Contents
Permutation gate
Permutation gate applies a classical permutation to the computational basis states of qubits. It is a unitary operation that reorders basis states according to a permutation : . Permutation gates are reversible, preserve the Hamming weight (number of 1s), and can be efficiently decomposed into two-qubit gates.
Definition
For qubits, a permutation gate corresponding to permutation is:
The matrix representation is if and 0 otherwise (permutation matrix).
Examples
Cyclic shift (rotation):
- Rotates all basis states by one position
- For 3 qubits:
Bit-reversal permutation:
- Reverses the bitstring of
- For 3 qubits: (palindromic),
- Used in Fourier transforms to reorder outputs
Transposition (single swap): exchange two basis states
- for fixed
- All other states unchanged
SWAP of qubits: reorder qubits, e.g.,
- Permutation of qubits within a state
Properties
- Unitary: (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
Construction from two-qubit gates
Most permutations can be decomposed into SWAP gates and single-qubit gates:
Bit-reversal on n qubits: SWAPs
- Swap qubits 0 and , then 1 and , etc.
- Total: gates
Cyclic shift: use CNOTs to implement rotation logic
- More complex than bit-reversal; often gates for general construction
Arbitrary permutation: decompose into transpositions, then implement each via SWAPs
- Up to gates for arbitrary permutations
Circuit depth
- Bit-reversal: depth with adjacent SWAPs
- Cyclic shift: depth for specific implementations
- General permutation: 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
- SWAP gates: implement transpositions and reorderings
- Quantum Fourier Transform: uses bit-reversal permutation
- Controlled-unitary gates: permutations can be controlled
