Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

• URL: http://arxiv.org/abs/2511.20618v2
• Date: Wed, 26 Nov 2025 14:57:45 GMT
• Title: Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations
• Authors: Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov,
• Abstract summary: We present optimized quantum circuits for multiplication and division operations.<n>Our ancilla-free GF multiplication circuit has the gate count complexity of $O(mlog3)$.<n>We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts.
• Score: 1.1694898979785655
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Compact Circuits for Constrained Quantum Evolutions of Sparse Operators [0.0]
  We introduce a general framework for constructing compact quantum circuits that implement the real-time evolution of Hamiltonians of the form $H = sigma P_B$.<n>We also construct transposition gates, widely used in quantum computing, that scale more efficiently than the best known constructions in literature.
  arXiv  Detail & Related papers  (2025-04-12T08:47:59Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  Windowed arithmetic is a technique for reducing the cost of quantum circuits with space--time tradeoffs.<n>In this work we introduce four optimizations to windowed modular exponentiation.<n>This leads to a $3%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications.
  arXiv  Detail & Related papers  (2025-02-24T16:59:16Z)
• Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost [3.129187821625805]
  We present an algorithm for constructing quantum circuits that perform multiplication over $GF (2n)$ with $mathcalO(nlog_(n))bits.<n>For some primitives, such as trinomials, the multiplication can be done in logarithmic depth and with $mathcalO(nlog_(n))bits.
  arXiv  Detail & Related papers  (2025-01-27T15:26:11Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Lower T-count with faster algorithms [2.488003578430483]
  We contribute to the $T$-count reduction problem by proposing efficient $T$-counts with low execution times.<n>We greatly improve the complexity of TODD, an algorithm currently providing the best $T$-count reduction on various quantum circuits.<n>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.
  arXiv  Detail & Related papers  (2024-07-11T17:31:20Z)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  We introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits. The only qubits involved are the input and output registers themselves. Our algorithm has the potential to outperform previous problem sizes relevant in practice.
  arXiv  Detail & Related papers  (2024-03-26T18:00:03Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  Two improvements to Regev's recent quantum factoring algorithm.<n>Regev's circuit requires $O(n3/2)$ qubits and $O(n3/2 log n)$ gates.<n>Regev's analysis of his classical postprocessing procedure requires all $approx sqrtn$ runs to be successful.
  arXiv  Detail & Related papers  (2023-10-02T04:31:21Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.