Lower T-count with faster algorithms
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911156824702976 |
|---|---|
| author | Vandaele, Vivien |
| author_facet | Vandaele, Vivien |
| contents | Among the cost metrics characterizing a quantum circuit, the $T$-count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the $T$-count reduction problem by proposing efficient $T$-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of $T$ gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated. We also prove that the number of $T$ gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of $n$ qubits is upper bounded by $n(n + 1)/2 + 1$, which improves on the worst-case $T$-count of existing optimization algorithms. From this we derive an upper bound of $(n + 1)(n + 2h)/2 + 1$ for the number of $T$ gates in a Clifford$+T$ circuit where $h$ is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last $T$ gate of the circuit. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08695 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lower T-count with faster algorithms Vandaele, Vivien Quantum Physics Among the cost metrics characterizing a quantum circuit, the $T$-count stands out as one of the most crucial as its minimization is particularly important in various areas of quantum computation such as fault-tolerant quantum computing and quantum circuit simulation. In this work, we contribute to the $T$-count reduction problem by proposing efficient $T$-count optimizers with low execution times. In particular, we greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits. We also propose some modifications to the algorithm which are leading to a significantly lower number of $T$ gates. In addition, we propose another algorithm which has an even lower complexity and that achieves a better or equal $T$-count than the state of the art on most quantum circuits evaluated. We also prove that the number of $T$ gates in the circuit obtained after executing our algorithms on a Hadamard-free circuit composed of $n$ qubits is upper bounded by $n(n + 1)/2 + 1$, which improves on the worst-case $T$-count of existing optimization algorithms. From this we derive an upper bound of $(n + 1)(n + 2h)/2 + 1$ for the number of $T$ gates in a Clifford$+T$ circuit where $h$ is the number of internal Hadamard gates in the circuit, i.e. the number of Hadamard gates lying between the first and the last $T$ gate of the circuit. |
| title | Lower T-count with faster algorithms |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2407.08695 |