CNOT-Optimal Clifford Synthesis as SAT
Irfansha Shaik, Jaco van de Pol · 2025
Read CNOT-Optimal Clifford Synthesis as SAT by Irfansha Shaik, Jaco van de Pol (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00634.txt.
Description
Irfansha Shaik and Jaco van de Pol shrink quantum circuits with exact methods. Their 2025 paper targets Clifford circuits, a core family in quantum computing. Noisy two-qubit gates, called CNOTs, are the ones worth cutting most. Fast heuristic compilers often leave savings on the table.
The team encodes the search as a SAT problem, the kind solvers crack by logic. Restricting the search to normal forms guarantees the fewest CNOTs possible. A second encoding trims circuit depth instead. The tool also honors hardware wiring limits and allows qubit relabeling. In tests it beat older SAT tools and trimmed benchmark circuits by up to about a third.
Catalog record
| CREATOR | Irfansha Shaik, Jaco van de Pol |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-00634