2020/02/29 by Daniel Bochen Tan, Bochen Tan, Jason Cong · 92 citations
Computer Science · Engineering · Physics and Astronomy · #Algorithm #Computational science #Computer engineering #Computer science #Construct (python library) #Electrical engineering #Electronic circuit #Engineering #IBM #Low-power high-performance VLSI design #Parallel Computing and Optimization Techniques #Physics #Programming language #Quantum #Quantum Computing Algorithms and Architecture #Quantum circuit #Quantum computer #Quantum gate #Quantum network #Surprise #Theoretical computer science #cs.AR #quant-ph
paper · pdf · doi:10.1109/tc.2020.3009140
published in IEEE Transactions on Computers 70(9), 1363-1373 (Institute of Electrical and Electronics Engineers) · 17 pages, 8 figures
arxiv created 2020/07/13 · openalex publication_date 2020/07/14 · arxiv updated 2020/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Layout synthesis, an important step in quantum computing, processes quantum circuits to satisfy device layout constraints. In this paper, we construct QUEKO benchmarks for this problem, which have known optimal depths and gate counts. We use QUEKO to evaluate the optimality of current layout synthesis tools, including Cirq from Google, Qiskit from IBM, t|ket) from Cambridge Quantum Computing, and a recent academic work. To our surprise, despite over a decade of research and development by academia and industry on compilation and synthesis for quantum circuits, we are still able to demonstrate large optimality gaps: 1.5-12x on average on a smaller device and 5-45x on average on a larger device. This suggests substantial room for improvement of the efficiency of quantum computer by better layout synthesis tools. Finally, we also prove the NP-completeness of the layout synthesis problem for quantum computing. We have made the QUEKO benchmarks open-source.