Optimize decomposition of cirq.QubitPermutationGate

[tanujkhattar]

Description of the issue
#5093 introduced a default decomposition for cirq.QubitPermutationGate using odd-even sort to decompose the gate into minimum number of adjacent swap operations.

We should optimize this decomposition assuming all to all connectivity and minimizing resulting circuit depth.

Cirq version
0.14dev

[migueltorrescosta]

I'd like to take on this task. Before working on a solution, are there recommended / standardized ways to solve this issue? If not I'd be keen on developing my own :)

[NoureldinYosri]

the optimal number of swaps needed to sort a permuation = n - number of cycles. The standard way to sort permutations using swaps is to break down the permutation into cycles and then sort each cycles using cycle_length - 1 swaps. for example if the permuation is (1, 3, 2) then the cycles are (1,) and (2, 3) the first cycle is already sorted but the the second cycle needs one swap operation.

another example is (7, 6, 4, 5, 3, 4, 1, 10, 8, 9) in this cases the cycles are (1, 7), (2, 6, 4, 5, 3), (8, 10, 9) the first one needs 1 swap, the second needs 4 swaps (2, 6), (2, 4), (2, 5), (2, 3) the third one needs two swaps (8, 10) (8, 9)