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 International Symposium on Multiple-Valued Logic (ISMVL)

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

Kamalika Datta, Abhoy Kole, Indranil Sengupta, Rolf Drechsler

Published May 1, 2022• 8 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl52857.2022.00013

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

Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization

Ritu Ranjan Shrivastwa, Kamalika Datta, Indranil Sengupta

Design and synthesis of quantum circuits have gained huge momentum during the last few years. With various physical constraint sone of the major issues is in making quantum circuits nearest neighbor complaint. The existing one and two dimensional architectures for the placement of qubits does not scale well for larger circuits. The situation thus demands for a faster approach to solve the problem. To make a quantum circuit nearest neighbor compliant, SWAP gates are inserted in the quantum gate circuit to bring the interacting qubits of a gate adjacent. We have proposed a faster method with a simple yet effective algorithm to minimize the number of SWAP gates for adjacent interactions. The time required for processing does not exceed one second even for larger benchmark circuits. The proposed method is found to reduce the number of SWAP gates on an average by 9.5% compared to the best results in previous works on 2D architectures, and by 45.7% compared to the best results on 1D architecture.

IEEE International Symposium on Nanoelectronic and Information Systems (iNIS)•Dec 1, 2015•43 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

Efficient Design of Quantum Circuits Using Nearest Neighbor Constraint in 3D Architecture

Leniency Marbaniang, Kamalika Datta

Synthesis and optimization of quantum circuits have received significant attention from researchers in recent years. Developments in the physical realization of qubits in quantum computing have led to new physical constraints to be addressed. One of the most important constraints that is considered by many researchers is the nearest neighbor constraint which limits the interaction distance between qubits for quantum gate operations. Various works have been reported in the literature that deal with nearest neighbor compliance in multi-dimensional (mostly 1D and 2D) qubit arrangements. This is normally achieved by inserting SWAP gates in the gate netlist to bring the interacting qubits closer together. The main objective function to minimize here is the number of SWAP gates. The present paper proposes an efficient qubit placement strategy in a three-dimensional (3D) grid that considers not only qubit interactions but also the relative positions of the gates in the circuit. Experimental evaluation on a number of benchmark circuits show that the proposed method reduces the number of SWAP gates by 16.2% to 47.0% on the average as compared to recently published works.

Journal of Circuits Systems and Computers•Jun 24, 2018•6 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

A New Heuristic for $N$ -Dimensional Nearest Neighbor Realization of a Quantum Circuit

Abhoy Kole, Kamalika Datta, Indranil Sengupta

One of the main challenges in quantum computing is to ensure error-free operation of the basic quantum gates. There are various implementation technologies of quantum gates for which the distance between interacting qubits must be kept within a limit for reliable operation. This leads to the so-called requirement of neighborhood arrangements of the interacting qubits, often referred to as nearest neighbor (NN) constraint. This is typically achieved by inserting SWAP gates in the quantum circuits, where a SWAP gate between two qubits exchanges their states. Minimizing the number of SWAP gates to provide NN compliance is an important problem to solve. A number of approaches have been proposed in this regard, based on local and global ordering techniques. In this paper, a generalized approach for combined local and global ordering of qubits have been proposed that is based on an improved heuristic for cost estimation and is also scalable. The approach can be extended to N -dimensional arrangement of qubits, for any arbitrary values of N . Practical constraints, however, restrict the maximum value of N to 3. Extensive experiments on benchmark functions have been carried out to evaluate the performance in terms of SWAP gate requirements. 3-D organization of qubits shows average reductions of 6.7% and 37.4%, respectively, in the number of SWAP gates over 2-D and 1-D organizations. Also compared to the best 2-D and 1-D results reported in the literature, on the average 8.7% and 8.4% reductions, respectively, are observed.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Apr 18, 2017•68 citations
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 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.
Design and synthesis of quantum circuits have gained huge momentum during the last few years. With various physical constraint sone of the major issues is in making quantum circuits nearest neighbor complaint. The existing one and two dimensional architectures for the placement of qubits does not scale well for larger circuits. The situation thus demands for a faster approach to solve the problem. To make a quantum circuit nearest neighbor compliant, SWAP gates are inserted in the quantum gate circuit to bring the interacting qubits of a gate adjacent. We have proposed a faster method with a simple yet effective algorithm to minimize the number of SWAP gates for adjacent interactions. The time required for processing does not exceed one second even for larger benchmark circuits. The proposed method is found to reduce the number of SWAP gates on an average by 9.5% compared to the best results in previous works on 2D architectures, and by 45.7% compared to the best results on 1D architecture.
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.
Synthesis and optimization of quantum circuits have received significant attention from researchers in recent years. Developments in the physical realization of qubits in quantum computing have led to new physical constraints to be addressed. One of the most important constraints that is considered by many researchers is the nearest neighbor constraint which limits the interaction distance between qubits for quantum gate operations. Various works have been reported in the literature that deal with nearest neighbor compliance in multi-dimensional (mostly 1D and 2D) qubit arrangements. This is normally achieved by inserting SWAP gates in the gate netlist to bring the interacting qubits closer together. The main objective function to minimize here is the number of SWAP gates. The present paper proposes an efficient qubit placement strategy in a three-dimensional (3D) grid that considers not only qubit interactions but also the relative positions of the gates in the circuit. Experimental evaluation on a number of benchmark circuits show that the proposed method reduces the number of SWAP gates by 16.2% to 47.0% on the average as compared to recently published works.
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%.
A New Heuristic for NNN -Dimensional Nearest Neighbor Realization of a Quantum Circuit
One of the main challenges in quantum computing is to ensure error-free operation of the basic quantum gates. There are various implementation technologies of quantum gates for which the distance between interacting qubits must be kept within a limit for reliable operation. This leads to the so-called requirement of neighborhood arrangements of the interacting qubits, often referred to as nearest neighbor (NN) constraint. This is typically achieved by inserting SWAP gates in the quantum circuits, where a SWAP gate between two qubits exchanges their states. Minimizing the number of SWAP gates to provide NN compliance is an important problem to solve. A number of approaches have been proposed in this regard, based on local and global ordering techniques. In this paper, a generalized approach for combined local and global ordering of qubits have been proposed that is based on an improved heuristic for cost estimation and is also scalable. The approach can be extended to N -dimensional arrangement of qubits, for any arbitrary values of N . Practical constraints, however, restrict the maximum value of N to 3. Extensive experiments on benchmark functions have been carried out to evaluate the performance in terms of SWAP gate requirements. 3-D organization of qubits shows average reductions of 6.7% and 37.4%, respectively, in the number of SWAP gates over 2-D and 1-D organizations. Also compared to the best 2-D and 1-D results reported in the literature, on the average 8.7% and 8.4% reductions, respectively, are observed.