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

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, 20232 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, 201542 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 SystemsOct 31, 20197 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, 20241 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, 201495 citations

A Transformation-Based Quantum Physical Synthesis Approach for Nearest-Neighbor Architectures

Golriz Hoseinimanesh, Naser Mohammadzadeh

The physical synthesis concept for quantum circuits, the interaction between synthesis and physical design processes, was first introduced in our previous work. This concept inspires us to propose some techniques that can minimize the number of extra inserted SWAP operations required to run a circuit on a nearest-neighbor architecture. Minimizing the number of SWAP operations potentially decreases the latency and error probability of a quantum circuit. Focusing on this concept, we present a physical synthesis technique based on transformation rules to decrease the number of SWAP operations in nearest-neighbor architectures. After the qubits of a circuit are mapped onto the physical qubits provided by the target architecture, our procedure is fed by this mapping information. Our method uses the obtained placement and scheduling information to apply some transformation rules to the original netlist to decrease the number of extra SWAP gates required for running the circuit on the architecture. We follow two policies in applying a transformation rule, greedy and simulated-annealing-based policies. Simulation results show that the proposed technique decreases the average number of extra SWAP operations by about 20.6% and 24.1% based on greedy and simulated-annealing-based policies, respectively, compared with the best in the literature.

Quantum ReportsAug 15, 20212 citations