Shallower CNOT Circuits on Realistic Quantum Hardware

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.