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!

[buttercutter]

Just putting the following for further reference:

[1] A. Zulehner, A. Paler, and R. Wille. An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems (TCAD), 2018.

[2] R. Wille, L. Burgholzer, and A. Zulehner. Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations. In Design Automation Conference (DAC), 2019.

[3] S. Hillmich, A. Zulehner, and R. Wille. Exploiting Quantum Teleportation in Quantum Circuit Mapping. In Asia and South Pacific Design Automation Conference (ASP-DAC), 2021.

[4] L. Burgholzer, S. Schneider, and R. Wille. Limiting the Search Space in Optimal Quantum Circuit Mapping. In Asia and South Pacific Design Automation Conference (ASP-DAC), 2022.

[5] T. Peham, L. Burgholzer, and R. Wille. On Optimal Subarchitectures for Quantum Circuit Mapping. arXiv:2210.09321, 2022.

[6] S. Schneider, L. Burgholzer, and R. Wille. A SAT Encoding for Optimal Clifford Circuit Synthesis. In Asia and South Pacific Design Automation Conference (ASP-DAC), 2023.

Reference : https://github.com/cda-tum/qmap

[buttercutter]

qiskit.synthesis.clifford.synth_clifford_greedy — a “greedy” decomposition based on this paper.

qiskit.synthesis.clifford.synth_clifford_layers — decomposition into S-CZ-CX-H-S-CZ-H-Pauli layers, based on this paper.

qiskit.synthesis.linear.synth_cnot_count_full_pmh — linear synthesis method that leads to good CNOT counts, based on Gaussian elimination described in this paper.

qiskit.synthesis.linear.synth_cnot_depth_line_kms — decomposition guaranteeing a CNOT depth of 5n*, based on this paper.

qiskit.synthesis.permutation.synth_permutation_depth_lnn_kms— SWAP gate based decomposition, guaranteeing SWAP depth of n* or better. Based on this paper.

qiskit.synthesis.permutation.synth_permutation_acg — decomposition with guaranteed SWAP depth of 2 at most, based on this paper.

*where n is the number of qubits

Reference : https://qiskit.org/documentation/apidoc/synthesis.html