Questions about CNOT synthesis

[buttercutter]

For CNotSynthType, I have the following few questions:

1. What does swap-based algorithm exactly mean ?
2. How is qubit ordering related to Hamilton-path-based method ? See page 7 of Quantum CNOT Circuits Synthesis for NISQ Architectures Using the Syndrome Decoding Problem
3. For recursive Steiner--Gauss method, it seems that it does not have decent performance ? See Dynamic qubit allocation and routing for constrained topologies by CNOT circuit re-synthesis

@alexcowtan @cqc-melf Do you have any comments on these ?

[cqc-melf]

Hi @buttercutter, thank you for the questions and sorry for the late response.

1. the swap based algorithm means that in the last part (the synthesis of the linear map) will use a fast simple swap based approach to resolve this. You can have a look at the details on https://github.com/CQCL/tket/blob/develop/tket/src/ArchAwareSynth/SteinerTree.cpp#L730 If you want to know more or some of the details are unclear, please let me know.

2. To my knowledge we don't have a benchmark comparing to that paper, do you have done something in that direction?

3. In my understanding what Sarah and Arianne are suggesting in the paper is something different from what we have done in our implementation. The recursive part (which is similar to https://arxiv.org/abs/2004.06052) is only used in synthesising the linear part.

I hope this helps you, if there are any open questions left, please let me know!