Jason Cong talks about
Compilation for Quantum Computing: Gap Analysis and Optimal Solution

Papers in this session.

From the abstract:

As quantum computing devices continues to scale up, we would like to access the quality of the existing quantum compilation (or design automation) tools. As the first step, we focus on the layout synthesis step. We develop a novel method to construct a family of quantum circuits with known optimal, QUEKO, which have known optimal depths and gate counts on a given quantum device coupling graph. With QUEKO, we evaluated several leading industry and academic LSQC tools, including Cirq from Google, Qiskit from IBM, and t|ket from CQC.

We found rather surprisingly large optimality gaps, up to 45x on even near-term feasible circuits. Then, we went on to develop a tool for optimal layout synthesis for quantum computing, named OLSQ, which formulates LSQC as a mathematical optimization problem. OLSQ more compactly represents the solution space than previous optimal solutions and achieved exponential reduction in computational complexity.