Resource Bounds for Quantum Circuit Mapping via Quantum Circuit Complexity

Efficiently mapping quantum circuits onto hardware is an integral part of the quantum compilation process, wherein a quantum circuit is modified in accordance with the stringent architectural demands of a quantum processor. Many techniques exist for solving the quantum circuit mapping problem, many of which relate quantum circuit mapping to classical computer science. This work considers a novel perspective on quantum circuit mapping, in which the routing process of a simplified circuit is viewed as a composition of quantum operations acting on density matrices representing the quantum circuit and processor. Drawing on insight from recent advances in quantum information theory and information geometry, we show that a minimal SWAP gate count for executing a quantum circuit on a device emerges via the minimization of the distance between quantum states using the quantum Jensen-Shannon divergence. Additionally, we develop a novel initial placement algorithm based on a graph similarity search that selects the partition nearest to a graph isomorphism between interaction and coupling graphs. From these two ingredients, we then construct a polynomial-time algorithm for calculating the SWAP gate lower bound, which is directly compared alongside the IBM Qiskit compiler for over 600 realistic benchmark experiments, as well as against a brute-force method for smaller benchmarks. In our simulations, we unambiguously find that neither the brute-force method nor the Qiskit compiler surpass our bound, implying utility as a precise estimation of minimal overhead when realizing quantum algorithms on constrained quantum hardware. This work constitutes the first use of quantum circuit uncomplexity to practically-relevant quantum computing. We anticipate that this method may have diverse applicability outside of the scope of quantum information science, and we discuss several of these possibilities.