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

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Mapping Nearest Neighbor Compliant Quantum Circuits Onto a 2-D Hexagonal Architecture

Kuan-Yu Chang, Chun‐Yi Lee

Published Nov 13, 2021• 13 citations
Publisher

Abstract

Quantum algorithms can be described as quantum circuits and are supposed to be carried out on an ideal quantum device that is far from current ones. The current quantum devices have a significant limitation on the connectivity between quantum bits. In other words, a quantum bit is only allowed to interact with its nearest neighbors (NNs). In reality, quantum bits have to be placed on a grid, where the connectivity between quantum bits is predefined. The predefined connectivity of a grid further determines the possible range of architectures of a quantum device after the placement of quantum bits. In this article, we propose to place quantum bits based on a 2-D hexagonal architecture rather than a 2-D Cartesian architecture. To validate the effectiveness, we leverage a workflow for mapping NN compliant quantum circuits onto targeting grids, where the workflow consists of a global reordering strategy and a local reordering strategy. With the advantages of the hexagonal grid, the overhead of making quantum circuits NN compliant is reduced significantly compared with the Cartesian grid. We also provide a comprehensive set of ablation analyses to gain a better understanding of the contributions of the components within our workflow. According to the experimental results, when changing the grid type from Cartesian to hexagonal, the global reordering strategy is crucial for small quantum circuits. In contrast, the local reordering strategy is more important than the global reordering strategy for large quantum circuits.

DOI
10.1109/tcad.2021.3127868

Related papers

Exploiting the Extended Neighborhood of Hexagonal Qubit Architecture for Mapping Quantum Circuits

Abhoy Kole, Kamalika Datta, Indranil Sengupta +1 more

In this work mapping of quantum circuits to regular hexagonal grid with coupling degree of six has been investigated. Architectures involving superconducting qubits impose restrictions on 2-qubit gate operations to be carried out only between physically coupled qubits, also referred to as nearest-neighbor (NN) constraint. The noise introduced by the 2-qubit gates and the execution time greatly affect the computational reliability. Existing mapping techniques suffer either from the adopted approach to reduce gate overhead or from their inability to take advantage of such architectural regularity. We outlined three different qubit mapping approaches using Remote-CNOT templates, Swap gates and combination of both. We show the benefits of assigning the Cartesian coordinate system in hexagonal grid for runtime elevation and devised approaches for reduction in gate overheads. While the template-based approach gives a strict upper bound of additional gate overheads for a particular qubit mapping, the combined approach provides better result employing a larger lookahead window. Experiments on benchmark quantum circuits confirm that the proposed Swap-based method provides an average \(25\%\) improvement in gate overheads over a recent work and the combined approach contributes further \(15\%\) average improvement on the result at the expense of a little higher runtime.

ACM Journal on Emerging Technologies in Computing Systems•Aug 20, 2024•2 citations

A method of mapping and nearest neighbor optimization for 2-D quantum circuits

Yuxin Zhang, Zhijin Guan, Longyong Ji +2 more

In some practical quantum physical architectures, the qubits need to be distributed on 2-dimensional (2-D) grid structure to implement quantum computation. In order to map an 1-dimensional (1-D) quantum circuit into a 2-D grid structure and satisfy the nearest neighbor constraint of qubit interaction in the grid structure, a mapping method from 1-D quantum circuit to 2-D grid structure is proposed in this paper. This method firstly determines the order of placing qubits, and then presents the layout strategy of qubits in 2-D grid. We also proposed an algorithm for establishing interaction paths between non-adjacent qubits in 2-D grid structure, which can satisfy the physical constraints of the interaction of quantum bits in the grid in the process of mapping an 1-D quantum circuit to a 2-D grid structure. For some benchmark circuits, after using the method of this paper to place qubits, it is possible to make every 2-qubit gate in the circuit have a nearest neighbor, so that there is no need to use SWAP gate to establish channel routing. Compared with the latest available methods, the average optimization rate is 82.38%.

