Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost

2025/01/27 by Vivien Vandaele, Vandaele, Vivien · 2 citations
Computer Science · #Coding theory and cryptography #FOS: Physical sciences #Polynomial and algebraic computation #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2501.16136

openalex publication_date 2025/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

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ⁿ). In this paper, we present an algorithm for constructing quantum circuits that perform multiplication over GF(2ⁿ) with O(n^log₂(3)) Toffoli gates. We propose a variant of our construction that achieves linear depth by using O(nlog₂(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 O(n^log₂(3)) gates.

Cited by

• Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations
• Symmetry-accelerated classical simulation of Clifford-dominated circuits

Related

• Space-efficient quantum multiplication of polynomials for binary finite fields with sub-quadratic Toffoli gate count
• New Space-Efficient Quantum Algorithm for Binary Elliptic Curves using the Optimized Division Algorithm
• A quantum circuit to find discrete logarithms on ordinary binary\n elliptic curves in depth O(log² n)
• Asymptotic yet practical optimization of quantum circuits implementing GF(2^m) multiplication and division operations
• Quantum resource estimates for computing elliptic curve discrete logarithms