Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search

Abstract

Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This paper proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit; and (ii) searching, in a filtered and depth-limited way, a most useful SWAP combination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.4346 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.6047, 0.8154, and 1.0067 respectively.

References in corpus (4)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Quantum Circuit Placement
• On the qubit routing problem

Cited by in corpus (12)

• Mapping quantum circuits to modular architectures with QUBO
• rustworkx: A High-Performance Graph Library for Python
• Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques
• Supervised Learning Enhanced Quantum Circuit Transformation
• Lightcone Bounds for Quantum Circuit Mapping via Uncomplexity
• Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
• MLQM: Machine Learning Approach for Accelerating Optimal Qubit Mapping
• Dynamic quantum circuit compilation
• Quantum Circuit Transformation Based on Tabu Search
• A Quantum Framework for Protein Binding-Site Structure Prediction on Utility-Level Quantum Processors
• QSteed: A Resource-Virtualized and Hardware-Aware Quantum Compilation Framework for Real Quantum Computing Processors
• A Variation-Aware Quantum Circuit Mapping Approach Based on Multi-agent Cooperation