Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929688099684352 |
|---|---|
| author | Vandaele, Vivien |
| author_facet | Vandaele, Vivien |
| contents | Multiplication over binary fields is a crucial operation in quantum algorithms designed to solve the discrete logarithm problem for elliptic curve defined over $GF(2^n)$. In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over $GF(2^n)$ with $\mathcal{O}(n^{\log_2(3)})$ Toffoli gates. We propose a variant of our construction that achieves linear depth by using $\mathcal{O}(n\log_2(n))$ ancillary qubits. This approach provides the best known space-time trade-off for binary field multiplication with a subquadratic number of Toffoli gates. Additionally, we demonstrate that for some particular families of primitive polynomials, such as trinomials, the multiplication can be done in logarithmic depth and with $\mathcal{O}(n^{\log_2(3)})$ gates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_16136 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost Vandaele, Vivien Quantum Physics Multiplication over binary fields is a crucial operation in quantum algorithms designed to solve the discrete logarithm problem for elliptic curve defined over $GF(2^n)$. In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over $GF(2^n)$ with $\mathcal{O}(n^{\log_2(3)})$ Toffoli gates. We propose a variant of our construction that achieves linear depth by using $\mathcal{O}(n\log_2(n))$ ancillary qubits. This approach provides the best known space-time trade-off for binary field multiplication with a subquadratic number of Toffoli gates. Additionally, we demonstrate that for some particular families of primitive polynomials, such as trinomials, the multiplication can be done in logarithmic depth and with $\mathcal{O}(n^{\log_2(3)})$ gates. |
| title | Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2501.16136 |