-
Notifications
You must be signed in to change notification settings - Fork 62
Questions about CNOT synthesis #485
For CNotSynthType, I have the following few questions:
- What does swap-based algorithm exactly mean ?
- 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
- 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 ?
All reactions
Replies: 3 comments
Hi @buttercutter,
thank you for the questions and sorry for the late response.
-
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. -
To my knowledge we don't have a benchmark comparing to that paper, do you have done something in that direction?
-
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!
All reactions
-
👍 1
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
All reactions
-
👍 1
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