  Current proposals for quantum compilers require the synthesis and
optimization of linear reversible circuits and among them CNOT circuits. Since
these circuits represent a significant part of the cost of running an entire
quantum circuit, we aim at reducing their size. In this paper we present a new
algorithm for the synthesis of CNOT circuits based on the solution of the
syndrome decoding problem. Our method addresses the case of ideal hardware with
an all-to-all qubit connectivity and the case of near-term quantum devices with
restricted connectivity. For both cases, we present benchmarks showing that our
algorithm outperforms existing algorithms.
