# Decomposing a $(w+1)$-qubit permutation gate into $w$-qubit permutation gates, SWAPs and NOTs

Say I have a quantum circuit of $$w+1$$ qubits with a permutation gate (mapping computational basis states to computational basis states) that does the permutation $$(i, i+1)(i+4, i+5)$$ on $$w+1$$ qubits if $$i$$ is odd and the permutation $$(i+1, i+2)(i+3, i+4)$$ if $$i$$ is even, for some fixed $$i$$ in the range $$1 \leq i \leq 2^W -2$$. Is it possible to decompose the $$(w+1)$$-qubit permutation gate into some $$w$$-qubit permutation gates, $$\mathrm{SWAP}$$s and $$\mathrm{NOT}$$s? How? (Ideally, I'd like to avoid using $$\mathrm{SWAP}$$s and $$\mathrm{NOT}$$s due to certain implementation issues.)

I think it should be possible because of Lemma $$2$$ in the appendix of the paper Generating the group of reversible logic gates (Vos, Ra & Storme, 2002) (PDF):

The subgroup of exchangers $$\mathbf{E}_w$$, augmented with the $$\text{NOT}$$ gate and the $$\text{CONTROLLED}^{w−2}$$ $$\text{NOT}$$ gate, generates the group of even simple control gates.

but I'm not sure how to construct the circuit.

• It's not quite clear what is that permutation with $(i,i+1)$ cycles. Jan 1 '20 at 22:14
• @DanyloY The $2^{W+1}$ (basis) state of $W+1$ qubits. $|0...0\rangle, |0...1\rangle,...,|1...1\rangle$ and so on. If you look at the paper's appendix things might be a bit more clearer Jan 1 '20 at 22:18
• I mean permutations $(1,2)(5,6)$ and $(5,6)(9,10)$ intersect. Also they intersect with, say, $(5,6)(7,8)$. So what is the total permutation? Jan 1 '20 at 22:31
• @DanyloY The gate is abstract . It can permutation arbitrary permutations of the form $(i, i+1)(i+4, i+5)$ for any given odd $i$ but not for two odd $i$'s simultaneously. So it can either do $(1,2)(5,6)$ or $(5,6)(9,10)$ depending on whether we set $i$ as $1$ or $5$. For the problem, consider $i$ to be some constant value in the given range. Jan 1 '20 at 22:43

Consider some simpler cases, $$(j,j+1)$$ for general $$j$$. Then you can do you want with plugging in $$j=i$$, $$j=i+1$$, $$j=i+3$$ and $$j=i+4$$ and concatenating the circuits appropriately and then simplifying.
So how to do $$(j,j+1)$$? That is conjugate to $$(0,1)$$, so just consider that for now.
$$(0,1)$$ would be NOT but controlled on making sure all the higher places are $$0$$.
The conjugation that takes you between $$(0,1)$$ and $$(j,j+1)$$ is the circuit that does addition of $$j$$ modulo $$2^{w+1}$$. Reduce that to addition of $$1$$ modulo $$2^{w+1}$$ repeated.