2023/12/26 by Ayse Kotil, Kotil, Ayse, F. Šimkovic +3 · 1 citation
Computer Science · Engineering · #FOS: Physical sciences #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2312.15982
openalex publication_date 2023/12/26 · openalex created_date 2023/12/29 · openalex updated_date 2026/07/28
We develop a qubit routing algorithm with polynomial classical run time for the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a two step process. First, it obtains a near-optimal solution, based on Vizing's theorem for the edge coloring problem, consisting of subsets of the interaction gates that can be executed in parallel on a fully parallelized all-to-all connected QPU. Second, it proceeds with greedy application of SWAP gates based on their net effect on the distance of remaining interaction gates on a specific hardware connectivity graph. Our algorithm strikes a balance between optimizing for both the circuit depth and total SWAP gate count. We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on k-regular as well as Erdös-Renyi problem graphs of sizes up to N ≤ 400.