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.
We present a method for reducing the number of non-Clifford quantum gates, in particularly T-gates, in a circuit, an important task for efficiently implementing fault-tolerant quantum computations. This method matches or beats previous approaches to ancillae-free T-count reduction on the majority of our benchmark circuits, in some cases yielding up to 50% improvement. Our method begins by representing the quantum circuit as a ZX-diagram, a tensor networklike structure that can be transformed and simplified according to the rules of the ZX-calculus. We then extend a recent simplification strategy with a different ingredient, phase gadgetization, which we use to propagate non-Clifford phases through a ZX-diagram to find nonlocal cancellations. Our procedure extends unmodified to arbitrary phase angles and to parameter elimination for variational circuits. Finally, our optimization is self-checking, in the sense that the simplification strategy we propose is powerful enough to independently validate equality of the input circuit and the optimized output circuit. We have implemented the routines of this paper in the open-source library pyzx.
Physical implementation of scalable quantum architectures faces an immense challenge in the form of fragile quantum states. To overcome it, quantum architectures with fault tolerance are desirable. These are achieved currently by using a surface code along with a transversal gate set. This indicates the need for decomposition of universal
n-qubit multicontrolled Toffoli (
n-MCT) gates using a transversal gate set. Additionally, the transversal non-Clifford phase gate incurs high latency, which makes it an important factor to consider during decomposition. Additionally, the decomposition of a large MCT gate without ancillas presents an additional hurdle. In this paper, we address both of these issues by introducing the
Clifford+ZN gate library. We present an ancilla-free decomposition of MCT gates with linear phase depth and quadratic phase count. Furthermore, we provide a technique for decomposition of MCT gates in unit phase depth using the
Clifford+ZN library, albeit at the cost of ancillary lines and exponential phase count.
In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and
π/2-phase rotations, together with T operations (
π/4-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem [arXiv:1206.0758, 1303.2042, 1308.4134, 1601.07363, 1606.01904, 1701.00140] has led to observations that this problem is closely related to NP-hard tensor decomposition problems [arXiv:1712.01557] and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes [arXiv:1601.07363]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of spider nest identities: easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.
The
T-count is a dominant cost of fault-tolerant Clifford
+T computation. We prove that every Hadamard-free Clifford
+T circuit with clean ancillas for a layer of
m disjoint CCZ gates, the diagonal core of a parallel Toffoli layer, uses at least
6m+1 T gates. Campbell and Howard gave a circuit with
6m+1, and to our knowledge this is the first proof that it is optimal for general
m. The proof combines Campbell and Howard's self-orthogonality of the columns of the parity matrix with a rank (flattening) bound, sharpened by one. More generally, the argument gives a lower bound on the
T-count of every diagonal gate in the third level of the Clifford hierarchy, the isotropy floor, computable by Gaussian elimination. It is never below the stabilizer nullity
ν and reaches
2ν+1 on non-Clifford gates whose phase is purely cubic. No bound that also holds for circuits with measurement and feedforward can do this, since such circuits implement CCZ (
ν=3) with four
T gates and the layer with
4m, where the floor gives seven and
6m+1. The floor also recovers Campbell and Howard's count
4m+3 for a fan-out of Toffolis. On the output of PyZX's TODD-based optimizer, relative to its Hadamard placement, it certifies
193 of
311 phase-polynomial blocks
T-optimal once repeated parities are merged (at the best of five optimizer seeds), against
113 for nullity, including
37 of the
72 blocks too large for exhaustive search.
The well-known 3-bit Hermitian gate (a Toffoli gate) has been implemented using Clifford + T circuits. Compared with the Peres gate, its implementation circuit requires more controlled-NOT (CNOT) gates. However, the Peres gate is not Hermitian. This paper reports four 3-bit Hermitian gates named LI gates. Whose realized circuits have the same T-count, T-depth, and CNOT-count as the Peres gate. Furthermore, two decomposition methods of a multiple control Toffoli (MCT) gate are proposed for different primary optimization goals. Then, we design the equality, less-than, and full comparators with the minimum circuit width using proposed Hermitian gates and optimized MCT gates. A fault-tolerant circuit is required for robust quantum computing. Clifford+T circuits are accepted solutions for fault-tolerant implementation. Considering T-count, T-depth, CNOT-count, and circuit width as the primary optimization goals, we design the optimized Clifford + T circuits of three comparators using LI gates and optimized MCT gates. Comparison and analysis show that the proposed comparators have better overall performances for T-count, T-depth, CNOT-count, and circuit width than the best-known comparators without quantum measurements.