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 Conference on Quantum Computing and Engineering (QCE)

Optimization for Gaussian Elimination-Based NNA-Compliant Circuit Synthesis Method by Inserting CN OT Gates

Zhijun Qi, Atsushi Matsuo, Shigeru Yamashita

Published Sep 15, 2024• 1 citation
Publisher

Abstract

Quantum circuits should comply with the Nearest Neighbor Architecture (NNA), which primarily supports only two-qubit operations between adjacent qubits. Typically, con-verting a quantum circuit to an NNA -compliant circuit involves the insertion of SWAP gates. However, employing Gaussian Elimination often results in a smaller NNA -compliant quantum circuit. If we fix the order of qubits to apply Gaussian Elimination (GE), it appears there is no room to improve the GE-based synthesis method. This paper reveals that we can enhance the GE-based method by inserting CNOT gates before and/or after a target circuit in many cases. As a result, we achieve a reduction of approximately 16% in the number of CNOT gates by inserting CNOT gates into the target circuits compared to the original GE-based method. Additionally, we utilize a Simulated Annealing (SA)-based method to achieve an optimal circuit, resulting in an 18% reduction in the number of CNOT gates by inserting CNOT gates, compared to the original GE-based method.

DOI
10.1109/qce60285.2024.00116

Related papers

An SMT-Solver-Based Synthesis of NNA-Compliant Quantum Circuits Consisting of CNOT, H and T Gates

Kyohei Seino, Shigeru Yamashita

It is natural to assume that we can perform quantum operations between only two adjacent physical qubits (quantum bits) to realize a quantum computer for both the current and possible future technologies. This restriction is called the Nearest Neighbor Architecture (NNA) restriction. This paper proposes an SMT-solver-based synthesis of quantum circuits consisting of CNOT, H, and T gates to satisfy the NNA restriction. Although the existing SMT-solver-based synthesis cannot treat H and T gates directly, our method treats the functionality of quantum-specific T and H gates carefully so that we can utilize an SMT-solver to minimize the number of CNOT gates; unlike the existing SMT-solver-based methods, our method considers "Don't Care" conditions in intermediate points of a quantum circuit by exploiting the property of T gates to reduce CNOT gates. Experimental results show that our approach can reduce the number of CNOT gates by 58.11% on average compared to the naive application of the existing method which does not consider the "Don't Care" condition.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 16, 2023•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

Mapping a Quantum Circuit to 2D Nearest Neighbor Architecture by Changing the Gate Order

Wakaki Hattori, Shigeru Yamashita

This paper proposes a new approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on a two-dimensional (2D) NNA. Our new idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the sub-circuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.

IEICE Transactions on Information and Systems•Oct 31, 2019•7 citations

Utilizing Don't-Cares to Minimize CNOTs in Synthesizing NNA Compliant Quantum Circuits

David Clarino, Kyouhei Seino, Atsushi Matsuo +1 more

We propose an exact method of synthesizing Nearest Neighbor Architecture (NNA) compliant networks of CNOT gates on 2-D architecture quantum computers using SMT solvers. To minimize noisy CNOT gates in the circuit, previous methods have employed SMT solvers and partitioning to obtain a lower CNOT gate count than contemporary methods. We observe that there is no need to fix the positions of T-gates relative to the source circuit; we can freely move them relative to the original, in turn enabling the gates that implement the logic feeding into them to be freely placed. In this paper, we introduce a set of constraints based around relaxing the constraints on the logic that acts on the T-gates in the circuit. Using these, we improve both the runtime and the quantum cost of the generated circuits. We compare our method to the method by Ding et al., and find a reduction 29.22% in the runtime and 58.11% in the quantum cost. We also find an advantage vs. IBM's SabreSwap.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

Optimal SWAP gate insertion for nearest neighbor quantum circuits

Robert Wille, Aaron Lye, Rolf Drechsler

Motivated by its promising applications e.g. for database search or factorization, significant progress has been made in the development of automated design methods for quantum circuits. But in order to keep up with recent physical developments in this domain, new technological constraints have to be considered. Limited interaction distance between gate qubits is one of the most common of these constraints. This led to the development of several strategies aiming at making a given quantum circuit nearest neighbor-compliant by inserting SWAP gates into the existing structure. Usually these strategies are of heuristic nature. In this work, we present an exact approach that enables nearest neighbor-compliance by inserting a minimal number of SWAP gates. Experiments demonstrate the applicability of the approach which enabled a comparison of results obtained by heuristic methods to the actual optimum.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2014•101 citations

Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits

Robert Wille, Oliver Keszöcze, Marcel Walter +3 more

