Optimality Study of Existing Quantum Computing Layout Synthesis Tools

Abstract

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, $\mathsf{t}|\mathsf{ket}⟩$ from Cambridge Quantum Computing, and 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.

arXiv comment17 pages, 8 figures

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Resource-Aware Quantum Programming with General Recursion and Quantum Control
• Automated optimization of large quantum circuits with continuous parameters
• Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Quantum Circuit Placement
• On the qubit routing problem
• Circuit Transformations for Quantum Architectures

Cited by in corpus (18)

• CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations
• Optimal Layout Synthesis for Quantum Computing
• Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era
• Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors
• Optimal Qubit Mapping with Simultaneous Gate Absorption
• On Optimal Subarchitectures for Quantum Circuit Mapping
• Improving Quantum Computation by Optimized Qubit Routing
• Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
• Supervised Learning Enhanced Quantum Circuit Transformation
• Compilation for Dynamically Field-Programmable Qubit Arrays with Efficient and Provably Near-Optimal Scheduling
• A Hardware-Aware Gate Cutting Framework for Practical Quantum Circuit Knitting
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation
• A doubly stochastic matrices-based approach to optimal qubit routing
• MLQM: Machine Learning Approach for Accelerating Optimal Qubit Mapping
• Distance-four quantum codes with combined postselection and error correction
• A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-agent Cooperation
• Special-Purpose Quantum Processor Design
• String Abstractions for Qubit Mapping