Lightcone bounds for quantum circuit mapping via uncomplexity
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 prioritize...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2024-11-01
|
| Series: | npj Quantum Information |
| Online Access: | https://doi.org/10.1038/s41534-024-00909-7 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2056-6387 |