Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, the T-gate incurs extra cost relative to Clifford gates like the S-gate and CNOT gate. Relative-phase Toffoli Gates (RTOFs) have been proposed as a way to reduce this T-count at the cost of incurring a relative phase that could skew the final quantum states. In this paper, we utilize an observation that the relative phase which RTOFs introduce can be canceled by the appropriate application of less expensive S-gates instead of T-gates. It leverages alternate forms of the RTOF including incorporating S-gates into it or moving around its input bits in order to simplify the logic to erase the relative phase. We find experimentally that our method has a clear advantage in most cases, and identify several types of circuits that it could be synergistic with.
Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, the T-gate incurs extra cost relative to Clifford gates like the S-gate and CNOT gate. Relative-phase Toffoli Gates (RTOFs) have been proposed as a way to reduce this T-count at the cost of incurring a relative phase that could skew the final quantum states. In this paper, we utilize an observation that the relative phase which RTOFs introduce can be canceled by the appropriate application of less expensive S-gates instead of T-gates. It leverages alternate forms of the RTOF including incorporating S-gates into it or moving around its input bits in order to simplify the logic to erase the relative phase. We find experimentally that our method has a clear advantage in most cases, and identify several types of circuits that it could be synergistic with.
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.
Toffoli gates are an important primitive in reversible Boolean logic. In quantum computation, these Toffoli gates are composed using other elementary gates, most notably the Clifford+T basis. However, in fault-tolerant implementations of quantum circuits, a non-transversal gate like the T gate incurs extra cost relative to transversal gates like the S and CNOT gates. Relative-phase Toffoli Gates (RTOF) have been proposed as a way to minimize this "T-depth" at the cost of incurring a relative phase that could skew the final quantum states. While previous research has proposed a way to use transversal S gates to eliminate this relative phase, this paper proposes a novel form of the RTOF that incorporates S gates in order to simplify generation of the logic to return the phase
In fault-tolerant Clifford+T circuits, a Boolean oracle costs T gates and extra qubits, and on four or more qubits every exact Toffoli gate needs an extra qubit. Gosset, Kothari and Zhang showed that sampling a fresh random circuit for each call makes the T-count of the Toffoli gate independent of its size, but a direct implementation of their sampler uses about one extra qubit per bit of precision. We show that computing the sampled parities in place, on the gate's own controls, removes every extra qubit once the gate is large enough: each random circuit then uses about 8 T gates per bit of precision and borrows only the gate's own idle inputs. This is one T gate more per circuit than the best measurement-free variant that keeps one clean ancilla. The same holds for exclusive-ors of indicators of affine subspaces, such as equality tests and checks of linear equations. For randomized circuits that do not measure, this is within a factor of eight of optimal up to an additive constant, even with extra qubits, and when each random circuit computes a Boolean function exactly, closing the factor asymptotically is equivalent to determining the leading constant in the T-count of exact multi-controlled Toffoli gates. Finally, the oracle of the indicator of a random set of fixed density needs exponentially many T gates at constant error, while that of an affine subspace of the same density needs a constant number, and extra qubits reduce the exponential cost only quadratically.
Currently, the most used universal quantum gate set is the augmented Clifford+T set of gates. Most commonly, we use the cost reduction in terms of the T-depth or T-count to implement logic primitives such as the Toffoli gate. While a lot of research has been done in this area, the Clifford+T set of gates is difficult to use for the synthesis of larger multi-controlled NOT gates (CnNOT) or simply larger circuits. To address this issue, in this work, we examine the composition of the Toffoli gate in relation to the T-gates. We adopt an approach based on the logic formalization of the T-gate placement and deduce three main results. First, if the trailing phase is not a concern, we can efficiently reduce the number of T gates. The second result is that to construct CnNOT gates for n>2 the T gates require smaller angles of rotation (analogous to the original scaling problem in the Barenco et al. Toffoli implementation). Lastly, we demonstrate that it is feasible to substitute all T gates with RZrotations, ensuring the correct logic operation and a constant phase across all outputs.
In fault-tolerant quantum circuit synthesis, T gates supplied via magic states dominate space-time cost, while Clifford gates incur negligible overhead. Conventional flows minimize AND count in an {XOR, AND, NOT} basis as a proxy for T, which neglects phase cancellation and can be far from T-optimal. We instead formulate an exact T synthesis problem and canonicalize Boolean functions under Clifford equivalence. By precomputing T-optimal implementations up to seven variables and developing a customized mapper, we reduce the T count by up to 14.3% on EPFL benchmarks and improve the T counts of several cryptographic modules by up to 40%.
The Toffoli gate (controlled-controlled-NOT) and its multi-controlled generalizations are fundamental logical building blocks of quantum algorithms and utilized extensively in pivotal algorithms such as Grover’s algorithm and Shor’s algorithm. Despite being a fundamental logical primitive of quantum algorithms, Toffoli gates must be decomposed to primitive single-qubit and two-qubit gates which are available in physical quantum hardware. These decompositions incur significant implementation costs in circuit depth and gate count, costs that propagate directly to the entire circuit. Consequently, reducing the implementation cots of Toffoli gates provides a direct method of reducing the implementation costs of many quantum algorithms. This thesis evaluates state-of-the-art methods for reducing the implementation costs of Toffoli gates by introducing approximations. While approximations introduce errors to the output of the Toffoli gate, they can reduce the depth and gate count of the implementation. This thesis finds that discrete errors in two-qubit and three-qubit controlled Toffoli gates have been utilized to reduce the gate counts in such a way that the implementation is exact cancelling the errors. Additionally, continuous errors are utilized to reduce the depth of a multi-controlled Toffoli gate decomposition in ancilla-free settings. However, this review also demonstrates other, non-approximate, construction of multi-controlled Toffoli gate, which achieves comparable implementation costs demonstrating marginal gains for the approximation techniques currently.