Optimal T depth quantum circuits for implementing arbitrary Boolean functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916772746100736 |
|---|---|
| author | Dutta, Suman Bhaumik, Anik Basu Chattopadhyay, Anupam Maitra, Subhamoy |
| author_facet | Dutta, Suman Bhaumik, Anik Basu Chattopadhyay, Anupam Maitra, Subhamoy |
| contents | In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ having algebraic degree $k\leq n$, and it achieves an exact Toffoli (and T) depth of $\lceil \log_2 k \rceil$. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01542 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal T depth quantum circuits for implementing arbitrary Boolean functions Dutta, Suman Bhaumik, Anik Basu Chattopadhyay, Anupam Maitra, Subhamoy Quantum Physics In this paper we present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f: \{0,1\}^n \rightarrow \{0,1\}^m$ having algebraic degree $k\leq n$, and it achieves an exact Toffoli (and T) depth of $\lceil \log_2 k \rceil$. This is a broader generalization of the recent result establishing the optimal Toffoli (and consequently T) depth for multi-controlled Toffoli decompositions (Dutta et al., Phys. Rev. A, 2025). We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function. Obtaining a benchmark for the minimum T depth of such circuits are of prime importance for efficient implementation of quantum algorithms by enabling greater parallelism, reducing time complexity, and minimizing circuit latency, making them suitable for near-term quantum devices with limited coherence times. The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations, for example AES. |
| title | Optimal T depth quantum circuits for implementing arbitrary Boolean functions |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2506.01542 |