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. © 2026 Information Processing Society of Japan.

This paper shows that the minimum number of Toffoli gates to realize any 4-input function is at most five for the first time as far as we know. This result should be not only theoretically interesting but also practically useful because sub-circuits to calculate 4-input functions are used in the practical quantum Boolean circuit design framework based on LUT-network synthesis, and the state-of-the-art heuristic method requires an average of 9.29 Toffoli gates to realize 4-input functions. Because previous SAT-based exact design methods cannot find the minimum number of Toffoli gates to implement a target function, we introduce a novel idea, complex Toffoli gates, which are very useful to significantly reduce the search space to find a quantum Boolean circuit with the minimum number of Toffoli gates; we can successfully formulate the problem as an SMT problem by using complex Toffoli gates, which should be interesting on their own. © 2025 IEEE.