(IWQC20) Daniel Bochen Tan: Layout Synthesis for Quantum Computing: Measure, then Improve
All attendees have received an email regarding access to the QWoF Slack workspace. If you have not accepted the invitation, click this link to do so: https://join.slack.com/t/quantumweeko...
If you have accepted this invitation, click this link to access this session’s Slack Channel for live discussion and question answering: https://quantumweekoffun.slack.com/ar...
Click this link to continue to the next IWQC session: • (IWQC20) Kyle E. C. Booth: Exact and heuri...
Full talk title: Layout Synthesis for Quantum Computing: Measure, then Improve
Authors: Daniel Bochen Tan and Jason Cong
Abstract: Layout synthesis for quantum computing (LSQC) involves mapping the qubits in quantum programs to physical qubits, scheduling the quantum gates, and inserting some gates, usually SWAP gates, to resolve the hardware connectivity issues. We approach this problem with the ‘measure, then improve’ methodology. Before attempts to solve the problem directly, we first conduct some evaluations on the existing tools. Previously, benchmarks for LSQC are usually circuits of some reversible functions. However, due to the complexity of this problem, it is very hard to find the optimal solution for an arbitrary instance. Thus, we can compare the LSQC tools with each other without knowing how far they are from the optimum. To this end, we construct a family of quantum mapping examples with known optimal, QUEKO, which have known optimal depths and gate counts on given coupling graphs. With QUEKO, we evaluate several leading industry and academic LSQC tools, including Qiskit, Cirq, and t|ket, and find rather large optimality gaps, up to 45x on some near-term feasible circuits. Now that large optimality gaps are measured, we go on to the ‘improve’ stage. We develop a tool for optimal layout synthesis for quantum computing, OLSQ, which formulates LSQC as a mathematical optimization problem. OLSQ makes use of a more compact representation of the solution space, achieving orders-of-magnitude reductions in runtime and memory than previous optimal solutions. Furthermore, by removing some redundant mapping variables between mapping transformations, we arrive at a more scalable, approximate synthesizer, transition-based (TB-) OLSQ. Compared to t|ket, TB-OLSQ can reduce 70% SWAP cost in geomean on a set of arithmetic quantum circuits. TB-OLSQ can increase fidelity by 1.3x in geomean compared to TriQ, a leading academic work on fidelity optimization. We also apply some domain-specific knowledge to adjust TB-OLSQ in the LSQC of QAOA circuits, resulting in further reductions in depth and SWAP cost.