International Conference on Electronics, Circuits and Information Engineering (ECIE)

MCT Circuit Decomposition for Two-Dimensional Topological Structures

Yibo Jiang, Junde Wu, Xueyun Cheng, Zhijin Guan

Published May 23, 2025• 0 citations

Abstract

With the rapid development of the field of quantum computing, quantum computing devices have entered the era of noisy intermediate-scale quantum (NISQ). However, current NISQ quantum computing devices still face the challenge of physical constraints. In order to enable quantum algorithms to be directly executed on quantum computing devices, it is necessary to decompose the advanced quantum gates (such as the MCT gate) in the quantum circuit and map them onto the quantum computing devices. This paper proposes a decomposition method for advanced quantum gates that is aware of the two-dimensional topological structure. Based on the proposed decomposition rules of the MCT gate, this method designs a search algorithm for associated gate pairs that is conducive to subsequent decomposition, and divides the control bits of the MCT gate based on the associated gate pairs, making the division method more adaptable to the topological structure. After the associated gate pairs are inversely decomposed to eliminate redundant gates, the circuit mapping is carried out. The experimental results show that the decomposition method proposed in this paper can reduce the number of basic quantum gates in the quantum circuit, with an average optimization rate of 14.6%; for the benchmark circuits using the decomposition method in this paper, when the routing algorithm is applied for mapping, the number of additional gates required is smaller, with an average optimization rate of 20.6%.

DOI: 10.1109/ecie65947.2025.11086805

Related papers

Device-Aware Decomposition and Mapping of Multiple-Control Toffoli Circuits in Quantum Computing Systems

Yibo Jiang, Xueyun Cheng, Pengcheng Zhu +2 more

Abstract With the rapid development of quantum computing, quantum computing devices have entered the Noisy Intermediate-Scale Quantum(NISQ)era. However, current NISQ quantum computing devices still face the challenge of physical limitations. To enable quantum algorithms to be directly executed on quantum computing devices, high-level quantum gates (such as MCT gates) in quantum circuits need to be decomposed and mapped onto quantum computing devices. This paper proposes a quantum device-aware method for decomposing high-level quantum gates. This method selects an optimal sub-topology of the quantum device as the target based on the circuit scale and the goal of reducing error rates. According to the proposed MCT gate decomposition rules, an associated gate-pairs generation algorithm is designed to facilitate subsequent decomposition. The control bits of the MCT gates are partitioned based on the associated gate-pair to better match the selected sub-topology. After eliminating redundant gates through the inverse decomposition of associated gate-pairs, the mapping is performed. Experimental results show that the proposed decomposition method reduces the number of basic quantum gates in quantum circuits, with an average optimization rate of 14.6%. For benchmark circuits decomposed using the method, applying the routing algorithm for mapping requires fewer additional gates, with an average optimization rate of 20.6%. The fidelity of the circuits improved by an average of 14.1% after mapping.

Sep 13, 20240 citations

Pre-processing of quantum circuit mapping based on circuit partitioning and unitary matrix decomposition

Kexin Cao, Xueyun Cheng, Xinyu Chen +1 more

Quantum computing is currently in the era of Noisy-Intermediate-Scale Quantum (NISQ), where superconducting quantum chips can only support two-qubit gates between adjacent physical qubits. This constraint necessitates the insertion of SWAP gates during circuit mapping to ensure that the nearest neighbor requirements are met on actual quantum computing devices. In this work, based on the circuit partitioning and unitary matrix decomposition mechanism, an equivalent transformation form of quantum circuit is given to reduce the number of two-qubit gates in the target quantum circuit. Experimental results demonstrate that the decomposed equivalent circuits have a shorter depth, with an average optimization rate of 18.41%. Our proposed optimization method effectively reduces the number of two-qubit gates in quantum circuits, enhancing the efficiency of mapping on NISQ devices.

International Conference on Electronics, Circuits and Information Engineering (ECIE)May 24, 20240 citations

A Decomposition Method for MCT Gates Considering T-depth of Each Qubit

Zhijun Qi, Kouki Hirono, David Clarino +1 more

For realizing future fault-tolerant quantum computation, it is very important to reduce so-called the T-depth of a target quantum circuit. Thus, there have been many researches to consider how to decompose Multiple Controlled Toffoli (MCT) gates with few T-depth; these existing methods does not consider the T-depth of each qubit when they decompose one MCT gate. In contrast to existing methods, this paper proposes to consider the T-depth of each qubit when we decompose an MCT gate; we show that we can decrease the T-depth by considering Tdepth of each bit and appropriately selecting ancilla qubits and decomposition methods. In addition, to consider the impact of the decomposition of one MCT gate on the decomposition of subsequent gates, our method utilizes beam search to select a possibly best decomposition for each MCT gate. We confirmed that the proposed method can reduce the T-depth by an average of 17.1% compared to existing methods.

IEEE Computer Society Annual Symposium on VLSIJul 6, 20251 citation

A Decomposition Method of MCT Gates for Reducing Overall Circuit T-depth

Zanhe Qi, Koki Hirono, David Clarino +1 more

It is considered to be very important to reduce so-called the T-depth of a target quantum circuit for realizing future fault-tolerant quantum computation. Thus, there have been many researches to consider how to decompose Multiple Controlled Toffoli (MCT) gates with few T-depth; these existing methods do not consider the T-depth of each qubit when they decompose one MCT gate. In contrast to existing methods, this paper proposes to consider the T-depth of each qubit when we decompose an MCT gate; we show that we can decrease the T-depth by considering the T-depth of each qubit and appropriately selecting ancilla qubits and decomposition methods. In addition, to consider the impact of the decomposition of one MCT gate on the decomposition of subsequent gates, our method utilizes beam search to select a possibly best decomposition for each MCT gate. We confirmed that the proposed method can reduce the T-depth by an average of 17.1% compared to existing methods.

IPSJ Transactions on System and LSI Design MethodologyJan 1, 20260 citations

Optimizing Layout Synthesis for Quantum Computing Performance

Chi‐Chou Kao, Hung-Yi Lin

In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.

Journal of Circuits Systems and ComputersMar 6, 20250 citations

Layout Synthesis for Quantum Circuits Considering Toffoli Gate Decomposition

Po-Wei Chen, Sheng-Tan Huang, Shao‐Yun Fang

State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.

ACM Transactions on Design Automation of Electronic SystemsJun 16, 20251 citation