Quantum circuits for permutation matrices
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911316532264960 |
|---|---|
| author | Hanson, Jason |
| author_facet | Hanson, Jason |
| contents | Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on $2^n$ letters. All circuits involve $n$ qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_11938 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum circuits for permutation matrices Hanson, Jason Quantum Physics Computational Complexity 68Q12 Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on $2^n$ letters. All circuits involve $n$ qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved. |
| title | Quantum circuits for permutation matrices |
| topic | Quantum Physics Computational Complexity 68Q12 |
| url | https://arxiv.org/abs/2512.11938 |