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