Spyros Tserkis, Muhammad Umer, Eleftherios Mastorakis, Dimitris G. Angelakis
The decomposition of complex quantum operations into experimentally feasible gate sets has been a central challenge since the early development of quantum computing. The multi-controlled Toffoli (MCT) gate is a key example, with applications across a wide range of quantum algorithms, whose decomposition into smaller gates, however, typically leads to deep circuits. In this work, we introduce a teleportation-based decomposition that implements an arbitrary MCT gate with unit Toffoli depth, independent of the number of controls, while maintaining a relatively low Toffoli count compared to existing approaches. This is achieved at the cost of a linear overhead in ancilla qubits and the ability to distribute entangled pairs across distant qubits, a capability already available in several quantum computing platforms. We further demonstrate the advantages of this implementation in circuits that rely on MCT gates, such as the adder operator, quantum read-only memory, quantum neurons, and quantum decision trees.
Cite as BibTex
@misc{tserkis2026minimumtoffolidepthmulticontrolled,
title={Minimum Toffoli depth for the multi-controlled Toffoli gate via teleportation},
author={Spyros Tserkis and Muhammad Umer and Eleftherios Mastorakis and Dimitris G. Angelakis},
year={2026},
eprint={2604.25861},
archivePrefix={arXiv},
primaryClass={quant-ph},
url={https://arxiv.org/abs/2604.25861},
}