This paper presents a heuristic for reducing T-depth in quantum circuits by jointly decomposing multiple multi-controlled Toffoli (MCT) gates with careful selection of control and ancilla qubits. Our experimental results show that our method achieves an average 58.06% reduction in overall T-depth in designed quantum oracles compared with existing decompositions. We further estimate the actual runtime of solving a 45-variable SAT problem on a future fault-tolerant quantum computer and show that our method reduces the execution time to 48.5% of that of a conventionally generated circuit; our result gives a concrete example of a search problem where a fault-tolerant quantum computer would outperform a classical one with a brute-force method.
This paper presents a heuristic for reducing T-depth in quantum circuits by jointly decomposing multiple multi-controlled Toffoli (MCT) gates with careful selection of control and ancilla qubits. Our experimental results show that our method achieves an average 58.06% reduction in overall T-depth in designed quantum oracles compared with existing decompositions. We further estimate the actual runtime of solving a 45-variable SAT problem on a future fault-tolerant quantum computer and show that our method reduces the execution time to 48.5% of that of a conventionally generated circuit; our result gives a concrete example of a search problem where a fault-tolerant quantum computer would outperform a classical one with a brute-force method.
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.
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.
The decomposition of complex quantum operations into experimentally feasible gate sets has been a central challenge since the early development of quantum computing. The multi-controlled Toffoli (MCT) gate is a key example, with applications across a wide range of quantum algorithms, whose decomposition into smaller gates, however, typically leads to deep circuits. In this work, we introduce a teleportation-based decomposition that implements an MCT gate. This decomposition has unit Toffoli depth, independent of the number of controls, while achieving the lowest Toffoli count among existing approaches for more than five controls at the cost of a linear overhead in ancilla qubits. We also investigate the parameter regimes in which the teleportation-based decomposition is preferable by analyzing the relative quality of distributed entanglement and Toffoli gates. We further demonstrate the advantages of this implementation in circuits that rely on MCT gates, such as the adder operator, quantum read-only memory, quantum neurons, and quantum decision trees.
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.
The multi-controlled Toffoli (MCT) gate is a key primitive in quantum arithmetic, oracle construction, and quantum cryptanalysis. Although recent work has established optimal Toffoli-depth MCT decompositions under all-to-all qubit connectivity, their realization on near-term quantum hardware with restricted qubit connectivity remains largely unexplored. While general-purpose quantum mappers can route arbitrary circuits, they do not explicitly exploit the repeated interaction patterns inherent in MCT decompositions.
In our present paper, we study architecture-aware mappings of optimal Toffoli-depth MCT decompositions onto restricted two-dimensional qubit layouts. We begin with a structured geometric placements that preserve the parallelism of state-of-the-art Toffoli and MCT decompositions with no additional depth overhead. We further introduce a motif-based packing framework in which decomposition layers are represented by interaction motifs derived from basic Toffoli gates. By embedding these motifs vertex-disjointly into hardware graphs, we characterize the minimum-size topologies supporting the required qubit resources and derive explicit bounds on the resulting depth overhead under tight qubit budgets. Finally, we compare these bounds with routing-aware placement heuristics and empirically evaluate the effectiveness of embedding different motifs across a range of hardware topologies.
Multi-controlled Toffoli gates are fundamental building blocks in quantum computation, with applications in quantum arithmetic, simulation, and search algorithms. In fault-tolerant architectures, their realization is constrained by the high cost of non-Clifford resources, particularly in terms of T-count and T-depth. Recent advances have demonstrated that the use of ancillary qubits, relative-phase Toffoli gates, and dynamic circuit techniques can substantially reduce this overhead.
In this work, we investigate the decomposition of large Toffoli gates using 3- and 4-input relative-phase Toffoli gates in the presence of a single clean ancilla and conditionally clean ancillas. We derive explicit resource bounds for Clifford+T implementations incorporating dynamic-circuit-based uncomputation and measurement-conditioned corrections. Our analysis emphasizes T-depth reduction under fixed CX and T-count overhead, ensuring relevance for near-term devices. We show that introducing 4-input relative-phase Toffoli gates enables significant T-depth reductions through enhanced parallelism while maintaining favorable ancilla requirements. We further validate our theoretical results through experimental evaluation and comparative analysis with existing approaches.