Quantum Information and Computation•Mar 1, 2020•1 citation

Nearest Neighbor Mapping of Quantum Circuits to Two-Dimensional Hexagonal Qubit Architecture

Kamalika Datta, Abhoy Kole, Indranil Sengupta +1 more

Motivated by physical realization of hexagonal architectures, in this paper we have introduced the hexagonal neighborhood structure for a set of qubits in a two-dimensional (2-D) plane along with a simple measure for estimating neighborhood distance. As compared to the traditional layout of qubits on a 2-D Cartesian plane, the hexagonal arrangement offers greater flexibility in mapping the logical qubits from a quantum circuit into an array of physical qubits. In most of the prior works, the neighborhood cost is estimated as number of Swap operations required to ensure that all 2-qubit quantum gates operate on physically adjacent qubits. However, in recent times, CNOT Templates have been used to execute 2-qubit gates where the interacting qubits are not adjacent to each other. In this paper we exploit the benefits of CNOT Templates in mapping quantum circuits to hexagonal 2-D arrays. We propose an evolutionary algorithm to obtain a good placement of qubits in the hexagonal structure. We also show the benefits of this approach over a simple greedy qubit placement method. We have carried out experiments on a set of benchmark suites to evaluate the efficiency of the proposed approach. The results show an average improvement of 42.9% over a very recent state-of-the-art method.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2022•8 citations

An Efficient 2D Mapping of Quantum Circuits to Nearest Neighbor Designs

Anirban Bhattacharjee, Hafizur Rahaman

In the last few years, tremendous improvement in the field of quantum computing has been witnessed. Although quantum technologies such as ion-trap, NMR, quantum dots have emerged as the promising platforms for implementing quantum circuits but these technologies have faced several design issues. One such important design problem is the nearest neighbor condition, which requires the qubits to interact with adjacent neighbors. This problem can be addressed by adding SWAP gates in the circuit. By doing so, the overhead in the circuit increases thus NN designs with minimum number of SWAP gates need to be developed. Focusing on this, here, in this work, we introduce a heuristic design method for efficient NN realization of quantum circuits in 2D architecture. Our NN transformation process is carried out in two phases, where initially in the first phase, the input circuit is mapped to 2D configuration using a qubit placement strategy and then in the second phase NN designs are obtained through SWAP gate insertion. At the end, the design algorithm has been evaluated over a large set of benchmark functions and the results are compared with some of the existing works. From this comparison, it is seen that our proposed method performs better than the reported works.

IEEE International Symposium on Smart Electronic Systems (iSES)•Dec 1, 2021•2 citations

A Novel 2D Mapping Scheme for Nearest Neighbor Design of Quantum Circuits

Subham Kumar, Anirban Bhattacharjee, Sudip Ghosh +1 more

In the last few years, quantum computing has gained the attention of the researchers due to its ability to perform parallel and exponentially faster computation over classical computing. One of the prominent challenges for quantum circuits is to satisfy the nearest neighbor (NN) condition, i.e., the qubits of the computing gate must be placed adjacent. Based on this fact, here, in this paper, we have proposed a heuristic synthesis workflow to realize NN circuits in 2D grid configuration. The implemented approach has been evaluated over a broad range of benchmark circuits and we have reported the best results. To validate the efficiency of the stated approach, we have compared it with the previously reported works, an average improvement of 15.94%, 8.89% and 10.98% are obtained over the existing 2D works, and 44.72% and 70.35% are obtained over existing 1D works, respectively.

IEEE International Conference of Electron Devices Society Kolkata Chapter (EDKCON)•Nov 26, 2022•2 citations

Mapping quantum circuits on 3D nearest-neighbor architectures

Azim Farghadan, Naser Mohammadzadeh

