Lightcone bounds for quantum circuit mapping via uncomplexity
M.A. Steinberg (TU Delft - QuTech Advanced Research Centre, TU Delft - QCD/Feld Group)
Medina Bandic (TU Delft - QuTech Advanced Research Centre, TU Delft - QCD/Almudever Lab, TU Delft - QCD/Feld Group)
Sacha Szkudlarek (TU Delft - ChemE/Transport Phenomena, TU Delft - QuTech Advanced Research Centre)
Carmen G. Almudever (Universitat Politécnica de Valencia)
A. Sarkar (TU Delft - QuTech Advanced Research Centre, TU Delft - QCD/Feld Group)
S. Feld (TU Delft - Quantum Circuit Architectures and Technology, TU Delft - QCD/Feld Group, TU Delft - QuTech Advanced Research Centre)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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. We reconstitute 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. We also develop an initial placement algorithm based on graph similarity search, aiding us 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.
help_outline