fix permutation gate synthesis

[stylewarning]

Perm gates were being synthesized as inverses, leading to improper compilations.

Added a battery of new tests for checking multi-qubit perm gate synthesis.

Fixes #805.

[stylewarning]

Each of X, CNOT, and CCNOT are self-inverting, so the group inverse of a composite circuit is given by the same circuit with the reverse gate ordering. Maybe rather than invert the input permutation it would be preferable to reverse the order in which the gates are emitted? This may require more surgery, but to me it feels less “too wrongs make a right”.

I agree with you that inverting the inverse isn't very nice.

The only reason I decided against this was if in the future somebody modifies this code and the "just reverse the list" no longer implies an inverse. If we had a good "inverse sequence" function—which we do, but adds all sorts of DAGGERs–then maybe it'd be more palatable.

I think my preferred approach would be the one that I did, and post an issue to gently refactor it to just produce the right decomposition straight away.

[ecpeterson]

I’m not sure I buy it — it seems like OP might have mixed up “left” and “right” conventions in the algorithm description vs circuit ordering vs Quil instruction ordering, so that we’re already looking at an accidentally inverted implementation and we’d be eliminating DAGGER coincidences by untwisting some of the lefts and rights.

I’m also fine deferring further changes to an issue, but this fix as-is isn’t my long term preference.

[karlosz]

Hello. I think I'm leaning towards agreeing with @ecpeterson here. What he said about mixing up the convention for left and right sounds exactly like what I did: When I implemented the algorithm I remember getting confused exactly how the different notations associated left and right with post and preapplication, and its very likely there is one too many reversals or not enough. It is standard to write permutation composition as applying in left to right order in some parts of grou theory and as the normal right to left order in others. Since this is looks like the original code bungled that it would be nice to fix it the right way by nailing down what the convention is supposed to be.

[stylewarning]

Ok, I'll take a look and see if I can repair it / build it in the right direction.

[stylewarning]

Even though I've simplified the computation, I still feel something isn't right about my approach. It seems the functions that are generating gates on qubits 0 to n-1 should instead be doing so from n-1 to 0. I just don't know where exactly that should happen.

I really don't want the (reverse qubits) call there; it feels like the same issue as described in @ecpeterson and @karlosz's previous comments here.

[ecpeterson]

That may not be avoidable because Quil argument ordering has descending significance. I think you’ll find examples of expressions like (nth args (- (length args) index 1)) in the circuit builders which are necessary for this reason. Dunno tho.

Thanks for making the more complicated fix! 👍

P.S.: I wish diff tools were more intelligent about Lisp; removing an outer let should highlight its whole contents as being modified. Is there a way to suggest to git to use a different diff implementation on certain file types? Hm.

[stylewarning]

That may not be avoidable because Quil argument ordering has descending significance. I think you’ll find examples of expressions like (nth args (- (length args) index 1)) in the circuit builders which are necessary for this reason. Dunno tho.

This part isn't irksome to me, it's that even if I pass qubits in "3 2 1" order, I have to reverse them to "1 2 3" so the circuit building code works. I suppose I'm suggesting that deep in the circuit-building code, it "natively" understands "3 2 1".

P.S.: I wish diff tools were more intelligent about Lisp; removing an outer let should highlight its whole contents as being modified. Is there a way to suggest to git to use a different diff implementation on certain file types? Hm.

There are a few diff algorithms built in to git but they're not visible in the GitHub interface. Agreed it's annoying.

[stylewarning]

I'm no longer irked. I added documentation that I think justifies everything. I took out a reverse since it was really a red herring to it all. Things look good to me now.