Random sampling of permutations on quantum computers

We present a combinatorial perspective on the Steinhaus-Johnson-Trotter algorithm for expressing a permutation as a product of adjacent transpositions, which forms a generating set of the permutation group. We show that these adjacent transpositions can be implemented within a quantum circuit model using generalized Toffoli gates together with CNOT gates. Building on this framework, we design a quantum circuit for implementing linear combinations of permutations, which enables the sampling of a random permutation through quantum measurements of ancillary qubits serving as control qubits for the relevant adjacent transpositions.

Our analysis establishes that the overall gate complexity for implementing a linear sum of permutations on N elements is O(N^3 log⁡ N) in a quantum register of O(N log⁡ N) qubits, while the uniformly randomly sampled permutation is expressed as a product of O( N² log⁡ N) elementary gates. Furthermore, we show that a quantum circuit representation of a permutation on N elements can be achieved using ⌈log⁡ N⌉ qubits with gate complexity of O(N² log⁡ N).

This framework provides a scalable approach to quantum implementation of permutations and highlights the potential for efficient quantum random permutation sampling with applications in quantum algorithms and combinatorial optimization.