npj Quantum Information, Published online: 09 November 2024; doi:10.1038/s41534-024-00909-7
Lightcone bounds for quantum circuit mapping via uncomplexity
Efficiently mapping quantum circuits onto hardware is integral for the quantum compilation process, wherein a circuit is modified in accordance with a quantum processor’s connectivity.
Many techniques currently exist for solving this problem, wherein SWAP-gate overhead is usually prioritized as a cost metric.
Researchers have reconstituted quantum circuit mapping using tools from quantum information theory, showing that a lower bound, which we dub the lightcone bound, emerges for a circuit executed on hardware.
They have also developed an initial placement algorithm based on graph similarity search, aiding them in optimally placing circuit qubits onto a device. 600 realistic benchmarks using the IBM Qiskit compiler and a brute-force method are then tested against the lightcone bound, with results unambiguously verifying the veracity of the bound, while permitting trustworthy estimations of minimal overhead in near-term realizations of quantum algorithms.
This work constitutes the first use of quantum circuit uncomplexity to practically-relevant quantum computing.
