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 (17)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Variational Quantum Algorithms
• Probing many-body dynamics on a 51-atom quantum simulator
• State preservation by repetitive error detection in a superconducting quantum circuit
• Natural and artificial atoms for quantum computation
• Quantum Computation as Geometry
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Few-Electron Quantum Dot Circuit with Integrated Charge Read-Out
• Manipulation of a single charge in a double quantum dot
• The Addition Spectrum of a Lateral Dot from Coulomb and Spin Blockade Spectroscopy
• 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
• Circuit Transformations for Quantum Architectures