Paper 2026/1798 Original: eprint.iacr.org/2026/1798 ↗
Generalized Greedy Algorithms for Synthesizing Low-depth CNOT Circuits
Abstract
A CNOT circuit is a quantum circuit where the only type of gate appeared in the circuit is the CNOT gate. Given an n × n binary matrix which specifies the relationship between input and output, existing greedy algorithms generate corresponding CNOT circuits of n qubits, with the goal of minimizing depth of the circuits. This short paper presents two new greedy algorithms, which can be considered as generalized versions of existing greedy algorithms. The new algorithms are inspired by the algorithm presented in the Asiacrypt 2024 paper “Quantum circuits of AES with a low-depth linear layer and a new structure”. Although we have not run large-scale experiments, small-scale experiments suggest that the new algorithms are at least as powerful as existing greedy algorithms.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2026-08-25: last updated
- 2026-08-25: published
- Short URL
- https://ia.cr/2026/1798
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/1798,
author = {Tung Chou},
title = {Generalized Greedy Algorithms for Synthesizing Low-depth CNOT Circuits},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1798},
year = {2026},
url = {https://eprint.iacr.org/2026/1798}
}