Depth and Number of added SWAPs for newly developed routing code for QAOA quantum circuits

<p>We developed 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 <span><span><span><span>k</span></span></span></span>-regular as well as Erd&ouml;s-Renyi problem graphs of sizes up to&nbsp;<span><span><span><span>N</span><span>&le;</span><span>400</span></span></span></span>. This repository contains data and a ipython notebook used for plotting the results presented in the paper</p>