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 VLSI Design

Exploiting Negative Control Lines and Nearest Neighbor for Improved Comparator Design

Tathagato Bose, Kamalika Datta, Indranil Sengupta

Published Jan 1, 2019• 1 citation
Publisher

Abstract

In this paper, improved reversible comparator designs are investigated using Multiple Control Toffoli (MCT) gates, improving Quantum Cost (QC) and also Nearest Neighbor Cost (NNC) metrics of circuits. The proposed designs are compared with recent works and found to be efficient in terms of cost by making these nearest neighbor compliant using Swap gate insertions.

DOI
10.1109/vlsid.2019.00113

Related papers

Implementation of neareast neighbor quantum circuit with low quantum cost

Laxmidhar Biswal, Anirban Bhattachaijee, Sudip Ghosh +1 more

Primary purpose behind this work is to develop a type of quantum gate C2(iZ)/C2(-iZ) derived from unitary quantum gate C2(-I) by finding its 2ndroot. This newly introduced gate is nearest-neighbor compliant with a unit quantum cost. The main objective in deriving this quantum gate C2(iZ)/C2(-iZ) is to generate low cost MCT gates which eventually produces cost optimized NNC free reversible circuits. For systematic mapping and a fair comparison with prior works, we formed a quantum gate library that includes CNOT, NOT, H, CH, C2(-I) and C2(iZ)/C2(-iZ) gates. A mapping algorithm including the complete gate library is proposed alongwith necessary mathematical proofs. Using the gate library, we show significant cost savings is achievable over the state-of-the-art approaches, when mapping n-control Toffoli gates and chosen benchmark functions.

International Symposium on Devices, Circuits and Systems (ISDCS)•Mar 1, 2018•0 citations

Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning

Amlan Chakrabarti, Susmita Sur‐Kolay, Ayan Chaudhury

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.

arXiv:1112.0564•Dec 2, 2011•48 citations

Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques

Md. Belayet Ali, Takashi Hirayama, Katsuhisa Yamanaka +1 more

Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.

International Conference on Computational Science and Computational Intelligence (CSCI)•Dec 1, 2015•18 citations

A Novel Heuristic Method for Linear Nearest Neighbour Realization of Reversible Circuits

Anirban Bhattacharjee, Chandan Bandyopadhyay, Hafizur Rahaman

With the advancement of technological footprints, high-end computation techniques, like quantum computation, have made significant progress in the design industry. Although quantum computation has proved itself as the next-generation computing paradigm, it is facing several design challenges, and one such design issue is in the form of the Nearest Neighbour (NN)t. This much-talked NN property demands the qubits in operating quantum gates to be adjacent, and a circuit should satisfy this NN property to be eligible for implementation. Considering the importance of NN enforcement in implementing circuits, we introduce a synthesis approach for the efficient transformation of reversible circuits to equivalent LNN representations. Our main focus in this work is to minimize the use of SWAP gates in designing NN-satisfied MCT-based reversible circuits. Towards transforming input circuits to LNN architecture, we have exploited a template matching scheme followed by two-qubit reordering policies, global and local, to improve the NN designs and reduce SWAP utilization. In finding the global solution, here we have used a dynamic programming algorithm where the initial order of qubit lines gets changed, while a heuristic-based SWAP placement function is used for finding a local qubit order sequence. The proposed synthesis workflow has been tested over an extensive set of benchmark functions, and comparison with the reported design approaches showed a substantial reduction in cost parameters.

IETE Journal of Research•Feb 8, 2022•2 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

Improving the Realization of Multiple-Control Toffoli Gates Using the NCVW Quantum Gate Library

Laxmidhar Biswal, Chandan Bandyopadhyay, Robert Wille +2 more

Multiple Control Toffoli (MCT) gates are the main constituent of reversible circuits. For quantum circuits, MCT gates are realized using quantum gate libraries such as NCV or NCVW which are composed of universal quantum gates like NOT, CNOT, V/V+, and W/W+. In order to improve the design of quantum circuits, the mapping of MCT gates to a cascade of these quantum gates has to be improved as well. In this work, we propose reconfigured structures of quantum gates realizing MCT gates. To this end, we rely on the established mapping structure, but append redundant gates which can be used afterwards for simplifications. Eventually, the proposed design is mapped to an NCVW quantum circuit. We have successfully tested our mapping technique. The obtained results have experimentally been compared to related work.

International Conference on VLSI Design•Jan 1, 2016•10 citations
In this paper, improved reversible comparator designs are investigated using Multiple Control Toffoli (MCT) gates, improving Quantum Cost (QC) and also Nearest Neighbor Cost (NNC) metrics of circuits. The proposed designs are compared with recent works and found to be efficient in terms of cost by making these nearest neighbor compliant using Swap gate insertions.
Primary purpose behind this work is to develop a type of quantum gate C2(iZ)/C2(-iZ) derived from unitary quantum gate C2(-I) by finding its 2ndroot. This newly introduced gate is nearest-neighbor compliant with a unit quantum cost. The main objective in deriving this quantum gate C2(iZ)/C2(-iZ) is to generate low cost MCT gates which eventually produces cost optimized NNC free reversible circuits. For systematic mapping and a fair comparison with prior works, we formed a quantum gate library that includes CNOT, NOT, H, CH, C2(-I) and C2(iZ)/C2(-iZ) gates. A mapping algorithm including the complete gate library is proposed alongwith necessary mathematical proofs. Using the gate library, we show significant cost savings is achievable over the state-of-the-art approaches, when mapping n-control Toffoli gates and chosen benchmark functions.
Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.
Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.
With the advancement of technological footprints, high-end computation techniques, like quantum computation, have made significant progress in the design industry. Although quantum computation has proved itself as the next-generation computing paradigm, it is facing several design challenges, and one such design issue is in the form of the Nearest Neighbour (NN)t. This much-talked NN property demands the qubits in operating quantum gates to be adjacent, and a circuit should satisfy this NN property to be eligible for implementation. Considering the importance of NN enforcement in implementing circuits, we introduce a synthesis approach for the efficient transformation of reversible circuits to equivalent LNN representations. Our main focus in this work is to minimize the use of SWAP gates in designing NN-satisfied MCT-based reversible circuits. Towards transforming input circuits to LNN architecture, we have exploited a template matching scheme followed by two-qubit reordering policies, global and local, to improve the NN designs and reduce SWAP utilization. In finding the global solution, here we have used a dynamic programming algorithm where the initial order of qubit lines gets changed, while a heuristic-based SWAP placement function is used for finding a local qubit order sequence. The proposed synthesis workflow has been tested over an extensive set of benchmark functions, and comparison with the reported design approaches showed a substantial reduction in cost parameters.
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.
Multiple Control Toffoli (MCT) gates are the main constituent of reversible circuits. For quantum circuits, MCT gates are realized using quantum gate libraries such as NCV or NCVW which are composed of universal quantum gates like NOT, CNOT, V/V+, and W/W+. In order to improve the design of quantum circuits, the mapping of MCT gates to a cascade of these quantum gates has to be improved as well. In this work, we propose reconfigured structures of quantum gates realizing MCT gates. To this end, we rely on the established mapping structure, but append redundant gates which can be used afterwards for simplifications. Eventually, the proposed design is mapped to an NCVW quantum circuit. We have successfully tested our mapping technique. The obtained results have experimentally been compared to related work.