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 Journal on Emerging and Selected Topics in Circuits and Systems

A Heuristic for Linear Nearest Neighbor Realization of Quantum Circuits by SWAP Gate Insertion Using -Gate Lookahead

Abhoy Kole, Kamalika Datta, Indranil Sengupta

Published Mar 1, 2016• 71 citations
Publisher

Abstract

With recent interest in reversible and quantum computation, research in synthesis of reversible and quantum circuits has increased in momentum. With additional requirements of neighborhood interactions among qubits (with two basis states) being a necessity in some physical realizations, several works on obtaining nearest neighbor quantum gate realization by inserting SWAP gates have been reported. These methods are based on two broad optimization approaches, one based on global ordering, where qubits are ordered over the whole netlist, and the other based on local ordering for minimizing SWAP gate insertions on smaller segments of netlists. Further reductions in cost are possible by using multi-valued qudits that have more than two basis states. The present paper considers a quantum circuit based on the NCV library, and proposes a better SWAP gate insertion method based on local ordering that uses an N-gate lookahead approach to reduce cost. Experimental results on benchmark circuits and comparison against published works confirm the benefits of the proposed approach, with improvements over reported works obtained in the range of 27%-43% on the average and 54%-63% in the best case. The method is also scalable for larger circuits, with the longest runtime observed as 10 minutes.

DOI
10.1109/jetcas.2016.2528720

Related papers

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

Improved Look-Ahead Approaches for Nearest Neighbor Synthesis of 1D Quantum Circuits

Anirban Bhattacharjee, Chandan Bandyopadhyay, Robert Wille +2 more

In the present era of computation, quantum computing may offer a new direction as it allows to solve certain problems significantly faster than classical solutions. But it also has been found that there are several constrains in performing a successful realization of quantum circuits. One such constraint is the nearest neighbor (NN) criterion which states that qubits which interact with each other have to be adjacent. Motivated by this objective, in this work we propose a linear qubit placement technique that effectively rearranges the qubits and transforms quantum circuits to improved NN-based designs by inserting SWAPs. Furthermore, for placing these SWAPs in appropriate positions, we implemented a look-ahead strategy that considers the effect of the rest of the gates and computes a corresponding impact value which guides the insertion of the SWAP gates. To this extent, we consider three different strategies to evaluate the corresponding "look-ahead effects" and their influence on existing gates. At the end of this work, we have evaluated the developed methodology over a wide range of benchmarks and compared the results with existing related works. In this comparison, we have seen that the proposed technique outperforms the related works and provides substantial reductions in SWAP overhead.

International Conference on VLSI Design•Jan 1, 2019•17 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•42 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•5 citations

A Novel Approach for Nearest Neighbor Realization of 2D Quantum Circuits

Anirban Bhattacharjee, Chandan Bandyopadhyay, Robert Wille +2 more

Since decades, quantum computing has received tremendous attention among the researchers due to its dominance over classical computing. But simultaneously it has faced some design challenges and implementation constraints in this long run. One such constraint to build quantum circuits is to satisfy the so-called Nearest Neighbor (NN) property in the implemented circuits. Using SWAP gates, this constraint can be satisfied. But this leads to another design issue, namely how to determine such NN designs with a minimum use of SWAP gates. In way to further explore this area, in this work, we propose a heuristic approach for efficient NN complaint representation of quantum circuits in 2D space. The developed technique is segmented in three stages - qubit selection, qubit placement and SWAP gate insertion. The stated approach has been tested over a wide spectrum of benchmarks and reductions in cost parameters are observed. Improvement of more than 17%, 3% over 2D designs and 35%, 22% over 1D designs on SWAP count and quantum cost can be reported, respectively.

IEEE Computer Society Annual Symposium on VLSI•Jul 1, 2018•35 citations

Linear Nearest Neighbor Realization of Quantum Circuits Using Clustering and Look-ahead Policy

Anirban Bhattacharjee, Chandan Bandyopadhyay, Bappaditya Mondal +1 more

In the last couple of years, quantum computing has come out as emerging trends of computation not only due to its immense popularity but also for its commitment towards physical realization of quantum circuit in on-chip units. At the same time, the process of physical realization has faced several design constraints and one such problem is nearest neighbor (NN) enforcement which demands all the operating qubits to be placed adjacent in the implementable circuit. Though SWAP gate embedment can transform a design into NN architecture, it still creates overhead in the design. So, designing algorithms to restrict the use of SWAPs bears high importance. Considering this fact, in this work, we are proposing a heuristic-based improved qubit placement strategy for efficient implementation of NN circuit. Two different design policies are being developed here. In the first scheme, a global reordering technique based on clustering approach is shown. In the second scheme, a local reordering technique based on look-ahead policy is developed. This look-ahead strategy considers the impact over the gates in the circuit and thereby estimates the effect using a cost metric to decide the suitable option for SWAP implementation. Furthermore, the joint use of both the ordering schemes also has been explored here. To ascertain the correctness of our design algorithms, we have tested them over a wide range of benchmarks and the obtained results are compared with some state-of-the-art design approaches. From this comparison, we have witnessed a considerable reduction on SWAP cost in our design scheme against the reported works’ results.

