Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity
arXiv:2402.00478 · doi:10.1038/s41534-024-00909-7
Abstract
Efficiently mapping quantum circuits onto hardware is an integral part of the quantum compilation process, wherein a circuit is modified in accordance with the stringent architectural demands of a quantum processor. Many techniques exist for solving the quantum circuit mapping problem, in addition to several theoretical perspectives that relate quantum circuit mapping to problems in 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 circuit complexity 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, which we dub the lightcone bound. 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 construct an algorithm for calculating the lightcone bound, which is directly compared alongside the IBM Qiskit compiler for over 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 surpasses our bound, signaling utility for estimating minimal overhead when realizing quantum algorithms on constrained quantum hardware. This work also 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.
References in corpus (23)
- Critical phenomena in complex networks
- Layer aggregation and reducibility of multilayer interconnected networks
- tket : A Retargetable Compiler for NISQ Devices
- Quantum Circuit Simplification and Level Compaction
- Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
- Properties of Classical and Quantum Jensen-Shannon Divergence
- Spectral entropies as information-theoretic tools for complex network comparison
- On the metric character of the quantum Jensen-Shannon divergence
- A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
- Geometric optimisation of quantum thermodynamic processes
- Experiments on quantum causality
- Mapping quantum circuits to modular architectures with QUBO
- On Optimal Subarchitectures for Quantum Circuit Mapping
- Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques
- Quantum Circuit Compiler for a Shuttling-Based Trapped-Ion Quantum Computer
- Resource theory of quantum uncomplexity
- Improving Quantum Computation by Optimized Qubit Routing
- Advantages and limitations of quantum routing
- Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
- SpinQ: Compilation strategies for scalable spin-qubit architectures
- Geometric approach to quantum statistical inference
- beSnake: A routing algorithm for scalable spin-qubit architectures
- Low-Depth Flag-Style Syndrome Extraction for Small Quantum Error-Correction Codes