Optimal Qubit Mapping with Simultaneous Gate Absorption

Abstract

Before quantum error correction (QEC) is achieved, quantum computers focus on noisy intermediate-scale quantum (NISQ) applications. Compared to the well-known quantum algorithms requiring QEC, like Shor's or Grover's algorithm, NISQ applications have different structures and properties to exploit in compilation. A key step in compilation is mapping the qubits in the program to physical qubits on a given quantum computer, which has been shown to be an NP-hard problem. In this paper, we present OLSQ-GA, an optimal qubit mapper with a key feature of simultaneous SWAP gate absorption during qubit mapping, which we show to be a very effective optimization technique for NISQ applications. For the class of quantum approximate optimization algorithm (QAOA), an important NISQ application, OLSQ-GA reduces depth by up to 50.0% and SWAP count by 100% compared to other state-of-the-art methods, which translates to 55.9% fidelity improvement. The solution optimality of OLSQ-GA is achieved by the exact SMT formulation. For better scalability, we augment our approach with additional constraints in the form of initial mapping or alternating matching, which speeds up OLSQ-GA by up to 272X with no or little loss of optimality.

8 pages, 8 figures, to appear in ICCAD'21

References in corpus (11)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Hartree-Fock on a superconducting qubit quantum computer
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Demonstrating a Continuous Set of Two-qubit Gates for Near-term Quantum Algorithms
• Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers
• Quantum Circuit Placement
• Optimal Layout Synthesis for Quantum Computing
• Optimality Study of Existing Quantum Computing Layout Synthesis Tools
• Observation of separated dynamics of charge and spin in the Fermi-Hubbard model
• Generalized swap networks for near-term quantum computing

Cited by in corpus (10)

• Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors
• Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques
• Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
• Hardware-Conscious Optimization of the Quantum Toffoli Gate
• Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures
• Compilation for Dynamically Field-Programmable Qubit Arrays with Efficient and Provably Near-Optimal Scheduling
• Fermihedral: On the Optimal Compilation for Fermion-to-Qubit Encoding
• MIRAGE: Quantum Circuit Decomposition and Routing Collaborative Design using Mirror Gates
• Hardware-Efficient Preparation of Graph States on Near-Term Quantum Computers
• Improving Figures of Merit for Quantum Circuit Compilation