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 Transactions on Computer-Aided Design of Integrated Circuits and Systems

Exact Synthesis of Nearest Neighbor Compliant Quantum Circuits in 2-D Architecture and Its Application to Large-Scale Circuits

Jingwen Ding, Shigeru Yamashita

Published Mar 27, 2019• 26 citations
Publisher

Abstract

In this paper, we propose an exact method of directly synthesizing a nearest neighbor compliant (NNC) quantum circuit with the smallest depth in 2-D architecture, given a reversible function. Our method maps the synthesis problem to a Boolean satisfiability (SAT) problem and uses a satisfiability modulo theories (SMT) solver to find an assignment of a network of allowed quantum gates. Since an SMT solver performs an exhaustive search, it can be ensured that on a specific qubit placement, the NNC quantum circuit synthesized by our method has the smallest number of quantum gates. However, the exhaustive search also makes our exact method not scale well. For that reason, we propose another method of applying our exact method in the local synthesis of large-scale circuits, to in parallel synthesize sub-NNC quantum circuits. From the experimental results, the quantum costs of the NNC quantum circuits synthesized by our methods are reduced by an average of 23.89%, when compared to an optimal heuristic method which determines the smallest number of SWAP gates in 2-D architecture.

DOI
10.1109/tcad.2019.2907919

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

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

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 method for synthesis and optimization for linear nearest neighbor quantum circuits by parallel processing

Zongyuan Zhang, Zhijin Guan, Hong Zhang +2 more

In order to realize the linear nearest neighbor{(LNN)} of the quantum circuits and reduce the quantum cost of linear reversible quantum circuits, a method for synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication of the structure of the quantum circuit is proposed. This method shows the matrix representation of linear quantum circuits by multiplying matrices of different parts of the whole circuit. The LNN realization by adding the SWAP gates is proposed and the equivalence of two ways of adding the SWAP gates is proved. The elimination rules of the SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose an algorithm based on parallel processing in order to effectively reduce the time consumption for large-scale quantum circuits. Experiments show that the quantum cost can be improved by 34.31\% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm. The average time optimization ratio of the benchmark large-scale circuits in RevLib processed by the parallel algorithm is {95.57\%} comparing with the serial algorithm.

Quantum Information and Computation•Nov 1, 2018•3 citations

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•95 citations

Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits

Aaron Lye, Robert Wille, Rolf Drechsler

Motivated by the promises of significant speed-ups for certain problems, quantum computing received significant attention in the past. While much progress has been made in the development of synthesis methods for quantum circuits, new physical developments constantly lead to new constraints to be addressed. The limited interaction distance between the respective qubits (i.e. nearest neighbor optimization) has already been considered intensely. But with the emerge of multi-dimensional quantum architectures, new physical requirements came up for which only a few automatic synthesis solutions exist yet all of them of heuristic nature. In this work, we propose an exact scheme for nearest neighbor optimization in multi-dimensional quantum circuits. Although the complexity of the problem is a serious obstacle, our experimental evaluation shows that the proposed solution is sufficient to allow for a qualitative evaluation of the respective optimization steps. Besides that, this enabled an exact comparison to heuristical results for the first time.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2015•106 citations
In this paper, we propose an exact method of directly synthesizing a nearest neighbor compliant (NNC) quantum circuit with the smallest depth in 2-D architecture, given a reversible function. Our method maps the synthesis problem to a Boolean satisfiability (SAT) problem and uses a satisfiability modulo theories (SMT) solver to find an assignment of a network of allowed quantum gates. Since an SMT solver performs an exhaustive search, it can be ensured that on a specific qubit placement, the NNC quantum circuit synthesized by our method has the smallest number of quantum gates. However, the exhaustive search also makes our exact method not scale well. For that reason, we propose another method of applying our exact method in the local synthesis of large-scale circuits, to in parallel synthesize sub-NNC quantum circuits. From the experimental results, the quantum costs of the NNC quantum circuits synthesized by our methods are reduced by an average of 23.89%, when compared to an optimal heuristic method which determines the smallest number of SWAP gates in 2-D architecture.
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.
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.
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 order to realize the linear nearest neighbor{(LNN)} of the quantum circuits and reduce the quantum cost of linear reversible quantum circuits, a method for synthesizing and optimizing linear reversible quantum circuits based on matrix multiplication of the structure of the quantum circuit is proposed. This method shows the matrix representation of linear quantum circuits by multiplying matrices of different parts of the whole circuit. The LNN realization by adding the SWAP gates is proposed and the equivalence of two ways of adding the SWAP gates is proved. The elimination rules of the SWAP gates between two overlapped adjacent quantum gates in different cases are proposed, which reduce the quantum cost of quantum circuits after realizing the LNN architecture. We propose an algorithm based on parallel processing in order to effectively reduce the time consumption for large-scale quantum circuits. Experiments show that the quantum cost can be improved by 34.31\% on average and the speed-up ratio of the GPU-based algorithm can reach 4 times compared with the CPU-based algorithm. The average time optimization ratio of the benchmark large-scale circuits in RevLib processed by the parallel algorithm is {95.57\%} comparing with the serial algorithm.
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.
Motivated by the promises of significant speed-ups for certain problems, quantum computing received significant attention in the past. While much progress has been made in the development of synthesis methods for quantum circuits, new physical developments constantly lead to new constraints to be addressed. The limited interaction distance between the respective qubits (i.e. nearest neighbor optimization) has already been considered intensely. But with the emerge of multi-dimensional quantum architectures, new physical requirements came up for which only a few automatic synthesis solutions exist yet all of them of heuristic nature. In this work, we propose an exact scheme for nearest neighbor optimization in multi-dimensional quantum circuits. Although the complexity of the problem is a serious obstacle, our experimental evaluation shows that the proposed solution is sufficient to allow for a qualitative evaluation of the respective optimization steps. Besides that, this enabled an exact comparison to heuristical results for the first time.