Quantum computing (QC) has been shown, in theory, to hold huge advantages over classical computing. However, there remains many engineering challenges in the implementation of real-world QC applications. In order to devide-and-conquer, we can split the task as below.
The topics that we are particularly interested in are those concerning QC architecture and design automation, which connects algorithms and devices. One of them, is layout synthesis for quantum computing (LSQC). A quantum program usually assumes all-to-all connectivity of the qubits, but this is not the case for some QC technologies. LSQC aims to transform the programs so that they are executable on actual quantum hardware and, at the same time, overcome some limitations of these near-term devices, e.g. volatile qubits and error-prone quantum gates.
Our results so far came from two different angles: benchmark and solution. We published QUEKO, a set of benchmarks with known optimal depths and gate counts on given architectures, which can be used to evaluate existing layout synthesis tools, and direct future development of such tools. Previously, LSQC benchmarks do not provide optimal solutions, so researchers can only compare with each other, but how far are they from theoretical optimum? This is an NP-complete problem to answer in general but, specifically, the optimal solutions for QUEKO benchmarks on the given architectures are known, so we can measure the optimality gaps with QUEKO. In our study, large gaps were found, even up to 45x on some near-term feasible QUEKO circuits.
After we revealed the optimality gaps, we went on to develop an optimal/exact LSQC tool, OLSQ. We represented the solution space in a more compact way, resulting in orders-of-magnitubes reductions in time and memory. By eliminating some redundant variables between mapping transformations, we arrived at a more scalable, nearly-optimal solution, transition-based (TB-) OLSQ. It can reduce 70% SWAP cost in geomean and increase fidelity by 1.3x in geomean compared to leading related works. We also applied some domain-specific knowledge to adjust TB-OLSQ in the LSQC of QAOA circuits, resulting in further reductions in depth and SWAP cost. A microgrant for open-source OLSQ has been granted by Unitary Fund.