We focus on the depth optimization of CNOT circuits on hardware with limited connectivity. We adapt the algorithm from Kutin et al. that implements any n -qubit CNOT circuit in depth at most 5n on a Linear Nearest Neighbor architecture. Our proposal is a block version of Kutin et al.’s algorithm that is scalable with the number of interactions available in the hardware: the more interactions we have, the less the depth. We derive better theoretical upper bounds and provide a simple implementation of the algorithm. Overall, we achieve better depth complexity for CNOT circuits on some realistic quantum hardware like a grid or a ladder. For instance, the execution of an n -qubit CNOT circuit on a grid can be done in depth 4n+8 .

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.

Linear reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. These circuits can be efficiently simulated by classical computers and their size is polynomially bounded by the number of qubits, making them a good candidate to deploy efficient methods to reduce computational costs. We propose a new algorithm for synthesizing any linear reversible operator by using an optimized version of the Gaussian elimination algorithm coupled with a tuned LU factorization. We also improve the scalability of purely greedy methods. Overall, on random operators, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes: The custom Gaussian elimination algorithm provides the best results for large problem sizes (n > 150), while the purely greedy methods provide quasi optimal results when n < 30. On a benchmark of reversible functions, we manage to significantly reduce the CNOT count and the depth of the circuit while keeping other metrics of importance (T-count, T-depth) as low as possible.