Optimizing Qubit Routing with Bridge Gates: Extending Quantum Circuit Efficiency Across Arbitrary Distances

Qubit routing is a critical challenge in quantum computing,<br/>essential for implementing quantum circuits on hardware with limited<br/>connectivity. This paper introduces a novel perspective on qubit routing by exploring the use of bridge gates, which enable the execution of<br/>controlled NOT (CNOT) operations over non-adjacent qubits without re-routing the qubits. The study highlights the advantages of bridge gates<br/>compared to SWAP gates, particularly their ability to preserve qubit<br/>assignments and potentially optimize subsequent routing steps.<br/>We propose an extension to the concept of bridge gates by generalizing<br/>them for arbitrary distances and provide constructions demonstrating<br/>their feasibility. By analysing their performance, we show that larger-distance bridge gates can significantly reduce the number of CNOT gates<br/>in certain circuits. Furthermore, a new qubit routing problem is defined,<br/>incorporating both SWAP and bridge gates, and we discuss how this<br/>impacts the complexity of the problem.<br/>