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

International Conference on Emerging Trends in Information Technology and Engineering (ICETITE)

Compiling NCV Quantum Circuits for Nearest Neighbour Realization

Lalengmawia Chhangte, Alok Chakrabarty

Published Feb 1, 2020• 1 citation
Publisher

Abstract

Quantum computers that are based on superconducting and quantum dots have a fundamental requirement called Nearest Neighbour (NN) constraint satisfaction. They require interacting qubits to be directly connected (neighbours). If two non-adjacent qubits are to interact, they should be brought together first, so that interaction can occur. In this paper, we summarized state-of-the-art techniques and proposed a local ordering algorithm for transforming a given quantum circuit to a 2D NN-compliant circuit. Using the algorithm, a given circuit is decomposed into non-overlapping sub-circuits where each sub-circuit contains unique qubits. The insertion of swap gates occurs between every two consecutive sub-circuits (Ciand $C_{i+1}$) if $C_{i+1}$ do not satisfy the NN-constraint. Up to 50% reduction in swap count was obtained when compared to the most recent existing work on NCV benchmark circuits.

DOI
10.1109/ic-etite47903.2020.305

Related papers

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

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

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

Improving the Designs of Nearest Neighbour Quantum Circuits for 1D and 2D Architectures

Chandan Bandyopadhyay, Anirban Bhattacharjee, Robert Wille +2 more

In recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.

IETE Journal of Research•Sep 27, 2020•6 citations

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

Abhoy Kole, Kamalika Datta, Indranil Sengupta

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.

IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Mar 1, 2016•71 citations

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
Quantum computers that are based on superconducting and quantum dots have a fundamental requirement called Nearest Neighbour (NN) constraint satisfaction. They require interacting qubits to be directly connected (neighbours). If two non-adjacent qubits are to interact, they should be brought together first, so that interaction can occur. In this paper, we summarized state-of-the-art techniques and proposed a local ordering algorithm for transforming a given quantum circuit to a 2D NN-compliant circuit. Using the algorithm, a given circuit is decomposed into non-overlapping sub-circuits where each sub-circuit contains unique qubits. The insertion of swap gates occurs between every two consecutive sub-circuits (Ciand Ci+1C_{i+1}Ci+1​) if Ci+1C_{i+1}Ci+1​ do not satisfy the NN-constraint. Up to 50% reduction in swap count was obtained when compared to the most recent existing work on NCV benchmark circuits.
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.
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.
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 recent years, the semiconductor industry is increasingly considering alternative computation schemes and in this conjuncture quantum computing has come up as a promising alternative due its ability to perform parallel computations (by exploiting superposition) and capacity to solve some of the intractable problems exponentially faster. But one of the criteria in the realization of quantum circuits is that corresponding descriptions demand a so-called nearest neighbour (NN) constraint to be satisfied. One of the possible solutions towards satisfying such constraints is through the insertion of SWAP gates that makes the qubit interactions within a gate adjacent. But since the incorporation of SWAP gates increases the cost of the circuits, strategies should be employed which satisfy the NN constraint while placing SWAP gates so that the cost are reduced. In this work, we propose improved design strategies to realize low-cost NN-compliant quantum circuits. Two approaches are introduced, where the first approach relies on a graph traversal process and uses heuristics in critical decision-making conditions to design a 1D NN-compliant representation. The second approach considers qubit-to-qubit interactions and realizes the circuits in a 2D platform based on some weighted metric. Both the designs are evaluated over a wide spectrum of benchmarks and results have been compared with related works. In those comparisons, we have seen that our approaches perform fairly better than the reported ones.
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.