Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2111.03716

String Abstractions for Qubit Mapping

Blake Gerard, Martin Kong

Published Nov 5, 2021• 2 citations
arXivHTMLPDF

Abstract

One of the key compilation steps in Quantum Computing (QC) is to determine an initial logical to physical mapping of the qubits used in a quantum circuit. The impact of the starting qubit layout can vastly affect later scheduling and placement decisions of QASM operations, yielding higher values on critical performance metrics (gate count and circuit depth) as a result of quantum compilers introducing SWAP operations to meet the underlying physical neighboring and connectivity constraints of the quantum device. In this paper we introduce a novel qubit mapping approach, string-based qubit mapping. The key insight is to prioritize the mapping of logical qubits that appear in longest repeating non-overlapping substrings of qubit pairs accessed. This mapping method is complemented by allocating qubits according to their global frequency usage. We evaluate and compare our new mapping scheme against two quantum compilers (QISKIT and TKET) and two device topologies, the IBM Manhattan (65 qubits) and the IBM Kolkata (27 qubits). Our results demonstrate that combining both mapping mechanisms often achieve better results than either one individually, allowing us to best QISKIT and TKET baselines, yielding between 13% and 17% average improvement in several group sizes, up to 32% circuit depth reduction and 63% gate volume improvement.

DOI
10.48550/arxiv.2111.03716

Related papers

Exploring Affine Abstractions for Qubit Mapping

Blake Gerard, Martin Kong

One of the key compilation steps in Quantum Computing (QC) is to determine an initial logical to physical mapping of the qubits used in a quantum circuit. The impact of the starting qubit layout can vastly affect later scheduling and placement decisions of QASM operations, yielding higher values on critical performance metrics (gate count and circuit depth) as a result of a quantum compilers introducing communication operations to meet the underlying physical neighboring and connectivity constraints of the quantum device.We present our ongoing work on qubit mapping with affine abstractions, which aims to compute effective initial qubit layouts. The key assumption is that the quantum program is represented in an affine representation, a property which permits us to apply aggressive program analyses to determine the potential of sharing qubit accesses among groups of quantum operations prescribed by linear and affine relations. We present preliminary results demonstrating the effectiveness of our novel approach on 69 quantum circuits, while using the QISKIT compiler on IBM Tokyo and Google Sycamore, obtaining between 16% and 21% average improvement on circuit depth and 24%–47% improvement on the number of added gates.

IEEE/ACM International Workshop on Quantum Computing Software (QCS)•Nov 1, 2021•3 citations

Enhancing Quantum Circuit Compilation with Modular Floorplanning

Giacomo Lancellotti, Giovanni Agosta, Alessandro Barenghi +1 more

Quantum circuit compilation is a multi-stage process that translates a high-level quantum circuit representation into a sequence of quantum gates that can be directly executed by a quantum machine. One of the core steps in quantum compilation is mapping, a procedure that transforms a quantum circuit into a semantically equivalent circuit while inserting additional gates to comply with the architectural constraints of the underlying quantum hardware. Current mapping techniques exhibit significant performance degradation—in terms of circuit depth and gate count—when applied to large-scale circuits containing hundreds of thousands of gates or more. In this work, we propose a novel methodology to enhance quantum compiler capabilities by adapting general principles from classical Electronic Design Automation. We model the quantum hardware as being composed of standard cells, onto which portions of the circuit are mapped using a floorplanning-based technique. This contrasts with current state-of-the-art solutions, which perform mapping at the gate level without considering any form of hierarchical abstraction. We use the ChaCha20 stream cipher as a running example to validate and explain our strategy. We evaluate our methodology using two well-known, industrial-grade quantum compilers: IBM Qiskit and Quantinuum TKET. Compared to these compilers, our approach achieves an average circuit depth reduction of 59.78% and 68.85%, respectively, and a gate count reduction of 4.07 % and 6.20 %, respectively. These results are obtained across a large set of randomly generated quantum circuit descriptions in the range of millions of gates, with varying input and output connectivity for each block in the circuit.

IEEE International Conference on Quantum Software (QSW)•Jul 7, 2025•0 citations

On the Qubit Routing Problem

Alexander Cowtan, Silas Dilkes, Duncan, Ross +3 more

We introduce a new architecture-agnostic methodology for mapping abstract quantum circuits to realistic quantum computing devices with restricted qubit connectivity, as implemented by Cambridge Quantum Computing's tket compiler. We present empirical results showing the effectiveness of this method in terms of reducing two-qubit gate depth and two-qubit gate count, compared to other implementations.

arXiv:1902.08091•Leibniz international proceedings in informatics•Jan 1, 2019•132 citations

Efficient Qubit Routing Using a Dynamically Extract-and-Route Framework

Ching-Yao Huang, Wai-Kei Mak

In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Apr 10, 2024•12 citations

Optimizing Layout Synthesis for Quantum Computing Performance

Chi‐Chou Kao, Hung-Yi Lin

In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.

