Abstract
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 .
Funding Information
  • French state through the ANR as a part of Plan France 2030 (NISQ2LSQ (ANR-22-PETQ-0006), EPiQ (ANR-22-PETQ-0007), SoftQPro (ANR-17-CE25-0009))

This publication has 20 references indexed in Scilit: