Cheaper quantum gates by borrowing a single spare qubit

Multi-controlled Toffoli gates are expensive in fault-tolerant quantum computers because non-Clifford operations (T gates) dominate resource costs and limit parallelism. This work derives tight resource bounds for breaking large Toffoli gates into 3- and 4-input relative-phase variants using a single clean ancilla, combined with dynamic-circuit uncomputation and measurement-conditioned corrections. The key finding is that 4-input relative-phase Toffoli gates unlock additional parallelism, cutting T-depth significantly without demanding many extra qubits. The results are validated experimentally and benchmarked against existing methods.