Ensuring nearest neighbor compliance of quantum circuits by inserting SWAP gates has heavily been considered in the past. Here, quantum gates are considered which work on non-adjacent qubits. SWAP gates are applied in order to “move” these qubits onto adjacent positions. However, a decision how exactly the SWAPs are “moved” has mainly been made without considering the effect a “movement” of qubits may have on the remaining circuit. In this work, we propose a methodology for nearest neighbor optimization which addresses this problem by means of a look-ahead scheme. To this end, two representative implementations are presented and discussed in detail. Experimental evaluations show that, in the best case, reductions in the number of SWAP gates of 56% (compared to the state-of-the-art methods) can be achieved following the proposed methodology.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2016•125 citations
Quantum circuits should comply with the Nearest Neighbor Architecture (NNA), which primarily supports only two-qubit operations between adjacent qubits. Typically, con-verting a quantum circuit to an NNA -compliant circuit involves the insertion of SWAP gates. However, employing Gaussian Elimination often results in a smaller NNA -compliant quantum circuit. If we fix the order of qubits to apply Gaussian Elimination (GE), it appears there is no room to improve the GE-based synthesis method. This paper reveals that we can enhance the GE-based method by inserting CNOT gates before and/or after a target circuit in many cases. As a result, we achieve a reduction of approximately 16% in the number of CNOT gates by inserting CNOT gates into the target circuits compared to the original GE-based method. Additionally, we utilize a Simulated Annealing (SA)-based method to achieve an optimal circuit, resulting in an 18% reduction in the number of CNOT gates by inserting CNOT gates, compared to the original GE-based method.
It is natural to assume that we can perform quantum operations between only two adjacent physical qubits (quantum bits) to realize a quantum computer for both the current and possible future technologies. This restriction is called the Nearest Neighbor Architecture (NNA) restriction. This paper proposes an SMT-solver-based synthesis of quantum circuits consisting of CNOT, H, and T gates to satisfy the NNA restriction. Although the existing SMT-solver-based synthesis cannot treat H and T gates directly, our method treats the functionality of quantum-specific T and H gates carefully so that we can utilize an SMT-solver to minimize the number of CNOT gates; unlike the existing SMT-solver-based methods, our method considers "Don't Care" conditions in intermediate points of a quantum circuit by exploiting the property of T gates to reduce CNOT gates. Experimental results show that our approach can reduce the number of CNOT gates by 58.11% on average compared to the naive application of the existing method which does not consider the "Don't Care" condition.
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.
This paper proposes a new approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on a two-dimensional (2D) NNA. Our new idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the sub-circuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.
We propose an exact method of synthesizing Nearest Neighbor Architecture (NNA) compliant networks of CNOT gates on 2-D architecture quantum computers using SMT solvers. To minimize noisy CNOT gates in the circuit, previous methods have employed SMT solvers and partitioning to obtain a lower CNOT gate count than contemporary methods. We observe that there is no need to fix the positions of T-gates relative to the source circuit; we can freely move them relative to the original, in turn enabling the gates that implement the logic feeding into them to be freely placed. In this paper, we introduce a set of constraints based around relaxing the constraints on the logic that acts on the T-gates in the circuit. Using these, we improve both the runtime and the quantum cost of the generated circuits. We compare our method to the method by Ding et al., and find a reduction 29.22% in the runtime and 58.11% in the quantum cost. We also find an advantage vs. IBM's SabreSwap.
Motivated by its promising applications e.g. for database search or factorization, significant progress has been made in the development of automated design methods for quantum circuits. But in order to keep up with recent physical developments in this domain, new technological constraints have to be considered. Limited interaction distance between gate qubits is one of the most common of these constraints. This led to the development of several strategies aiming at making a given quantum circuit nearest neighbor-compliant by inserting SWAP gates into the existing structure. Usually these strategies are of heuristic nature. In this work, we present an exact approach that enables nearest neighbor-compliance by inserting a minimal number of SWAP gates. Experiments demonstrate the applicability of the approach which enabled a comparison of results obtained by heuristic methods to the actual optimum.
Ensuring nearest neighbor compliance of quantum circuits by inserting SWAP gates has heavily been considered in the past. Here, quantum gates are considered which work on non-adjacent qubits. SWAP gates are applied in order to “move” these qubits onto adjacent positions. However, a decision how exactly the SWAPs are “moved” has mainly been made without considering the effect a “movement” of qubits may have on the remaining circuit. In this work, we propose a methodology for nearest neighbor optimization which addresses this problem by means of a look-ahead scheme. To this end, two representative implementations are presented and discussed in detail. Experimental evaluations show that, in the best case, reductions in the number of SWAP gates of 56% (compared to the state-of-the-art methods) can be achieved following the proposed methodology.