Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations
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_ | 1866910066958925824 |
|---|---|
| author | Yosri, Noureldin Gavinsky, Dmytro Maslov, Dmitri |
| author_facet | Yosri, Noureldin Gavinsky, Dmytro Maslov, Dmitri |
| contents | We present optimized quantum circuits for GF$(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$, an improvement over the previous best bound of $O(m^2)$. This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_20618 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations Yosri, Noureldin Gavinsky, Dmytro Maslov, Dmitri Quantum Physics Emerging Technologies We present optimized quantum circuits for GF$(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$, an improvement over the previous best bound of $O(m^2)$. This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary. |
| title | Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2511.20618 |