7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ It's not quite clear what is that permutation with $(i,i+1)$ cycles. $\endgroup$
    – Danylo Y
    Jan 1, 2020 at 22:14
  • $\begingroup$ @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 $\endgroup$
    – Sanchayan Dutta
    Jan 1, 2020 at 22:18
  • $\begingroup$ 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? $\endgroup$
    – Danylo Y
    Jan 1, 2020 at 22:31
  • 2
    $\begingroup$ @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. $\endgroup$
    – Sanchayan Dutta
    Jan 1, 2020 at 22:43

1 Answer 1

Reset to default
3
$\begingroup$

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.

So that decomposes your desired operation into a bunch of other computational basis to computational basis transformations. Construct the circuits for those, concatenate them all together in the specified order and then pass the resulting circuit through an optimizer.

Write down something that works even if it is inefficient first, then you can look for simplifications until you come up with something better. That might be more general advice as well.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.