search

quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
457 stars 72 forks source link

Understand pre-/post-permutations in gate decompositions (was: Add CNS translation) #121

Open stylewarning opened 5 years ago

stylewarning commented 5 years ago

As @marcusps described to me in private correspondence, there is a ISWAP to CNOT+SWAP translation described in this paper. We should add it (if @ecp-rigetti didn't already figure it out). See this paper: https://arxiv.org/pdf/quant-ph/0209035.pdf

ecpeterson commented 5 years ago

Yeah, you're late to the party: SWAP lies in the same local equivalence class as CNOT followed by ISWAP, and you can use that to solve for ISWAP, then expand SWAP into three CNOTs, then cancel one of those CNOTs with the one from the previous decomposition, and you'll end up with https://github.com/rigetti/quilc/blob/master/src/compilers/translators.lisp#L83 .

ecpeterson commented 5 years ago

(optimal-2q.lisp will also produce this decomposition without further prompting.)

stylewarning commented 5 years ago

@ecp-rigetti Does it (optimal 2q) understand the nature of the swaps?

ecpeterson commented 5 years ago

No: given an ISWAP, it won't attempt to marry it to a SWAP in order to drive the depth down. This might be worth doing; IBM likes this idea enough to have given it a name ("mirror gates") in this paper: https://arxiv.org/pdf/1811.12926.pdf .