Journal of Circuits Systems and Computers•Mar 6, 2025•0 citations

Recent Advances in Qubit Allocation Algorithm for NISQ Architectures

Sengthai Heng, Taekyung Kim, Youngsun Han

In recent years, the advancement of quantum computers has been improving, with its use increasing in practical applications, including noisy intermediate-scale quantum (NISQ) technology. However, an obstacle that limits quantum computer usage is the connectivity restriction between logical and physical qubits. For performing quantum entanglement on NISQ machines, two logical qubits must be mapped to physical qubit pairs that much up to the connectivity constraint. This mapping process must insert additional operations into an initial quantum circuit. Many powerful algorithms have been proposed to solve the mapping problem, which also mitigate circuit size or depth and improve the fidelity of the quantum state. In this review paper, we present various studies for solving qubit mapping or allocation problems and analyze their time complexity and methods.

IEIE Transactions on Smart Processing and Computing•Jun 22, 2021•0 citations
One of the key compilation steps in Quantum Computing (QC) is to determine an initial logical to physical mapping of the qubits used in a quantum circuit. The impact of the starting qubit layout can vastly affect later scheduling and placement decisions of QASM operations, yielding higher values on critical performance metrics (gate count and circuit depth) as a result of quantum compilers introducing SWAP operations to meet the underlying physical neighboring and connectivity constraints of the quantum device. In this paper we introduce a novel qubit mapping approach, string-based qubit mapping. The key insight is to prioritize the mapping of logical qubits that appear in longest repeating non-overlapping substrings of qubit pairs accessed. This mapping method is complemented by allocating qubits according to their global frequency usage. We evaluate and compare our new mapping scheme against two quantum compilers (QISKIT and TKET) and two device topologies, the IBM Manhattan (65 qubits) and the IBM Kolkata (27 qubits). Our results demonstrate that combining both mapping mechanisms often achieve better results than either one individually, allowing us to best QISKIT and TKET baselines, yielding between 13% and 17% average improvement in several group sizes, up to 32% circuit depth reduction and 63% gate volume improvement.
One of the key compilation steps in Quantum Computing (QC) is to determine an initial logical to physical mapping of the qubits used in a quantum circuit. The impact of the starting qubit layout can vastly affect later scheduling and placement decisions of QASM operations, yielding higher values on critical performance metrics (gate count and circuit depth) as a result of a quantum compilers introducing communication operations to meet the underlying physical neighboring and connectivity constraints of the quantum device.We present our ongoing work on qubit mapping with affine abstractions, which aims to compute effective initial qubit layouts. The key assumption is that the quantum program is represented in an affine representation, a property which permits us to apply aggressive program analyses to determine the potential of sharing qubit accesses among groups of quantum operations prescribed by linear and affine relations. We present preliminary results demonstrating the effectiveness of our novel approach on 69 quantum circuits, while using the QISKIT compiler on IBM Tokyo and Google Sycamore, obtaining between 16% and 21% average improvement on circuit depth and 24%–47% improvement on the number of added gates.
Quantum circuit compilation is a multi-stage process that translates a high-level quantum circuit representation into a sequence of quantum gates that can be directly executed by a quantum machine. One of the core steps in quantum compilation is mapping, a procedure that transforms a quantum circuit into a semantically equivalent circuit while inserting additional gates to comply with the architectural constraints of the underlying quantum hardware. Current mapping techniques exhibit significant performance degradation—in terms of circuit depth and gate count—when applied to large-scale circuits containing hundreds of thousands of gates or more. In this work, we propose a novel methodology to enhance quantum compiler capabilities by adapting general principles from classical Electronic Design Automation. We model the quantum hardware as being composed of standard cells, onto which portions of the circuit are mapped using a floorplanning-based technique. This contrasts with current state-of-the-art solutions, which perform mapping at the gate level without considering any form of hierarchical abstraction. We use the ChaCha20 stream cipher as a running example to validate and explain our strategy. We evaluate our methodology using two well-known, industrial-grade quantum compilers: IBM Qiskit and Quantinuum TKET. Compared to these compilers, our approach achieves an average circuit depth reduction of 59.78% and 68.85%, respectively, and a gate count reduction of 4.07 % and 6.20 %, respectively. These results are obtained across a large set of randomly generated quantum circuit descriptions in the range of millions of gates, with varying input and output connectivity for each block in the circuit.
In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.
In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.
In recent years, the advancement of quantum computers has been improving, with its use increasing in practical applications, including noisy intermediate-scale quantum (NISQ) technology. However, an obstacle that limits quantum computer usage is the connectivity restriction between logical and physical qubits. For performing quantum entanglement on NISQ machines, two logical qubits must be mapped to physical qubit pairs that much up to the connectivity constraint. This mapping process must insert additional operations into an initial quantum circuit. Many powerful algorithms have been proposed to solve the mapping problem, which also mitigate circuit size or depth and improve the fidelity of the quantum state. In this review paper, we present various studies for solving qubit mapping or allocation problems and analyze their time complexity and methods.