Journal of Circuits Systems and Computers•Jul 18, 2020•2 citations
With recent interest in reversible and quantum computation, research in synthesis of reversible and quantum circuits has increased in momentum. With additional requirements of neighborhood interactions among qubits (with two basis states) being a necessity in some physical realizations, several works on obtaining nearest neighbor quantum gate realization by inserting SWAP gates have been reported. These methods are based on two broad optimization approaches, one based on global ordering, where qubits are ordered over the whole netlist, and the other based on local ordering for minimizing SWAP gate insertions on smaller segments of netlists. Further reductions in cost are possible by using multi-valued qudits that have more than two basis states. The present paper considers a quantum circuit based on the NCV library, and proposes a better SWAP gate insertion method based on local ordering that uses an N-gate lookahead approach to reduce cost. Experimental results on benchmark circuits and comparison against published works confirm the benefits of the proposed approach, with improvements over reported works obtained in the range of 27%-43% on the average and 54%-63% in the best case. The method is also scalable for larger circuits, with the longest runtime observed as 10 minutes.
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.
In the present era of computation, quantum computing may offer a new direction as it allows to solve certain problems significantly faster than classical solutions. But it also has been found that there are several constrains in performing a successful realization of quantum circuits. One such constraint is the nearest neighbor (NN) criterion which states that qubits which interact with each other have to be adjacent. Motivated by this objective, in this work we propose a linear qubit placement technique that effectively rearranges the qubits and transforms quantum circuits to improved NN-based designs by inserting SWAPs. Furthermore, for placing these SWAPs in appropriate positions, we implemented a look-ahead strategy that considers the effect of the rest of the gates and computes a corresponding impact value which guides the insertion of the SWAP gates. To this extent, we consider three different strategies to evaluate the corresponding "look-ahead effects" and their influence on existing gates. At the end of this work, we have evaluated the developed methodology over a wide range of benchmarks and compared the results with existing related works. In this comparison, we have seen that the proposed technique outperforms the related works and provides substantial reductions in SWAP overhead.
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.
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.
Since decades, quantum computing has received tremendous attention among the researchers due to its dominance over classical computing. But simultaneously it has faced some design challenges and implementation constraints in this long run. One such constraint to build quantum circuits is to satisfy the so-called Nearest Neighbor (NN) property in the implemented circuits. Using SWAP gates, this constraint can be satisfied. But this leads to another design issue, namely how to determine such NN designs with a minimum use of SWAP gates. In way to further explore this area, in this work, we propose a heuristic approach for efficient NN complaint representation of quantum circuits in 2D space. The developed technique is segmented in three stages - qubit selection, qubit placement and SWAP gate insertion. The stated approach has been tested over a wide spectrum of benchmarks and reductions in cost parameters are observed. Improvement of more than 17%, 3% over 2D designs and 35%, 22% over 1D designs on SWAP count and quantum cost can be reported, respectively.
In the last couple of years, quantum computing has come out as emerging trends of computation not only due to its immense popularity but also for its commitment towards physical realization of quantum circuit in on-chip units. At the same time, the process of physical realization has faced several design constraints and one such problem is nearest neighbor (NN) enforcement which demands all the operating qubits to be placed adjacent in the implementable circuit. Though SWAP gate embedment can transform a design into NN architecture, it still creates overhead in the design. So, designing algorithms to restrict the use of SWAPs bears high importance. Considering this fact, in this work, we are proposing a heuristic-based improved qubit placement strategy for efficient implementation of NN circuit. Two different design policies are being developed here. In the first scheme, a global reordering technique based on clustering approach is shown. In the second scheme, a local reordering technique based on look-ahead policy is developed. This look-ahead strategy considers the impact over the gates in the circuit and thereby estimates the effect using a cost metric to decide the suitable option for SWAP implementation. Furthermore, the joint use of both the ordering schemes also has been explored here. To ascertain the correctness of our design algorithms, we have tested them over a wide range of benchmarks and the obtained results are compared with some state-of-the-art design approaches. From this comparison, we have witnessed a considerable reduction on SWAP cost in our design scheme against the reported works’ results.