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 (51)
- Statistical mechanics of complex networks
- Quantum Computing in the NISQ era and beyond
- Critical phenomena in complex networks
- Quantum Error Correction for Quantum Memories
- Quantum Computing with Very Noisy Devices
- Fast Scramblers
- Reliable Quantum Computers
- A Theory of Fault-Tolerant Quantum Computation
- Quantum Fisher information matrix and multiparameter estimation
- Layer aggregation and reducibility of multilayer interconnected networks
- Roads towards fault-tolerant universal quantum computation
- Experimental Quantum Error Correction
- Jerusalem Lectures on Black Holes and Quantum Information
- Measuring thermodynamic length
- tket : A Retargetable Compiler for NISQ Devices
- Overhead and noise threshold of fault-tolerant quantum error correction
- The Second Law of Quantum Complexity
- Quantum Circuit Simplification and Level Compaction
- Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states
- Quantum error correction with only two extra qubits
- 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
- The laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states
- Flag fault-tolerant error correction with arbitrary distance codes
- Complex Networks from Classical to Quantum
- Stochastic thermodynamic interpretation of information geometry
- Thermodynamic length in open quantum systems
- Quantum circuit optimizations for NISQ architectures
- A Hardware-Aware Heuristic for the Qubit Mapping Problem in the NISQ Era
- Geometric optimisation of quantum thermodynamic processes
- Timing and resource-aware mapping of quantum circuits to superconducting processors
- Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search
- Mapping of Lattice Surgery-based Quantum Circuits on Surface Code Architectures
- Experiments on quantum causality
- Fault-tolerant Quantum Error Correction on Near-term Quantum Processors using Flag and Bridge Qubits
- Mapping quantum circuits to modular architectures with QUBO
- On Optimal Subarchitectures for Quantum Circuit Mapping
- Quantum Circuit Compiler for a Shuttling-Based Trapped-Ion Quantum Computer
- Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques
- 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
- Thermodynamics of network model fitting with spectral entropies
- beSnake: A routing algorithm for scalable spin-qubit architectures
- Low-Depth Flag-Style Syndrome Extraction for Small Quantum Error-Correction Codes
- Asymptotic entropy of the Gibbs state of complex networks