Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint

Abstract

In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. Compilation of a quantum circuit into one compliant to such qubit connectivity constraint results in an increase of circuit depth. Various compilation algorithms were studied, yet what this depth overhead is remains elusive. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph, a graph-theoretic measure which has been studied for 3 decades. We also give reduction algorithms between different graphs, which allow compilation for one graph to be transferred to one for another. These results, when combined with existing routing algorithms, give asymptotically optimal compilation for all commonly seen connectivity graphs in quantum computing.

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Probing many-body dynamics on a 51-atom quantum simulator
• Quantum Computation as Geometry
• Quantum-state preparation with universal gate decompositions
• Quantum walks on a programmable two-dimensional 62-qubit superconducting processor
• Scalable gate architecture for densely packed semiconductor spin qubits
• An electrostatically defined serial triple quantum dot charged with few electrons
• Quantum Circuit Placement