On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929709185499136 |
|---|---|
| author | Dutta, Suman Wang, Siyi Baksi, Anubhab Chattopadhyay, Anupam Maitra, Subhamoy |
| author_facet | Dutta, Suman Wang, Siyi Baksi, Anubhab Chattopadhyay, Anupam Maitra, Subhamoy |
| contents | In this paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford $+$ T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the $n$-controlled Toffoli (hereform we will tell $n$-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the ($2$-controlled) Toffoli gate can further be decomposed using Clifford $+$ T, various methodologies are explored too in this regard for trade-off related implications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01433 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition Dutta, Suman Wang, Siyi Baksi, Anubhab Chattopadhyay, Anupam Maitra, Subhamoy Quantum Physics 81P65 In this paper, we consider the optimized implementation of Multi Controlled Toffoli (MCT) using the Clifford $+$ T gate sets. While there are several recent works in this direction, here we explicitly quantify the trade-off (with concrete formulae) between the Toffoli depth (this means the depth using the classical 2-controlled Toffoli) of the $n$-controlled Toffoli (hereform we will tell $n$-MCT) and the number of clean ancilla qubits. Additionally, we achieve a reduced Toffoli depth (and consequently, T-depth), which is an extension of the technique introduced by Khattar et al. (2024). In terms of a negative result, we first show that using such conditionally clean ancilla techniques, Toffoli depth can never achieve exactly $\ceil{\log_2 n}$, though it remains of the same order. This highlights the limitation of the techniques exploiting conditionally clean ancilla [Nie et al., 2024, Khattar et al., 2024]. Then we prove that, in a more general setup, the T-Depth in the Clifford + T decomposition, via Toffoli gates, is lower bounded by $\ceil{\log_2 n}$, and this bound is achieved following the complete binary tree structure. Since the ($2$-controlled) Toffoli gate can further be decomposed using Clifford $+$ T, various methodologies are explored too in this regard for trade-off related implications. |
| title | On Exact Space-Depth Trade-Offs in Multi-Controlled Toffoli Decomposition |
| topic | Quantum Physics 81P65 |
| url | https://arxiv.org/abs/2502.01433 |