Abstract In some quantum technologies, an interaction is only allowed between physically adjacent qubits, hence the nearest-neighbor requirement is needed. In such technologies, quantum gates are limited to operate on adjacent qubits. To make a quantum circuit compliant with the nearest-neighbor requirement, SWAP gates are inserted into the circuit to move the interacting qubits of a gate to be adjacent to each other. The mapping of qubits on the physical environment has an important role on reducing the number of SWAP gates and thus the circuit latency. Focusing on this issue, in this paper, a method is proposed that maps a quantum circuit onto a 3D physical hardware such as a 3D optical lattice. A new methodology for this mapping problem is proposed based on a complex network spectral clustering algorithm and graph theory, which are suitable for very large scale networks. It includes three steps: finding the order of qubit mapping, placing physical qubits, and routing. Simulation results show that the proposed mapping approach not only decreases the average number of SWAP gates by about 37% but also improves the average runtime by about 87% for the 2D architecture compared to PAQCS. Moreover, it reduces the average number of SWAP gates for the 3D architecture by 17.1% compared to the best studies in the literatures.

Quantum Science and Technology•Apr 9, 2019•11 citations
Quantum algorithms can be described as quantum circuits and are supposed to be carried out on an ideal quantum device that is far from current ones. The current quantum devices have a significant limitation on the connectivity between quantum bits. In other words, a quantum bit is only allowed to interact with its nearest neighbors (NNs). In reality, quantum bits have to be placed on a grid, where the connectivity between quantum bits is predefined. The predefined connectivity of a grid further determines the possible range of architectures of a quantum device after the placement of quantum bits. In this article, we propose to place quantum bits based on a 2-D hexagonal architecture rather than a 2-D Cartesian architecture. To validate the effectiveness, we leverage a workflow for mapping NN compliant quantum circuits onto targeting grids, where the workflow consists of a global reordering strategy and a local reordering strategy. With the advantages of the hexagonal grid, the overhead of making quantum circuits NN compliant is reduced significantly compared with the Cartesian grid. We also provide a comprehensive set of ablation analyses to gain a better understanding of the contributions of the components within our workflow. According to the experimental results, when changing the grid type from Cartesian to hexagonal, the global reordering strategy is crucial for small quantum circuits. In contrast, the local reordering strategy is more important than the global reordering strategy for large quantum circuits.
In this work mapping of quantum circuits to regular hexagonal grid with coupling degree of six has been investigated. Architectures involving superconducting qubits impose restrictions on 2-qubit gate operations to be carried out only between physically coupled qubits, also referred to as nearest-neighbor (NN) constraint. The noise introduced by the 2-qubit gates and the execution time greatly affect the computational reliability. Existing mapping techniques suffer either from the adopted approach to reduce gate overhead or from their inability to take advantage of such architectural regularity. We outlined three different qubit mapping approaches using Remote-CNOT templates, Swap gates and combination of both. We show the benefits of assigning the Cartesian coordinate system in hexagonal grid for runtime elevation and devised approaches for reduction in gate overheads. While the template-based approach gives a strict upper bound of additional gate overheads for a particular qubit mapping, the combined approach provides better result employing a larger lookahead window. Experiments on benchmark quantum circuits confirm that the proposed Swap-based method provides an average 25%25\%25% improvement in gate overheads over a recent work and the combined approach contributes further 15%15\%15% average improvement on the result at the expense of a little higher runtime.
In some practical quantum physical architectures, the qubits need to be distributed on 2-dimensional (2-D) grid structure to implement quantum computation. In order to map an 1-dimensional (1-D) quantum circuit into a 2-D grid structure and satisfy the nearest neighbor constraint of qubit interaction in the grid structure, a mapping method from 1-D quantum circuit to 2-D grid structure is proposed in this paper. This method firstly determines the order of placing qubits, and then presents the layout strategy of qubits in 2-D grid. We also proposed an algorithm for establishing interaction paths between non-adjacent qubits in 2-D grid structure, which can satisfy the physical constraints of the interaction of quantum bits in the grid in the process of mapping an 1-D quantum circuit to a 2-D grid structure. For some benchmark circuits, after using the method of this paper to place qubits, it is possible to make every 2-qubit gate in the circuit have a nearest neighbor, so that there is no need to use SWAP gate to establish channel routing. Compared with the latest available methods, the average optimization rate is 82.38%.
Motivated by physical realization of hexagonal architectures, in this paper we have introduced the hexagonal neighborhood structure for a set of qubits in a two-dimensional (2-D) plane along with a simple measure for estimating neighborhood distance. As compared to the traditional layout of qubits on a 2-D Cartesian plane, the hexagonal arrangement offers greater flexibility in mapping the logical qubits from a quantum circuit into an array of physical qubits. In most of the prior works, the neighborhood cost is estimated as number of Swap operations required to ensure that all 2-qubit quantum gates operate on physically adjacent qubits. However, in recent times, CNOT Templates have been used to execute 2-qubit gates where the interacting qubits are not adjacent to each other. In this paper we exploit the benefits of CNOT Templates in mapping quantum circuits to hexagonal 2-D arrays. We propose an evolutionary algorithm to obtain a good placement of qubits in the hexagonal structure. We also show the benefits of this approach over a simple greedy qubit placement method. We have carried out experiments on a set of benchmark suites to evaluate the efficiency of the proposed approach. The results show an average improvement of 42.9% over a very recent state-of-the-art method.
In the last few years, tremendous improvement in the field of quantum computing has been witnessed. Although quantum technologies such as ion-trap, NMR, quantum dots have emerged as the promising platforms for implementing quantum circuits but these technologies have faced several design issues. One such important design problem is the nearest neighbor condition, which requires the qubits to interact with adjacent neighbors. This problem can be addressed by adding SWAP gates in the circuit. By doing so, the overhead in the circuit increases thus NN designs with minimum number of SWAP gates need to be developed. Focusing on this, here, in this work, we introduce a heuristic design method for efficient NN realization of quantum circuits in 2D architecture. Our NN transformation process is carried out in two phases, where initially in the first phase, the input circuit is mapped to 2D configuration using a qubit placement strategy and then in the second phase NN designs are obtained through SWAP gate insertion. At the end, the design algorithm has been evaluated over a large set of benchmark functions and the results are compared with some of the existing works. From this comparison, it is seen that our proposed method performs better than the reported works.
In the last few years, quantum computing has gained the attention of the researchers due to its ability to perform parallel and exponentially faster computation over classical computing. One of the prominent challenges for quantum circuits is to satisfy the nearest neighbor (NN) condition, i.e., the qubits of the computing gate must be placed adjacent. Based on this fact, here, in this paper, we have proposed a heuristic synthesis workflow to realize NN circuits in 2D grid configuration. The implemented approach has been evaluated over a broad range of benchmark circuits and we have reported the best results. To validate the efficiency of the stated approach, we have compared it with the previously reported works, an average improvement of 15.94%, 8.89% and 10.98% are obtained over the existing 2D works, and 44.72% and 70.35% are obtained over existing 1D works, respectively.
Abstract In some quantum technologies, an interaction is only allowed between physically adjacent qubits, hence the nearest-neighbor requirement is needed. In such technologies, quantum gates are limited to operate on adjacent qubits. To make a quantum circuit compliant with the nearest-neighbor requirement, SWAP gates are inserted into the circuit to move the interacting qubits of a gate to be adjacent to each other. The mapping of qubits on the physical environment has an important role on reducing the number of SWAP gates and thus the circuit latency. Focusing on this issue, in this paper, a method is proposed that maps a quantum circuit onto a 3D physical hardware such as a 3D optical lattice. A new methodology for this mapping problem is proposed based on a complex network spectral clustering algorithm and graph theory, which are suitable for very large scale networks. It includes three steps: finding the order of qubit mapping, placing physical qubits, and routing. Simulation results show that the proposed mapping approach not only decreases the average number of SWAP gates by about 37% but also improves the average runtime by about 87% for the 2D architecture compared to PAQCS. Moreover, it reduces the average number of SWAP gates for the 3D architecture by 17.1% compared to the best studies in the literatures.