Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford Gates
In the authors' words
Temporary occupation of qutrit levels can reduce the width and depth required for binary circuit logic in quantum computing. We introduce an efficient intermediate-qutrit decomposition of multi-controlled Toffoli gates with binary-subspace inputs and outputs. For balanced control widths , the proposed decomposition is evaluated hierarchically through a tree, allowing independent subtree computations to proceed in parallel and reducing the depth from linear to logarithmic. The balanced low-depth construction requires logical injections and clean ancillary qutrits. It matches the direct count of a recursively extended Clifford+ baseline derived from the state-of-the-art work while using asymptotically one-quarter as many clean ancillas and replacing linear depth with logarithmic depth. For arbitrary control widths, a sequential extension preserves the count but has depth for a balanced core , which is linear in the worst case over . By reducing the resource overhead of a widely used reversible primitive, the proposed decomposition provides a practical building block for the design and compilation of more resource-efficient quantum algorithms in the fault-tolerant regime.
Appeared: Friday, September 25. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 15 pages, 3 figures