Site Tools


quantum-gate-permutation

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

quantum-gate-permutation.md · Last modified: